기록기록 우는 갈매기

외판원 문제란? home city에서 출발해 모든 city를 한번씩 거치고 다시 home city로 돌아오는 최단 경로를 구하는 문제이다. 만약 무식하게 모든 경우의 수를 다 알아본 후 가장 짧은 경로를 찾는다면 그 성능은 어떻게 될까? (n - 1)! 즉 O(n!)이라는 결과가 나온다. 이렇게 비효율적인 방법은 쓸모가 없으므로 우리는 동적계획법을 사용하여 TSP를 풀어보려고 한다. ① W : 그래프의 인접행렬 W[i][j] = 이음선의 가중치 (vi에서 vj로의 이음선이 있는 경우) = ∞ (vi에서 vj로의 이음선이 없는 경우) = 0 ( i = j인 경우 ) ② V : 모든 정점들이 담긴 집합 ③ A : V의 부분집합 ④ D[vi][A] : vi에서 A의 집합들을 한번씩 모두 지나면서 v1로 가는 ..

최적 이진 검색 트리란? 최적 이진 검색트리의 뜻을 알기위해서는 먼저 이진 검색 트리의 뜻을 알아야한다. 이진 검색 트리는 말 그대로 이진 트리를 검색 목적으로 사용하는 것이다. 왼쪽에는 같거나 더 작은 값을, 오른쪽에는 더 큰 값을 저장하고 leaf 노드들 간의 depth 차이가 1보다 클 수 없다. 여기서 '최적'이란 단어까지 붙으면 최적 이진 검색트리가 된다. 최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미한다. 탐색시간은 원하는 키를 찾기까지 필요한 비교 횟수이다. 평균 탐색시간은 한 노드에 담긴 keym이 찾고자하는 search key일 확률을 pm라고 하고, keym을 찾기까지의 비교횟수를 cm이라고 할 때 pm과 cm의..

divide-and-conquer의 핵심은 재귀호출이다. 전체를 풀 때와 부분을 풀 때의 풀이가 같은 경우 큰 문제를 작은 문제로 쪼개서 해결하는데, 이 때 top-down 방식과 bottom-up방식이 있다. top-down: 처음부터 큰 문제를 방문 후 작은 문제를 호출, 재귀(recursive)방식 사용 bottom-up: 작은 문제들부터 해결 후 이를 바탕으로 더 큰 문제들을 해결, 반복(iterative) 방식 사용 top-down과 bottom-up 모두 문제를 쪼갠다는 점에서 비슷해보일 수 있지만 시도 자체가 다르다. top-down은 처음부터 큰 문제를 해결하려고 시도하지만, bottom-up은 큰 문제부터 해결하려하지 않고 작은 문제부터 시작한다. divide-and-conquer은 위의..