항해 99 2주차를 끝내며

    사전 프로젝트를 마치고, 알고리즘에 대해 공부하는 주차에 들어섰다.

 

    파이썬을 이용해서 공부를 시작했는데, 아무래도 나는 파이썬을 최초로 컴퓨터 언어를 접한 만큼 더 익숙한 상태였지만, 자바스크립트나 자바를 최초로 접한 사람들, 그리고 컴퓨터 언어를 이전에 접해보지 못했던 사람들도 있었던, 아니 꽤나 많았던만큼 적응에 진통이 있었던 것 같다.

 

    수업은 문자열을 다루는 기본적인 방법에서부터 시작하여, 리스트와 연결리스트, 스택, 큐, 해시 테이블, 그리고 DFS와 BFS까지 진행된 상태이다. 스파트라 코딩클럽의 입장에서도 알고리즘과 관련된 교육을 진행하는 것은 처음인지 꽤나 서툴렀던 것 같다. 강의 계획은 잡혀 있었지만, 그 강의 계획에 따라서 수업이 진행되지 못했고, 시간 분배에 있어서도 만족스럽지 못했다. 그러나, 그 후 피드백을 통해 빠르게 강의의 질을 높이려 노력해주었다.

 

<연결 리스트>

    파이썬에서 사용하는 리스틑 고정적인 형태의 배열로 그 길이가 동적으로 움직일 수는 있으나 그 구조 자체는 정적인 형태이다. 따라서, 배열의 길이가 늘어나기 위해서는 새로운, 더 긴 길이를 가진 배열을 생성하여 이전 배열에 담겨있는 정보를 복사하는 작업이 필요하다. 배열의 길이를 늘여주는 정도는 각 언어마다 어느정도의 차이를 보이며, 파이썬의 경우 1.125배 정도로 배열의 길이를 연장시킨다.

 

    연결리스트는 이와는 다르게 각 값을 가진 일부를 node라고 했을 때, 각 node에 다음 node의 위치에 해당하는 정보를 함께 저장하는 방식으로 데이터를 저장하는 자료 구조이다. 해당 node의 주소를 가지고 있기 때문에 고정된 위치에 다른 node와 함께 저장할 필요가 없고, 따라서 길이를 저장공간이 허용하는 한 제한없이 늘일 수 있다는 장점이 있다. 그러나 이를 위해서 연결리스트는 indexing에 대한 상수시간을 희생하였다. 고정적인 형태의 배열의 경우, 배열의 데이터타입이 정해져 있어 O(1)의 시간에 index를 통해 해당 자료에 접근할 수 있다. 반대로 연결리스트는 head부터 시작하여 해당 index가 나올 때까지 자료를 탐색하며 하나 하나의 node를 읽어들여야 하기 때문에 O(k)의 시간이 소요된다.

    추가로, 짐작건데 주소값을 저장하기 위한 공간이 더 필요하므로 공간복잡도 또한 증가했을 것으로 보인다.

 

<Stack & Queue>

    스택과 큐는 상호 유사한 부분이 매우 많고, 시간 복잡도와 공간 복잡도의 차이는 다소 존재할 수 있으나 이를 활용한 연산 자체는 파이썬이 기본적으로 지원하는 list 형태로 모두 가능하다. 그럼에도 불구하고 이런 자료구조 자체를 이해하는 것은 중요하다고 할 수 있는데, 단적으로도 코드테스트 문제를 풂에 있어서도 문제의 조건에 맞는 방식으로 코드를 구현하려면 이런 이해를 바탕으로 해야 하기 때문이다. 

 

    Stack은 후입선출이라는 말로 간단하게 요약할 수 있다. 조금 더 구체적으로 비유하자면 쌓여있는 접시를 상상해보면 좋을 것이다. 접시를 새로 올려놓을 때에는 항상 이전에 있던 접시 위에 올려두고, 접시를 꺼내갈 때에는 가장 위의 접시를 먼저 가지고 간다. 이런 것은 대게 push와 pop으로 구현되고, 파이썬의 list는 append와 pop을 지원하며 두 방법 모두 O(1)의 상수시간이 소요되어 stack으로의 기능을 훌륭하게 수행할 수 있다.

 

    Queue의 경우는 선입선출의 구조를 가지고 있다. 마찬가지로 더 구체적으로 비유를 하자면, 일차선 터널을 지나가는 일련의 자동차 무리를 생각하면 좋을 것 같다. 일차선 터널이므로 내부에서 뒤의 차가 앞의 차를 추월하는 일은 없을 것이다. 자동차가 터널에 진입하는 것을 자료가 입력된 것으로, 터널에서 나가는 것을 자료가 나가는 것으로 생각하면 된다. 먼저 들어온 자동차는 그 뒤에 들어온 자동차보다 더 먼저 나가게 되고, 상대적으로 뒤에 있는 자동차는 앞의 자동차가 모두 나가야 터널을 나갈 수 있게 된다. 

 

    파이썬의 경우, list에서 가장 첫번째 원소를 제거하는 pop(0)은 O(n)의 시간이 소요되는 만큼, list를 직접적으로 이용하는 것은 가능은 하지만 권장되지 않는다. 내장 모듈 중 하나인 collections를 import하면 deque를 이용할 수 있는데, deque는 double ended queue라는 뜻으로 popleft() 메서드를 지원하여 상수시간에 가장 왼쪽의 원소를 제거할 수 있다.

 

