-
알고리즘
- 알고리즘은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것 입니다. - 출처: 위키백과
- 짧게 줄이면, 어떤 종류의 문제를 푸는 방법을 공식으로 정해놓은 것이라고 할 수 있습니다. 예를 들어서 2차방정식을 풀기 위해서 근의 공식을 사용한다면, '근의 공식 알고리즘으로 이차방정식을 풀 수 있다' 라고 할 수 있는 것입니다.
- 알고리즘의 조건에는 입력, 출력, 명확성, 유한성, 효율성이 있습니다. 이 5가지 조건 중 효율성을 극대화하기 위해서 문제에 맞는 알고리즘 설계 기법이 필요합니다.
알고리즘 설계 기법
- 알고리즘 설계 기법은 어떤 문제를 해결하는 과정에서 해당 문제의 답을 효과적으로 찾아가기 위한 전략과 접근 방식을 제시합니다.
- 문제를 풀 때 어떤 알고리즘 설계 기법을 쓰는지에 따라 효율성이 막대하게 차이납니다. 이 효율성은 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)라는 척도로 판단할 수 있는데, 이 내용은 추후에 다루겠습니다.
- 모든 문제에서 우수한 알고리즘 설계 기법은 없습니다. 문제의 성질과 조건에 따라 알맞는 알고리즘 설계 기법을 선택해야하며, 그러기 위해서 어떠한 알고리즘 설계 기법이 있는지 알아야 합니다.
- 알고리즘 설계기법을 읽을 때, 그냥 알고리즘 이름을 읽을 때와 마찬가지로 OO 알고리즘 설계 기법이라고 부르지 않고 OO 알고리즘이라고 부릅니다. 예를 들어 Brute Force의 경우 Brute Force 알고리즘 설계기법 이라고 부르지 않고 Brute Force 알고리즘 까지만으로 부릅니다.
- 하지만 알고리즘과 알고리즘 설계 기법의 차이는 알아야 합니다!
알고리즘 설계 기법의 종류
- Brute Force Algorithm
- Brute(무식한) + Force(힘) + 알고리즘, 즉 무식한 알고리즘입니다.
- 조금 고급진 말로 완전탐색 알고리즘이라고 합니다. 단어에서 알 수 있듯이 모든 경우의 수를 탐색해서 정답을 도출해 내는 알고리즘 설계 기법입니다.
- 완전 탐색 알고리즘에서 알 수 있듯, 탐색 알고리즘에서 주로 사용됩니다.
- 대표적인 알고리즘: 깊이 우선 탐색(DFS, Depth First Search), 너비 우선 탐색(BFS, Breadth First Search)
- Backtracking Algorithm
- Backtracking, 한국어로는 퇴각 검색이라고 부릅니다. 퇴각이라는 단어에서 알 수 있듯, 탐색을 하는 과정에서 어떤 방향이 유망하지 않으면, 즉 답이 될 가능성이 없으면 탐색을 하지 않는다는 것입니다. 즉 완전 탐색 알고리즘에서 가지치기를 하면서 효율성을 높이는 방법입니다.
- 예를 들어서 가위바위보를 하는데 상대가 주먹을 낸다고 가정을 해보겠습니다. 완전탐색을 한다면, 가위, 바위, 보를 모두 내어보고, 이기는지 지는지 비기는지 결과를 확인하고 비로소 이기는 방법을 압니다. (한국말로 똥인지 된장인지 먹어봐야 한다고 하죠). 하지만 Backtracking알고리즘과 함께 사용하는 경우는 상대가 주먹을 냈을 때, 주먹이나 가위를 내면 이길 가능성이 없기 때문에 두 경우는 탐색하지 않고 보를 내는 상황만 탐색한다는 것입니다.
- Greedy Algorithm
- Greedy(탐욕) 알고리즘은 탐색을 하는 상황에서 상황마다 가장 좋아보이는 해결책을 선택하는 알고리즘 설계 기법입니다. 여기서 키포인트는 '좋아보이는'입니다. 이 해가 최선책이라는 보장이 되지 않습니다.
- 예를 들어보겠습니다. 산 정상까지 올라가야하는데, 당신의 앞에 케이블카와 오르막길이 있습니다.
- 케이블카를 타고 올라가서 내려주는 곳에서부터는 가파른 오르막길을 걸어 올라가야합니다.
- 오르막길은 조금만 걸어가면 엘리베이터가 나와서 정상까지 곧장 올려보내줍니다.
- 뒤의 길까지 본다면 오르막길로 조금 고생을 하고 엘리베이터를 타는 것이 더 쉽습니다. 하지만 탐욕 알고리즘은 상황마다 가장 좋아보이는 선택을 하기 때문에 당장 앞의 케이블카와 오르막길 중 케이블카를 선택하게 됩니다.
- 대표적인 알고리즘: 최소비용 신장트리(MST, Minimum Spanning Tree)를 구하는 알고리즘(Kruskal Algorithm, Prim Algorithm)
- Dynamic Programming 알고리즘 설계기법
- Dynamic(동적) Programming은 Memoization 기법을 사용하는 알고리즘 설계기법입니다.
- Memoization: 한 단계씩 계산을 해나갈 때 그전까지 계산한 내용을 저장해놓고 추후 반복 계산을 막는 방식입니다. 예를 들어 5라는 숫자를 1, 2, 3, 4, ... 10번 더한 결과값을 구해야 할 때, 10번 더할 때 5+5+5+5...+5를 하는 것이 아니라, 5를 9번 더한 결과물인 45를 저장해놓고, 5를 9번 더하면 45니까 한번만 더 더해주면 10번 더한것이니 45+5 = 50이다. 라고 구하는 방식도 Memoization이라고 볼 수 있겠습니다.
- 완전탐색을 하는 경우 이중 반복을 통해 O(N^2)의 시간복잡도가 소요될 때, 적절한 문제에서 Dynamic Programming을 사용하는 경우 O(N)으로 줄어들어 해결할 수 있는 경우가 흔히 생깁니다.
- 대표적인 Dynamic Programming 문제: 최장 공통 부분 수열(LCS)문제, 0/1 배낭 문제
- Divide and Conquer
- Divide(분할) and Conquer(정복) 기법은 큰 문제를 작은 문제로 나눠서 푸는 하향식 접근 방식입니다.
- Divide(분할)을 통해서 해결하기 쉬운 작은 문제로 나눈 후 Conquer(정복)한 후 Merge(병합)하는 과정을 통해서 큰 문제를 해결하는 방식입니다.
- 간단하게 예를 들어보면 토너먼트 방식도 분할 정복 기법이라고 볼 수 있습니다. 16팀 중 1등을 가리기 위해서 리그전 형식의 경기를 한다면 16*15/2 = 120 경기를 진행해야 합니다. 하지만 16팀중 1등을 가리기위해 8팀 8팀으로 쪼개고(Divide), 8팀을 4팀, 4팀으로 쪼개고(Divide), 4팀을 2팀, 2팀으로 쪼갠 후(Divide), 2팀끼리 16강전을 치러서 승자를 구합니다(Conquer). 첫 16강전 승자와 두번째 16강전 승자를 모아서 8강전을 만들고(Merge) 8강전의 승자를 구합니다(Conquer). 이러한 방식으로 8강전, 4강전, 결승전을 통해서 우승자를 뽑으면 15경기로 우승자를 가릴 수 있습니다.
- 보통의 분할 정복 기법은 recursion(재귀)을 사용합니다.
- 대표적인 알고리즘: Quick Sort, Merge Sort, Binary Search
마치며
- 위에서도 말했듯, 완벽한, 항상 적용되는, 가장 빠른 알고리즘 설계기법이란건 없습니다. 따라서 문제를 풀기 전에 유심히 생각해보고 문제를 풀기 시작하는 것, 그리고 문제들을 많이 경험해서 감을 익히는 것이 알고리즘 문제를 풀 때 적합한 알고리즘 설계기법을 고르고, 해당 설계기법에 속하는 알고리즘을 고르는데에 도움이 될 것입니다.