항해99 Chapter #2 - 2주차(자료구조 - 연결 리스트, 스택과 큐, 해시 테이블) 회고록

들어가며

매주 금요일마다 새롭게 배정된 팀에서 일정을 진행하느라, 이번주를 항해 3주차로 착각하였다. 알고리즘 주차는 총 4주 동안 진행되는데, 이번주는 기본 자료구조인 문자열 및 배열 조작, 연결 리스트, 스택, 큐, 해시 테이블에 대해서 공부하였다. 학사 과정 동안 얕게 공부한(직장생활과 병행하느라 제대로 된 공부는 하지 못했다) 내용이지만, 직접 구현해보면서, 관련된 알고리즘 문제를 푸는 시간이 굉장히 유익하게 느껴졌다. 따라서, 알고리즘 주차의 회고록에는 개념을 정리하기 보다는(조금만 검색해보면 관련 영상과 글이 넘쳐난다) 알고리즘 문제를 풀면서 또는 개념을 공부하면서 느낀점이나 내가 이해한 내용 정도를 기록하려고 한다.

공부한 내용 정리

알고리즘 문제를 제대로 해결하려면 반드시 자료구조에 대해서 알아야 한다. 간혹, 시간 복잡도나 공간 복잡도를 만족해야 하는 알고리즘 문제가 있는데, 이 경우 여러 자료구조의 특성을 이용하여 문제를 해결해야 하기 때문이다.

시간 복잡도와 공간 복잡도

이를 쉽게 설명하자면 시간 복잡도는 '입력값의 크기에 따라 문제를 해결하는데 소요되는 시간', 공간 복잡도는 '입력값의 크기에 따라 문제를 해결하는데 소요되는 메모리 용량'이라고 할 수 있다. 이는 점근 표기법으로 나타내며 그 중에서도 최악의 경우를 가정한 빅 오(Big-O) 표기법으로 나타낸다. 예를 들어, 시간 복잡도가 O(N)인 경우 최악의 입력값 N이 주어질 때 어떠한 알고리즘을 수행하기 위해 소요되는 시간이라고 할 수 있다. 다른 표기법으로는 빅 오메가(Big-Ω), 빅 세타(Big-θ) 표기법이 있으며 이는 각각 주어진 입력값이 최선인 경우와 평균인 경우를 가정하였을 때 사용된다.

즉, 자료구조의 연산에 따른 시간 복잡도를 알아야 상황에 맞게 적절한 자료구조를 사용할 수 있으므로 알고리즘 문제를 제대로 풀기 위해서는 자료구조에 대한 이해가 반드시 필요한 것 같다.

연결 리스트

연결 리스트(Linked List)에 대한 문제를 풀면서 정말 많은 그림을 그려보았던 것 같다. 그만큼 '연결'이라는 자체가 추상적인 사고로 이해해야 하기 때문인 것 같다. 즉, 각각의 노드가 어떻게 연결되어 있고, 이를 역순 정렬 또는 병합시키는 과정이 어떻게 되는지를 하나의 장면으로 떠올릴 수 있어야 하는 것 같다. LeetCode에는 이 개념을 다루는 두 개의 문제가 있는데 각각 다음과 같다.

LeetCode - 021. Merge Two Sorted List

• 문제 : https://leetcode.com/problems/merge-two-sorted-lists/
• 풀이 : https://choewy.tistory.com/126

항해99에서 매일 오후 8시에 진행되는 과제톡에서 내가 발표했던 문제이다. 문제를 보면 알 수 있겠지만, 개념을 이해하기 위한 용도로 이보다 더 완벽한 문제가 있을까라는 생각이 든다.

LeetCode - 206. Reverse Linked List

• 문제 : https://leetcode.com/problems/reverse-linked-list/
• 풀이 : https://choewy.tistory.com/127

이해하는데 한참 걸린 문제이다. 일일이 포인트를 잡아서 디버깅을 해보고, 콘솔로 값을 출력해보면서 이해하기는 했지만, 다시 풀어보라고 하면 아직도 한참 걸릴 것 같다. 따로 시간을 내어 역순으로 바꾸는 과정이 어떻게 되는지 정확하기 이해할 필요가 있다고 생각한다.

아마도 연결 리스트의 역순 정렬이나 병합을 자유자재로 구현할 수 있으면 뒤에서 배울 대부분의 내용은 쉽게 이해할 수 있을 듯하다.

스택과 큐

예전에 따로 스택(Stack)과 큐(Queue)에 대해서 공부한 적이 있어서 그런지 크게 어려움을 느끼진 못했다. 알고리즘 문제를 풀다보면 반드시 큐를 통해서 해결해야 하는 경우가 있는데, 이 경우 파이썬 내장 모듈인 deque를 사용할 수 있다.