<Hash table>

    list에서 값을 이용해 index를 찾으려 할 경우에는 O(n)의 시간이 소요된다. 각각의 요소에 대해서 값을 비교해야 하기 때문에 그런 것이다. 이런 경우에 O(1)의 시간을 소요할 수 있도록 만든 자료구조가 바로 hash table이다. 파이썬에서는 dictionary의 형태로 구현되어 있는데, 이러한 hash table은 이름에서 짐작할 수 있듯 hash 함수를 이용하여 구현된다. hash함수란 hash table을 이용하기 위한 정도로만 단순하게 설명하자면, 임의의 값을 입력했을 때 고정된 길이의 값으로 되돌려주는 함수이다. 이런 과정을 통해 모든 입력값을 고정된 길이로 고정할 수 있다. 바로 이 점을 이용해 O(1)의 시간소요만으로 key를 통해 value를 찾을 수 있는 것이다.

 

    다만, 5비트에는 2**5 가지 정보만 담을 수 있고, 2**6 가지 정보를 담으려고 하면 중복되는 경우가 발생한다는 것은 매우 당연하다. 비둘기집 원리에 의해 2**5번째 정보가 담긴 후의 정보는 무조건 중복될 수밖에 없기 때문이다. hash table의 경우에도 이런 문제에 직면하게 된다. 임의의 서로 다른 두 값을 hash함수에 입력했을 때 서로 같은 값이 나올 수 있는 것이다. 이런 문제를 피하는 방법으로는 임의의 입력값들에 대해 최대한 분산된 결과값을 출력해주는 좋은 hash함수를 사용하는 방법이 있다. 

 

    이러한 문제가 발생할 경우 hash table은 이를 해결하기 위해 2가지 방법을 선택적으로 사용하는데, close addressing과 chaining이 그것이다. chaining은 해당 hash에 이미 값이 들어있을 경우, linked list를 이용해 마치 사슬을 연장하듯 자료를 더 저장하는 기법이고, close addressing은 해당 hash 근처에 비어있는 hash를 찾아 그곳에 정보를 저장하는 식이다.

 

    Hash table의 경우, 해당 table에 빈 공간과 가득 찬 공간의 비율을 load율을 통해 나타낸다. 각각의 언어는 load율에 따라서 hash table을 확장시키는데 임계가 되는 비율은 다소간의 차이가 있다. close addressing은 hash table에서 각 hash들이 clustering하는 문제가 있고, chaing의 경우에는 key를 이용한 탐색 시간이 점점 더 길어지는 문제가 존재한다. 

 

 

DFS, BFS

    DFS와 BFS의 대상이 되는 그래프는 행렬이나 edge에 대한 정보를 포함하는 list 혹은 dictionary의 형태로 입력된다. 행렬로 표현되는 방식은 고등학교 수학에서 행렬에 대해 배울 때 배우는 방식과 같아 각 node에 대해 edge가 존재하는 adjacent node를 표시해주는 방식이다. DFS는 stack을 통한 while문이나 재귀함수로, BFS는 queue를 이용한 while문으로 주로 구현된다.

 

    나는 최초 알고리즘 문제 풀이에 도전했을 당시, 이런 자료구조나 그래프 탐색과 같은 부분에 대한 이해도가 전혀 없었다. 그래서 그래프나 기하학, 동적 프로그래밍 등의 문제는 거의 포기하고 지나갔었는데, 이런 배움을 통해 풀리지 않던 그래프 문제를 풀어나가는 경험은 아주 재미있는 경험이었고, 이러한 배움에 감사한다.

 

    DFS와 BFS를 훌륭하게 설명해주는 강의를 Youtube에서 발견하였다. 단순하고 직관적인 그림을 통해 DFS와 BFS를 설명해주는 영상으로, 빠르게 이해가 가능하다.

<https://www.youtube.com/watch?v=_hxFgg7TLZQ&ab_channel=%EC%97%94%EC%A7%80%EB%8B%88%EC%96%B4%EB%8C%80%ED%95%9C%EB%AF%BC%EA%B5%AD>

 

 

문제를 풀다보니, KMP algoritm에 대해 검색을 하게 되었다. 문자열을 검색할 때 O(n+m)의 시간에 검색이 가능하도록 고안된 알고리즘으로, 문자열을 다루는 문제를 풀 때 많은 도움이 될 것 같다. 추후 충분히 이해를 하고 나서 포스팅하고 싶다.