항해 99 5주차를 끝내며

     알고리즘 4주 과정이 모두 끝나고, 드디어 주특기 주차에 들어섰다. Node.js에 대한 공부를 시작했고, 컴퓨터 공학적 지식을 쌓기 위한 스터디도 시작되었다. 파이썬만 써보았고, 비록 Javascript 문법에 대해서는 조금씩 알아보고는 있었지만 역시 실전에 들어가니 헷갈리는 것 투성이에 코드 읽는 것도 한세월이었다. 기본적인 함수들에서 return해주는 형식과 함수를 적어주어야 하는 위치, 프로퍼티라는 개념 등 여러가지 것들이 달랐는데, 적응을 위해서는 최대한 많은 코드를 읽어보고 작성해보는 것이 가장 좋을 것이라고 생각한다.

 

    알고리즘 마지막 주차에서 배운 주제는 바로 이진 탐색과 분할 정복, 그리고 최단 경로 문제였다. 최단 경로 문제는 다양한 유형의 문제가 존재했는데, 그 중에서 내가 학습했던 것은 다익스트라 알고리즘과 플루이드 워셜 알고리즘이었다. 다익스트라 알고리즘은 다익스트라라고 하는 몹시 유명한 컴퓨터 과학자에 의해 개발된 알고리즘으로, 노드와 간선, 그리고 가중치가 주어졌을 때 한 노드에서 부터 다른 모든 노드까지의 최단 거리를 구할 수 있는 알고리즘이다. 이 알고리즘은 다른 노드까지의 최단 거리를 지금까지 찾은 노드들 중에서 가장 가까운 노드에서 시작하여 찾아가며 최단 거리를 계속해서 갱신해주는 방식으로 작동한다. 이 '가장 가까운 노드에서 시작하여' 라는 부분때문에 매번 모든 노드에 대해서 가장 가까운 노드를 찾아주어야 하는 계산 과정이 필요해서 O n^2의 시간복잡도를 보이는 것처럼 보이나, heap 자료구조를 이용하여 도달 거리에 따른 최소힙을 만들어주면 O nlogn의 시간 복잡도를 끌어낼 수 있다. 다만, 최단 경로를 구하는 과정에서 그 자체만을 고려하기 때문에 문제에 제약조건이 주어진다면 이 부분을 잘 구현해야 하는 것 같다.

 

    플루이드 워셜 알고리즘은 다익스트라의 확장판 같은 느낌이다. 물론 문제에 접근하는 방식은 다르지만, 플루이드 워셜 알고리즘은 모든 노드로부터 다른 노드까지의 최단 거리를 구하는 것이다. N개의 노드가 존재한다면, N^2개의 최단거리를 구하는 것이라고 생각하면 이해가 빠를 것이다. 플루이드 워셜 알고리즘의 문제 접근 방식은, 어떤 노드로 부터 다른 노드까지의 최단 거리를 구함에 있어, 모든 노드를 경유하여 도달하는 경우를 모두 비교해보는 것이다. 예를들어 1번 노드로부터 n번 노드까지 간다고 했을 때, 2번 노드를 경유하는 최단 거리와, 3번 노드를 경유하는 최단 거리 등 n-1번 노드를 경유하는 최단 거리까지 모두를 비교하여 최단 거리를 구하는 방식이다. 이러한 접근 방식 때문에 플루이드 워셜 알고리즘은 O n^3의 시간복잡도를 가져 시간적으로 오래 걸릴 수 있다.

 

    이진 탐색은 아주 놀라운 탐색 방법이다. 이진 탐색은 O logn의 시간 복잡도를 가지는 아주 강력한 탐색 방법이지만, 정렬이 되어 있지 않은 상태에서는 사용할 수 없다는 제약조건이 있다. 정렬이 되어 있는 상태에서만 이진 탐색을 적용할 수 있는 이유는, 이진 탐색의 원리를 알면 바로 이해할 수 있다. 이진 탐색에서는 배열에서 중앙에 위치하는 값을 찾아서 내가 찾고자 하는 값과 비교한다. 여기서 정렬된 배열의 강력함이 비로소 진가를 발휘하는데, 정렬 된 배열의 경우에는 중앙에 위치하는 값과 내가 찾고자 하는 값을 비교하는 것만으로 탐색 범위를 절반으로 줄일 수 있다. 정렬되지 않은 경우라면 그저 해당 값은 중앙에는 없다 혹은 있다로 끝나는 비교가 정렬된 상태에서라면 더 작은 경우에는 왼쪽, 더 큰 경우라면 오른쪽에 위치한다는 정보를 도출한다. 즉, 정렬된 배열을 통해 찾을 때에는 해당 값과 비교하는 과정에서 단지 해당 값이 맞다 아니다를 넘어서 추가적인 정보를 얻을 수 있다는 것이다. 

 

    동적 계획법, 다른 말로는 분할 정복은 마치 고등학교에 다니던 시절 배웠던 점화식과 아주 유사한 문제 접근 방식이있다. 점화식은 n번째 항이 주어졌을 때, 그 다음에 올 항을 n번째 항으로 표현할 수 있다면 첫번째 항으로 모든 항의 정보를 알아낼 수 있다는 특징이 있다. 분할 정복도 이와 마찬가지의 문제 접근 방식인데, 대표적인 예시로는 피보나치 수열이 있다고 한다. 피보나치 수열의 특징은 자연수 n에 대해서 f(n)이 n번째 피보나치 수를 의미한다고 할 때, f(n+2) = f(n+1) + f(n)을 만족한다는 것이다. 즉, f(n)을 알고 있으면, f(n+1)을 도출할 수 있고, 연쇄적으로 f(n+2)를 도출할 수 있는 것이다. 이를 위해서 f(n)을 저장해 줄 배열을 만들고, 인덱스를 통해 값을 뽑아서 쓰면서 f(n+1)을 추가해주는 방식으로 임의의 순서의 피보나치 수를 구할 수 있다. 다음은 피보나치 수열과 매우 유사한 로직을 통해 접근할 수 있는 문제와 스스로 적어본 그 해답이다.

Climbing Stairs - LeetCode

class Solution:
    def climbStairs(self, n: int) -> int:
        ans = [1, 1]
        par = 1
        while par < n:
            ans.append(sum(ans[-2:]))
            par += 1
        return ans[-1]

위 코드는 위에서 기술하였듯 하나의 배열을 통해 f(n)을 저장해주는데, f(n)을 도출해낼 때 해당 배열에 있는 숫자를 뽑아서 이용하는 방식을 이용한다. 문제를 작은 문제들로 쪼개서 하나씩 하나씩 쌓아간다는 느낌을 받을 수 있는데, 이래서 분할 정복이라는 이름으로 부르는 것 같다.