연결 리스트(Linked List)란?
연결 리스트는 요소들이 포인터를 통해 서로 연결되어 있는 선형 자료 구조입니다. 연결 리스트의 각 요소, 즉 노드(node)는 데이터를 저장하는 info 부분과 다음 노드를 가리키는 next 포인터(링크)로 구성됩니다. 배열과 달리 연결 리스트의 요소들은 메모리상에 반드시 연속된 위치에 저장될 필요가 없습니다.
문제 정의
데이터 부분과 다음 노드를 가리키는 링크로 이루어진 단일 연결 리스트(singly linked list)가 주어지고, 또 다른 입력으로 정수 K가 제공됩니다. 우리의 과제는 이 연결 리스트의 요소들 중 K로 나누어 떨어지는 값들만 골라 그중 최댓값(Max)과 최솟값(Min)을 찾는 것입니다.
선형 연결 리스트는 한 방향으로만 순회할 수 있으므로, 헤드(head) 노드부터 시작해 각 노드를 차례대로 방문하면서 해당 노드의 데이터가 K로 나누어 떨어지는지 확인합니다. 나누어 떨어지는 경우, 지금까지 발견한 최댓값(maxD)보다 크면 maxD를, 최솟값(minD)보다 작으면 minD를 갱신합니다.
예제 1
입력
SList : 5-->2-->10-->12-->3-->20-->7, K=5
출력
K로 나누어 떨어지는 최댓값 : 20
K로 나누어 떨어지는 최솟값 : 5
설명 − 헤드 노드부터 순회하면서 각 노드의 데이터를 K로 나누어 나머지가 0인지, 즉 완전히 나누어 떨어지는지 확인합니다.
전체 요소 중 5, 10, 20만이 5로 나누어 떨어지며, 그중 최솟값은 5, 최댓값은 20입니다.
예제 2
입력
SList : 12-->2-->5-->18-->3-->144-->7, K=4
출력
K로 나누어 떨어지는 최댓값 : 144
K로 나누어 떨어지는 최솟값 : 12
설명 − 마찬가지로 헤드 노드부터 순회하면서 각 노드의 데이터를 K로 나누어 나머지가 0인지 확인합니다.
전체 요소 중 12와 144만이 4로 나누어 떨어지며, 그중 최솟값은 12, 최댓값은 144입니다.
프로그램에서 사용한 접근 방식
연결 리스트 노드를 생성합니다. 여기서는 info 부분과 next 포인터를 멤버로 가지는 SLLnode 클래스를 만들었습니다.
연결 리스트를 생성합니다. SLLnode 객체를 멤버로 가지는 SLList 클래스를 만들었으며, SLList는 SLLnode들의 집합으로 구성됩니다.
addtohead(int) 함수는 리스트의 헤드에 새 노드를 추가하는 역할을 합니다.
SLList 객체인 LIST를 통해 addtohead(int)를 호출하여 리스트에 요소들을 추가합니다.
리스트 생성이 완료되면 리스트의 헤드와 정수 K를 두 개의 매개변수로 받는 Divisible(SLLnode*, int) 함수를 호출합니다.
Divisible 함수 내부에서는 K로 나누어 떨어지는 최댓값과 최솟값을 저장하기 위해 maxD와 minD 두 변수를 사용합니다.
maxD는 -1로, minD는 9999로 초기화합니다. 이는 입력 값이 존재한다고 가정하는 범위입니다.
for 루프 안에서 헤드부터 연결 리스트를 순회합니다. 이때 start 변수가 헤드를 가리킵니다.
각 노드의 info 값을 maxD, minD와 비교하면서 K로 나누어 떨어지는지 검사합니다. 현재 노드의 info가 K로 나누어 떨어지고 minD보다 작으면 minD를 현재 info 값으로 갱신합니다.
현재 노드의 info가 K로 나누어 떨어지고 maxD보다 크면 maxD를 현재 info 값으로 갱신합니다.
순회가 끝나면 minD와 maxD에 저장된 결과를 출력합니다.
예제 코드
#include<iostream.h>
#include<process.h>
#include<conio.h>
class SLLnode{
public:
int info;
SLLnode *next;
SLLnode(int e1,SLLnode *ptr=0){
info=e1;
next=ptr;
}
};
class SLList{
public:
SLLnode *head;
SLList()
{ head=0; }
void addtohead(int); };
void SLList::addtohead(int el)
{ head=new SLLnode(el,head); }
void Divisible(SLLnode* head, int K){
int minD=9999;
int maxD=-1;
SLLnode* start=head;
for(start;start->next!=NULL;start=start->next){
if ((start->info < minD) && (start->info % K == 0))
minD = start->info;
if ((start->info > maxD) && (start->info % K == 0))
maxD = start->info;
}
cout << "Max Element divisible by K: " << maxD << endl;
cout << "Min Element divisible by K: " << minD;
}
// Driver Code
int main(){
clrscr();
// Start with empty list
SLList LIST;
LIST.addtohead(50);
LIST.addtohead(21);
LIST.addtohead(32);
LIST.addtohead(45);
LIST.addtohead(11);
LIST.addtohead(23);
LIST.addtohead(90);
LIST.addtohead(56);
int K = 5;
Divisible(LIST.head, K);
getch();
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Max Element divisible by K: 90
Min Element divisible by K: 45
참고: 위 코드는 구형 Turbo C++ 환경(iostream.h, conio.h 등)을 기준으로 작성되었습니다. 최신 컴파일러(GCC, MSVC 등)에서 실행하려면 #include <iostream>과 using namespace std;를 사용하고, clrscr()·getch() 같은 conio.h 의존 함수는 제거하거나 대체해야 합니다.