자료구조&알고리즘 (2)
이 글은 자료구조와 알고리즘을 '코딩 인터뷰'를 준비한다는 목적에서 정리한 글입니다.
이번 글은 연결 리스트(linked list)를 다루겠습니다.
(1) 연결 리스트(linked list)
- 연결 리스트는 차례로 연결된 노드를 표현해주는 자료구조입니다.
단방향 연결 리스트에서 각 노드는 다음 노드를 가리킵니다.
양방향 연결 리스트에서 각 노드는 다음 노드와 이전 노드를 함께 가리킵니다.
면접에서 연결리스트에 관해 이야기 할 때는,
단방향 연결리스트에 대한 이야기인지, 양방향 연결리스트에 관한 이야기인지
반드시 인지하고 있어야 합니다.
Q. 왜 면접에서 연결리스트에 관해 이야기할 때, 단방향 연결리스트에 관한 이야기인지,
양방향 연결리스트에 관한 이야기인지 반드시 인지하고 있어야합니까?
A. 단방향 연결리스트냐, 양방향 연결리스트냐에 따라 문제의 해결 방법이 다르기 때문입니다.
Q. 왜 단방향 연결리스트냐, 양방향 연결리스트냐에 따라 문제의 해결 방법이 다릅니까?
A. 단방향 연결리스트와 양방향 연결리스트는 다른 자료구조이기 때문입니다.
즉, 다른 자료구조이기 때문에 다른 알고리즘으로서 표현됩니다.
(1-1) 단방향 연결리스트에서 노드 삭제
- 연결 리스트에서 노드를 삭제하는 연산은 꽤 직관적입니다.
노드 n이 주어지면 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정합니다.
리스트가 양방향 연결 리스트인 경우에는 n.next가 가리키는 노드를 갱신하여,
n.next.prev가 n.prev와 같도록 설정해야 합니다.
이 때, 유의할 점은 2가지입니다.
첫번째, 널 포인터 검사를 반드시 해야 합니다.
두번째, 필요하면 head와 tail 포인터도 갱신해야 합니다.
Q. 왜 노드 n이 주어지면 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정해야 하는가?
A. prev.next를 n.next와 같도록 설정한다는 것이 곧 노드 n을 삭제한다는 것을 의미하기 때문입니다.
Q. 왜 널 포인터 검사를 반드시 해야 하는가?
A.
Q. 왜 필요하면 head와 tail 포인터도 갱신해야 하는가?
A.
(1-2) Runner 기법
- Runner(부가 포인터라고도 합니다)는 연결리스트 문제에서 많이 활용되는 기법입니다.
연결 리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것입니다.
이 때, 한 포인터가 다른 포인터보다 앞서도록 합니다.
앞선 포인터가 따라오는 포인터보다 항상 지정된 갯수만큼을 앞서도록 할 수도 있고,
아니면 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있습니다.
Q. 포인터란 무엇인가?
A. 포인터는 변수의 메모리 주소를 담는 변수입니다.
변수의 값을 읽거나 변경하는 등, 변수에 적용 가능한 연산은 모두 포인터를 통해 할 수 있습니다.
Q. 왜 포인터와 같은 변수의 주소를 담는 변수가 필요합니까?
A. 포인터는 동적 메모리 할당, 많은 자료 구조, 그리고 큰 규모의 데이터를 핸들링하는데 필요합니다.
Q. 포인터는 왜 동적 메모리 할당, 큰 규모의 데이터를 핸들링하는데 필요합니까?
A.
Q. 왜 두 개의 포인터를 동시에 사용할 때, 한 포인터가 다른 포인터보다 앞서도록 합니까?
A.
Q. 왜 앞선 포인터가 따라오는 포인터보다 항상 지정된 갯수만큼을 앞서도록 하거나,
아니면 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정하는가?
A.
(1-3) 재귀 문제
- 연결리스트 관련 문제 가운데 상당수는 재귀 호출에 의존합니다.
연결리스트 문제를 푸는데 어려움을 겪고 있다면, 재귀적 접근법은 통할지 확인해 봐야 합니다.
하지만 재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n)만큼의 공간을 사용한다는
사실을 기억해야 합니다.
모든 재귀 알고리즘은 반복적 형태로도 구현될 수 있지만,
반복적 형태로 구현하면 한층 복잡해질 수 있습니다.
Q. 재귀 호출이란 무엇인가?
A. 재귀 호출이란 함수 내부에서 자기 자신을 또다시 호출하는 행위를 의미합니다.
Q. 왜 재귀 호출을 합니까?
A. 재귀 호출을 사용하면 복잡한 문제도 매우 간단하게 논리적으로 접근하여 표현할 수 있기 때문입니다.
Q. 왜 재귀 호출을 사용하면 복잡한 문제도 매우 간단하게 논리적으로 접근하여 표현할 수 있습니까?
A. 예를 들면, 다음과 같이 1부터 n까지의 합을 계산하는 함수를 재귀 호출로 구현할 수 있습니다.
int rSum(int n)
{ if (n == 1) // n이 1이면, 그냥 1을 반환함.
{ return 1;
}
return n + rSum(n-1); // n이 1이 아니면, n을 1부터 (n-1)까지의 합과 더한 값을 반환함.
}
Q. 왜 연결리스트 관련 문제 가운데 상당수는 재귀 호출에 의존하는가?
A. 연결 리스트는 차례로 연결된 노드를 표현해주는 자료구조인데,
이는 재귀 호출로 구현 가능하기 때문입니다.
Q. 왜 연결리스트 관련 문제는 재귀 호출로 구현 가능한가?
A. 예를 들어, 다음 코드는 C언어로 연결 리스트를 재귀 호출로서 구현한 것입니다.
void print_list2(node_t *from){
if (from == NULL)
return ;
printf("%d ", from-key);
print_list2(from->next);
}
연결리스트에서 전체 리스트에 속한 노드와 노드 간의 연결은 반복됩니다.
따라서 재귀 호출로 노드와 노드간의 연결을 반복적으로 구현할 수 있습니다.
Q. 왜 재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n)만큼의 공간을 사용하는가?
A.
Q. 왜 모든 재귀 알고리즘은 반복적 형태로도 구현될 수 있습니까?
A. 재귀 호출이란 본질적으로 특정한 함수의 실행이 반복되는 것입니다.
따라서 재귀 알고리즘은 for문이나 while문과 같은 반복적 형태로도 구현될 수 있습니다.
Q. 왜 모든 재귀 알고리즘은 반복적 형태로 구현하면 한층 복잡해질 수 있습니까?
A.
- 이 글의 내용은 '코딩 인터뷰 완전 분석'을 참조했습니다.
