알고리즘에 대한 책들을 보면 대부분이
소팅 문제, 그래프 문제, Dynamic programming, Greedy algorithm등이 나온다.
뭐 기타로 Genetic algorithm이나 Machine learning등에 관련된 내용들도 있기도 하지만
기본적으로는 소팅,그래프의 문제가 기본이라고 할수가 있을 것이다.
어떤 문제를 풀려면 기존에 나와 있는 알고리즘의 어떤 문제에 속하느지를 뭔져 파악하고 그 문제로 변환해보는게 중요하다. 대부분의 문제는 다른 문제로 변환이 가능하다. 이것이 NP문제에 대한 수학/알고리즘 연구자들의 로망을 생겨나게 만들기도 하는데, 어떤 NP문제를 풀면 모든 NP문제를 풀수 있다는 명제가 나오게 되는 이유이다.
예를 들어
무수히 많은 Random한 정수의 입력 값에 대해서(중복되어서 들어 올수도 있다) 중복된 정수를 찾는 문제를 보자.
해법은 들어온 값을 저장하고 이 값에 대한 Count값을 저장하여 이 Count값이 2이상이면 중복된 정수라고 생각할수 있다.
이에 대한 해법으로 linked list를 생각해 보면
정수1|Count -> 정수2|Count -> 정수 3|Count 로 들어온 정수값에 대해서 linked list를 운행하면서 해당 값이 기존에 있으면 그 노드의 Count값을 하나 증가시키고 없으면 마지막이나 처음에 노드를 추가한다. 이 linked list를 좀더 효율적인 구조로 바꾸라는 질문이 주어지면 이는 소팅 문제로 변환이 된다.
즉, 기존에 들어온 정수에 대한 저장 하는 방법과 현재 정수값이 이 저장된 곳에 있는지(기존에 이미 들어왔는지)를 찾는 문제가 생기는데, 이 찾는 문제가 바로 소팅 문제가 되는 것이다.
상기 문제에 대해서는 우선 저장을 하는 linked list에 저장할때
1. 다음에 들어오는 값이 linked list의 처음 값보다 작으면 맨 처음에 노드를 추가하고, 마지막 값보다 크면 맨 마지막에 노드를 추가한다.
2. 1에 해당 없으면 linked list를 head부터 tail까지 운행하면서 Node K의 값이 들어온 값과 같으면 Node K의 count를 하나 증가시키고, Node K 값<들어온 값<Node K+1의 값이면 Node K와 Node K+1 사이에 해당 값에 대한 노드를 추가한다.
중복된 정수는 linked list를 head부터 tail까지 운행하면서 Count값이 2 이상인 값이다.
이 알고리즘은 최악의 경우 O(N^2)가 된다.
따라서 무수히 많은 정수의 경우 O(N^2)는 좋은 알고리즘이 아니다. 이것은 소팅의 문제하고 비슷한데, 기본적으로 상기에 제시하는 알고리즘은 O(N^2)의 알고리즘의 동작 방식과 유사하다. 즉 기존 자료를 처음부터 scanning하면서 비교하고 해당 위치에 입력하는 방법이기 때문에 이런 한계가 생기는 것이다.
요것은 소팅 문제가 O(NlogN)으로 향상 될수 있는 것과 마찮가지로 O(NlogN)으로 향상이 가능하다.
우선 저장되는 자료구조를 Heap 트리 구조로 바꾸고,
1. 새로 들어오는 정수값을 Heap 운행으로 찾는다. (O(logN)) 이 값이 있으면 해당 노드의 Count값을 증가시키고 종료한다.
2. 새로 들어오는 정수값이 Heap에 존재하지 않으면 이 Heap tree에 해당 값에 대한 노드를 추가한다. (O(logN))
중복된 정수는 Heap트리를 운행하면서 Count값이 2 이상인 값이 된다.
이 알고리즘은 최악의 경우 O(NlogN)의 운행 시간을 가지게 된다.
즉 중요한 것은 컴퓨터 프로그램으로 어떤 문제를 풀기 위해서는 이 문제가 기본 알고리즘의 어느 문제로 변환될수 있느냐를 생각을 해보면 그 문제의 최적화 방법이 풀고자 하는 문제의 최적화 방법에 힌트를 제공할수 있다는 것이다.
비슷한 예로 Dynamic programming의 적용 예들을 볼수 있다. 실제로 Dynamic programming은 여러 문제를 푸는데 기본 틀을 제공해준다. 물론 기본적으로 어떤 상태의 최적화된 해는 기존 상태의 최적화된 해로 구성 된다는 전제만 있으면 그렇다.
아뭍은....당황하지 말고, 문제를 잘 읽어보고, 생각이 들렸으면 과감하게 고치고, 기본에 충실한 것이 Software engineer의 기본 자세가 되지 않을까...쯔업....(난 왜그랬을까..)
