[정글] 셋,넷,다섯째주. 다양한 자료구조와 탐색기법
스택, 큐, 힙, 깊이우선탐색, 너비우선탐색, 동적프로그래밍, 그리디
지난 주까지 다룬 알고리즘 문제들에서는 해결해야 할 과제가 단순하게 주어지고 정답을 찾기 위해서는 배열에 담은 데이터를 완전 탐색하거나 정렬 및 이분탐색을 하면 되었었다. 그러나 이번 주 부터는 해결해야 할 과제가 복잡하게 주어지고, 정답을 찾기 위해서는 데이터를 특정한 자료구조에 담아 탐색하거나, 배열에 담더라도 시간복잡도나 공간복잡도를 최적화해서 탐색해야 했다.
스택, 큐
자료구조에는 정수, 실수, 문자 등의 하나의 데이터로 이루어진 단순 구조도 있지만, 두개 이상의 데이터들이 논리적인 관계로 저장되어있는 복합구조도 있다. 복합구조는 1:1 관계인 선형구조와 1:N 또는 N:N 관계인 비선형구조, 그리고 파일구조로 나누어진다.
선형구조에는 순차리스트, 연결리스트, 스택, 큐, 덱 등이 있다. 선형구조의 데이터들은 순서를 가지고 저장되는데, 순차리스트에서는 논리적인 순서와 물리적인 저장순서가 일치하지만 연결리스트에서는 물리적으로 흩어져서 저장된 데이터들이 논리적인 순서관계를 맺는다.
비선형구조에는 트리와 그래프가 있다. 다른 자료구조가 더 있는지는 모르겠지만 내가 공부한 범위 내에서는 이 두 개의 자료구조만 존재한다. 트리와 그래프에서 각 노드들은 논리적인 순서를 갖지 않고, 서로 계층구조나 망구조로 얽혀있다.
스택과 큐는 선형자료구조의 일종이다. 리스트와 다른 점은 데이터를 삽입하고 꺼내는 위치가 정해져있다는 제약이 있다는 점이고, 이 제약 덕분에 삽입과 삭제에 걸리는 시간복잡도가 O(1)로 매우 짧다. 하지만 탐색은 배열과 마찬가지로 Index를 1부터 N까지 순차적으로 방문하며 진행되므로 시간복잡도는 O(N)이다.
트리, 힙, 우선순위 큐
비선형 자료구조의 일종인 트리는, 높이(루트부터 가장 먼 리프까지의 거리), 레벨(각 노드가 속한 층수)이라는 키워드를 가지며, 트리의 연산을 단순화하기 위해 각 노드가 자식을 최대 두개까지만 갖도록 제약사항을 둔 구조를 이진 트리라고 한다. 트리라고 하면 거의 이진 트리를 가리킨다. 이진 트리는 레벨과 노드 수의 관계에 따라 포화 이진 트리, 완전 이진 트리, 편향 이진 트리 등으로 나뉜다.
트리는 다양한 자료구조로 변형되고 확장된다. 가령, 힙은 완전 이진 트리를 기반으로 노드의 대소관계 정의가 추가된 자료구조이다. 힙에서는 각 노드의 값이 해당 노드의 왼쪽 자식 노드나 오른쪽 자식 노드는 루트보다 작아야 하며, 두 자식 노드 서로간의 대소관계는 규정되지 않는 특징을 갖는다. 바로 이러한 부모-자식 간의 대소관계 때문에 힙은 우선순위큐에 활용될 수 있다. 우선순위큐는 큐의 일종으로, 우선순위에 따른 순서에 의해 자료를 꺼내와야 하는 제약사항을 갖는다. 이 '우선순위'가 힙의 각 노드가 가진 '값'에 대응된다.
최소힙 혹은 최대힙에서는 삽입, 삭제연산을 할 수 있고 일반적인 힙에서 삽입과 삭제연산의 시간복잡도는 O(logN)이다. 힙 자료구조는 최소값 혹은 최대값을 빠르게 꺼내오기 위해서 쓰인다. 힙을 활용하여 정렬에 활용할 수도 있으며, N개의 데이터를 힙정렬하는 데 걸리는 시간복잡도는 O(NLogN)이다.
python에서 제공하는 heapq 모듈에서 제공하는 heapify연산은 원소가 들어있는 리스트를 힙정렬하여 힙으로 바꾸어주는 연산이며, O(N) 시간복잡도를 갖는다. 힙에 원소를 하나씩 추가하는 heappush연산은 O(logN)의 시간복잡도를 가지므로, n개의 원소를 추가하면 걸리는 시간복잡도는 O(NlogN)이 된다. 따라서 이론적으로 N개의 원소들로 힙을 구현할 때는 O(N)으로 리스트에 N개의 원소들을 추가(append)하고 O(N)으로 heapify 하는 것이 하나씩 heappush하는 것(O(NlogN))보다 이론상 효율적이다.
이진 트리는 이진 탐색 트리로도 발전시킬 수 있다. 힙은 이진 탐색 트리와 유사하면서도 다른데, 각각의 노드를 루트로 할때 왼쪽 서브트리는 루트보다 작아야 하고 , 오른쪽 서브트리는 루트보다 커야 하는 이진탐색트리와 구분된다. 이진 탐색 트리의 데이터에 대해서는 탐색, 삽입, 삭제 연산을 할 수 있고, 세 연산의 시간복잡도는 최선의 경우 O(logN), 최악의 경우 O(N)이다. 이 최악의 경우는 트리의 노드 개수가 한쪽으로 치우치는 경우에 발생하며 이를 방지하기 위해 노드를 회전시키면서 균형을 맞춘 균형 이진 탐색 트리, 레드 블랙 트리 등이 존재하며 이들은 최악의 경우에도 O(logN)안에 탐색, 삽입, 삭제 연산을 수행한다.
https://github.com/yeonwooz/CS-study/blob/main/5_data-structure/5.1_complexity/5.1.3_time-complexity그래프, 깊이우선탐색, 너비우선탐색
비선형 자료구조의 일종인 그래프에서는 정점(vertex)들이 서로 다:다 관계를 맺으며 간선(edge)으로 연결된다. 트리도 그래프가 될 수 있다.
간선의 연결관계를 탐색하는 방법은 깊이우선탐색과 너비우선탐색으로 나뉜다. 깊이우선탐색은 각 노드를 기준으로 갈 수 있는 모든 정점을 재귀적으로 탐색한 후 되돌아나오며 경로의 수를 체크하는 탐색기법이다. 너비우선탐색은 각 정점을 기준으로 인접한 정점들을 한 레벨씩 탐색하며 내려가는 기법이다.
동적 프로그래밍, 그리디
앞서 다양한 자료구조를 활용하는 알고리즘 기법들을 다루었다면, 동적 프로그래밍과 그리디는 어떤 자료구조에서든지 데이터들을 탐색할 수 있는 모든 경로를 최대한 효율적으로 파악하고 그중 최적해를 찾는 기법이다. 일반적인 방법으로 모든 경로를 탐색한다면 시간적, 공간적 부하가 발생한다. 동적 프로그래밍은 반복되는 연산을 미리 메모이제이션해두고 재활용함으로써 부하를 최소화하고 그리디는 불필요한 연산을 발생하지 않는 최선의 옵션을 단계적으로 선택해나감으로써 부하를 줄인다.
Photo by La-Rel Easter on Unsplash
