센로그

◆ 분기 한정법 (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)가 최단 경로를 나타내는 그래프(ve..

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

◆ 동적 계획법 (Dynamic Programming)입력 크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 문제를 해결해나가는 알고리즘. 다음 두 가지 조건을 만족해야 동적 계획법으로 쓸 수 있다.작은 문제들의 해를 활용해 큰 문제를 풀 수 있어야 함.최적의 원칙 : 전체가 최적이면 부분에 대해서도 최적이어야 함. ◆ 분할 정복법 vs 동적 계획법ㆍ분할 정복법- 하향식(top-down) 해결법- 큰 문제를 해결하는 데에만 관심이 있음 ㆍ동적 계획법- 상향식(bottom-up) 해결법- 작은 문제의 해결을 활용해 큰 문제를 해결 ◆ 이항 계수(binomial coefficient) 구하기분할 정복법 vs 동적 계획법으로 이항 계수를 구하는 법을 알아볼 것이다.  ◆ 이항 ..

◆ 분할 정복식 설계 전략큰 문제를 작은 문제로 나누어 해결한 후, 해답을 모아 큰 문제의 해를 만드는 방법문제의 성질과 전체 형태가 작은 문제에서도 똑같이 유지 됨  분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.정복(Conquer): 나눈 작은 문제를 각각 해결한다.  통합(Combine): (필요하다면) 해결된 해답을 모은다. 이러한 문제 해결 방법을 하향식(top-down)  접근 방법이라고 한다. ◆ 바닥 함수와 천장 함수 바닥 함수: 실수 x에 대해, x보다 작거나 같은 정수 중 가장 큰 정수 천장 함수: 실수 x에 대해, x보다 크거나 같은 정수 중 가장 작은 정수    ◆ 이분 검색 (binary search)배열을 반으로 나눠서, 찾아야할 x와 locatio..