👩🏻‍🌾

□Intractability Polynomial-Time algorithm (다항시간 알고리즘) - W(n) ∈ O(p(n))인 알고리즘이고, 이때 p(n)의 예시로는 2n, 3n^3 + 4n, n lg n 등이 있다. ex) Insertion Sort, Sequential Search, etc An Intractable Problem - polynomial - time 알고리즘으로 해결이 불가능한 문제를 intractable이라고 불린다. □The Three General Catagories of Problems 3 Categories of Problems Polynomial-Time algorithm found sorting, shortest paths problem, minimum spanning ..

□Insertion Sort - 이미 존재하는 정렬된 배열에 값을 삽입하여 정렬하는 알고리즘 정렬 방법 1. 첫번째 (i - 1) 배열 자리가 정렬되었고, x가 i번째 자리의 키라고 가정하자 2. x보다 작은 값을 찾을 때까지 x를 S[i - 1], S[i - 2] 등과 비교한다. 이런 자리의 인덱스를 j로 두자. 3. S[j + 1] ~ S[i - 1]의 값을 S[j + 2] ~ S[i]로 이동하고 (j + 1)번째 자리에 x를 삽입한다. 4. 이 과정을 i = 2에서 i = n까지 반복한다. public static void insertionSort(int n, keyType[]S){ index i,j; keyType x; for(i = 2; i 0 && S[j] > x){ S[j + 1] = S[j..

Branch and Bound - Backtraking과 같이 state-space tree를 사용한다. - 트리를 탐색하는 방식에 제한을 두지 않는다. - 오직 최적화 문제에만 사용된다. BFS와 Best-First Search를 사용해서 탐색을 진행하는데 이번 포스팅에서는 Best-First Search로 0-1 Knapsack Problem을 해결하는 방식에 대해 작성하도록 하겠습니다. 0-1 Knapsack Problem using Best-First Search Basic Idea - 노드가 promising한지로 결정하기보다는 bound를 사용해서 다음으로 확장할 노드를 선택 - 노드의 bound로 우선순위가 정해지는 priority queue를 사용 1. item을 모두 넣지 않았을 떄, b..

Backtracking 해를 찾는 도중 막히면 이전 단계로 돌아가서 해를 찾아가는 기법 Backtracking을 사용하는 3가지 예시를 보자. 1. N-queens problem - N x N 크기의 체스보드판에 N개의 퀸들을 서로 위협하지 않게 배치하는 문제 4 queens problem일 때 16개의 자리 중 4자리를 뽑는 경우 : C(16, 4) = 1820 두 퀸이 같은 행, 열 또는 대각선에 위치할 수 없으므로 배제할 수 있는 경우 : 4 x 4 x 4 x 4 = 256 : i행 j열에 퀸이 위치 처음 시작할 때와, 에만 퀸이 위치할 때 -> 하위 노드에서 답을 발견할 가능성이 있으므로 promising , , 에 퀸들이 위치할 때, 같은 열에 위치하므로 답이 될 수 없으므로 nonpromisi..

Greedy Algorithm -매 순간 가장 좋아보이는 것을 고르는 방법 General Greedy Approach - 빈 집합으로 시작하여 집합 인스턴스에 대한 답을 나타낼 때까지 집합에 아이템을 순서대로 추가 선택 절차 ( = Selection Procedure) 그리디 기준에 따라 집합에 추가할 다음 아이템을 선택 타당성 확인 ( = Feasibility Check) 인스턴스에 답을 제공하는 방식으로 집합을 완료할 수 있는지 여부를 확인 답 확인 ( = Solution Check) 새 집합이 인스턴스에 대한 답을 구성하는지 여부를 결정 Minimum Spanning Trees 정의 Undirected Graph Connected Graph Acyclic Graph Tree Spanning Tree..

Dynamic Programming이란?최적화 문제를 풀기 위한 수학적인 알고리즘. 문제를 작은 부분 문제로 나누고, 중복되는 부분 문제의 해를 저장하여 중복 계산을 피할 수 있고, 작은 부분 문제의 해를 조합하여 전체 문제의 해를 구하는 방법(=Bottom-Up) 4가지의 예시를 통해 Dynamic Programming에 대해 자세히 알아보자.1. The Binomial CoefficientC(n, k) = C(n-1, k) + C(n-1, k-1) for 0