센로그

정렬 문제의 계산 복잡도는 O(n lg n)이라는 걸 7장에서 증명했었다. 이번에는 검색 문제에 대해서 알아보자! ◆ 키를 비교함으로만 검색을 수행하는 경우의 하한 검색 문제란, n개의 키를 가진 배열 S와 어떤 키 x가 주어졌을 때, x = S[i]가 되는 인덱스 i를 찾는 것. 만약 x가 배열 S에 없을 때는 오류(F)로 처리한다. 이분 검색의 경우, 시간복잡도가 W(n) = floor(lg n) + 1이 되는데, (floor은 바닥 함수를 의미함) 정렬되어있을 때 키를 비교함으로만 검색을 수행하는 경우 이분 검색보다 더 좋은 알고리즘은 없다! 이진 검색과 순차 검색의 결정 트리를 비교하면서 이를 살펴보자. ■ 이진 검색의 결정 트리. 큰 마디(내부마디) – 키와 각 아이템을 비교하는 마디 작은마디(..

◆ 계산 복잡도 문제가 갖고있는 본연의 계산량. 최소한 얼마나 많은 계산을 해야 그 문제가 풀리는지 문제풀이 접근하는 2가지 방법 (1) 문제를 푸는 더 효율적인 알고리즘을 개발 (2) 더 효율적인 알고리즘 개발이 불가능함을 증명 (예) 정렬문제인 경우 Θ(n log n) 보다 좋은 알고리즘은 불가능함이 입증 되었음. 일반적으로 “계산 복잡도 분석”이란 “문제의 분석”을 지칭 (not "알고리즘의 분석") 어떤 문제에 대해서 그 문제를 풀 수 있는 모든 알고리즘의 효율의 하한(lower-bound)을 결정한다. (최소한 이것보다는 오래걸리거나 비슷하게 걸린다.) ex) 예를들어 행렬 곱셈 문제를 보자. - 알고리즘의 분석 ✓ 일반알고리즘: Θ(n³) ✓ Strassen의 알고리즘: Θ(n^2.81) ✓ ..

◆ 분기 한정법 (Branch and Bound)Branch: 가지를 나눈다Bound: 한계를 정한다 내가 어느쪽으로 가는 게 더 이득인지 가지를 치는 과정에서 한계를 가지고 판단하겠다 라는 뜻 되추적의 개념 + 최적화 문제에 대한 가장 좋은 해를 찾는 개념이 포함되어있다. 기본적으로 해를 찾아가는 방법은 백 트래킹. 어떤 해를 선택하느냐는 bound를 사용하며 뭐가 더 이득인지 판단. 되추적에서는 상태 공간 트리를 움직이면서 해를 찾았음. (promising 함수 사용) 분기한정법에서도 상태 공간 트리를 순회하긴 하는데, Bound 함수를 통해서 지금까지 찾은 해보다 최대한 더 좋은 해를 찾는 방향으로 나아가며, 최종적으로 가장 좋은 해를 찾아나가는 방법. ◆ 최소화 문제최소 거리의 트래킹 코스를 찾는..

◆ 되추적!? 어떤 수에서 더이상 확장할 수 없거나 유망하지 않다면 전 단계로 돌아가면서, 상태 공간을 만듦. 그 상태공간을 돌아다니면서 해를 찾는 방법. 마디의 유망성: ✓ 전혀 해답이 나올 가능성이 없는 마디는 유망하지 않다(non-promising) ✓ 그렇지 않으면 유망하다(promising). 되추적이란? ✓ 어떤 마디의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 마디의 부모마디(parent)로 돌아가서(backtrack) 다음 후손마디에 대한 검색을 계속하게 되는 절차. ✓ 부모마디로 돌아가는 것 → 가지치기(pruning) ✓ 이 과정에서 방문한 마디만으로 구성된 부분트리 → 가지친 상태공간 트리(pruned state space tree) ◆ 트리 방문 순서 ◆ n-queens ..

◆ Dijkstra 알고리즘 하나의 출발 지점으로부터 다른 모든 도착 지점들로 가는 각 최단 경로들을 모두 계산할 때 쓰는 방법 F (최종 결과 엣지 집합)를 공집합으로 초기화 Y (최단 경로가 확정된 노드들 집합)는 출발 노드로 초기화.(예시에서는 v1에서 출발하는 걸로 가정) V-Y집합(최단 경로가 확정된 노드들을 제외한 노드들)에 속한 노드 중에서, v1(출발 노드)에서 Y에 속한 정점만을 거쳐서(무조건 거쳐야 하는 것은 아님) 최단 경로가 되는 정점 v를 선정한다. 그 정점 v를 Y에 추가한다. v에서 Y로 이어지는 엣지('v와 Y를 잇기 위해 Y내에서 최종 경유하는 노드'와 'v노드'간의 엣지)를 F에 추가한다. Y = V가 되면(전체 노드 다 돌음), T = (V, F)가 최단 경..

◆ 탐욕적인 알고리즘 (Greedy Algorithm) 이란? 현 단계(상태)에서 가장 좋다고 생각되는 답을 선택함으로써 최종적인 해답에 도달하는 방법. 현 시점의 가장 좋은 해는 local 최적해이다. 그러나 항상 이것들이 모여서 global 최적해를 만들진 않는다. 따라서, 탐욕적인 알고리즘을 사용하려면 항상 최적의 해답을 주는지를 반드시 검증해야 함! ◆ 탐욕적인 알고리즘 설계 절차 걍 이런게 있구나 알고, 실제 알고리즘에서 어떤 부분이 어느 단계에 속하는지 알면 됨 1. 선정 과정 (selection procedure) 현재 상태에서 가장 좋으리라고 생각되는(greedy) 해답을 찾아서 해답모음(solution set)에 포함시킨다. 2. 적정성 점검 (feasibility check) 새로 얻은..