자료 구조(Data Structure)의 스택(Stack) 개념 정리

• 개념정리 : https://choewy.tistory.com/100
• 관련문제 : https://leetcode.com/problems/implement-queue-using-stacks/
• 문제풀이 : https://choewy.tistory.com/133

파이썬의 자료형 중 리스트가 곧 스택이라고 할 수 있을 정도로 이해하기 쉽다. 다만, 고정길이 스택과 같이 포인터를 사용하는 경우 약간 헷갈릴 수도 있는데, 위에서 언급했던 연결 리스트의 역순 정렬과 병합 모두 포인터를 사용하므로 연결 리스트를 자유롭게 구현할 수 있다면 크게 어렵지 않을 것으로 생각한다.

자료 구조(Data Structure)의 큐(Queue) 개념 정리

• 개념정리 : https://choewy.tistory.com/100
• 관련문제 : https://leetcode.com/problems/design-circular-queue
• 문제풀이 : https://choewy.tistory.com/134

파이썬의 리스트를 통해 큐를 구현하는 경우 시간 복잡도에서 문제가 있을 수 있다. 그 이유는 큐와 스택은 서로 다른 방식으로 연산이 수행되기 때문인데, 이에 대해 자세히 알고 싶다면 구글 검색창에 '리스트 연산 시간 복잡도'와 '큐 연산 시간 복잡도'를 검색해보면 된다. 추가적으로 위의 링크에서는 링 버퍼(Ring Buffer)를 구현하였다.

나는 알고리즘 문제를 풀 때 되도록이면 직접 구현하는 방법으로 접근하였다. 예를 들어, 파이썬의 리스트를 역순으로 바꾸고, 뒤에서부터 pop을 하면 Queue의 dequeue와 같이 동작할 수 있고, 리스트를 병합(['new'] + ['old']) 하면 enqueue와 동작할 수 있다.

참고로 파이썬 리스트의 병합은 시간 복잡도가 O(n + m)로 stack의 push 보다는 느리지만 알고리즘 문제를 풀 때에는 크게 영향을 주지 않고, pop()은 맨 뒤에 요소를 빼내는 것이므로 시간 복잡도는 항상 O(1)이다.

해시 테이블

알고리즘 문제를 풀다보면 해시 테이블(또는 해시맵)을 미리 만들어놓는 방식으로 해결해야 할 때가 있다. 해시 테이블은 파이썬의 딕셔너리라고 할 수 있으며, 이 또한 예전에 따로 공부한 적이 있어서 그런지 크게 어려움을 느끼진 못했다.

검색 알고리즘(Search Algorithm)의 해시법(체인법과 오픈 주소법) 개념 정리

• 개념정리 : https://choewy.tistory.com/99
• 관련문제 : https://leetcode.com/problems/longest-palindrome
• 문제풀이 : https://choewy.tistory.com/129

체인법의 경우 동작 방식이 딕셔너리와 JSON과 같이 직관적({ key: { key: { key: value }}})이기 때문에 이해하기 쉬운 듯하다. 오픈 주소법은 회고록을 작성하는 과정에서 다시 한 번 살펴보았는데, 언제 사용하면 좋은지에 대해 궁금증이 생겼다. 해시 충돌이 발생하였을 때 체인법의 경우 연결 리스트 방식으로 새로운 값을 연결하는 방식이라면, 오픈 주소법은 재해시하는 과정을 통해 빈 버킷에 값을 저장한다고 이해하고 있다. 그렇다면 저장할 수 있는 공간이 꽉 찬 경우라면 재해시를 하는게 과연 의미가 있을까?라는 의문이 들었다. 이 내용은 충분히 알아본 후 정리해서 따로 포스팅하도록 하겠다.

마치며

한 주 동안 공부한 내용을 정말 간단하게 정리해보았다. 알고리즘 1주차에는 이미 알고있는 내용이 있어서 그런지 비교적 큰 어려움은 느끼지 못했다. 그런데! 다음주 회고록에서 언급하겠지만 DFS, BFS를 공부할 때에는 러닝커브가 급격하게 올라간 느낌이 든다. BFS의 경우 반복문과 큐를 사용하므로 어느정도 극복할 수 있었지만, DFS의 경우 재귀(recursive) 또는 반복(iterative)으로 구현해야 하는데, 이 중에서 재귀함수가 끝판왕인 것 같다. 지금은 약 2일 정도 연습한 상태라 몇몇 DFS 문제를 풀 수 있는 정도이긴 하지만, 머릿속으로 완벽하게 그릴 수 있는 단계로 성장하기까지는 더 많은 연습이 필요할 것 같다.