건빵의 블로그

Branch and Bound 기법은 백트래킹과 유사하게 어떠한 기준을 만족하는 순서를 정하는 알고리즘 기법이다. 하지만 state space tree를 traverse하는 방법을 특별하게 정하지 않는다는 점에서 백트래킹과 다르며, branch and bound는 최적화 문제에 주로 사용된다. 즉, 백트래킹은 branch and bound의 일부라고 봐도 될 것이다. branch and bound는 어떠한 노드의 promising을 판단하기 위해 bound 개념을 도입한다. 최소해를 구하는 문제에 있어서는 minimum bound를, 최고의 값을 구하는 문제에 있어서는 maximum bound를 정한다. bound는 현재의 상태에서 나올 수 있는 최대 혹은 최소의 값을 의미한다. branch and bo..

백트래킹은 어떠한 기준을 만족하는 순서를 구하기 위해서 사용하는 알고리즘 기법이다. 솔루션을 찾아나가는 과정에서 잘못되었을 경우 backtrack을 통해 기존의 부분적인 해로 되돌아 갈 수 있다. 백트래킹 과정은 어떠한 상태의 변화를 나타내는 state space tree를 Depth First Search(DFS)하는 과정으로 볼 수 있으며 중간 중간에 상태가 해를 만들수 있는지 없는지를 판단하여 적절치 못한 부분적인 해일 경우 backtrack한다. 그 적절함의 여부를 promising이라고 하기도 한다. 즉, 어떠한 노드가 non-promising하면 backtrack한다. 백트랙킹은 recursive DFS알고리즘을 통하여 구현될 수 있다. 백트래킹은 시간의 문제일 뿐 해가 존재한다면 어떻게든 반..

우선 Spanning tree의 정의에 대해서 되돌아볼 필요가 있다. 스패닝 트리는 어떠한 그래프의 서브그래프이면서 그래프의 모든 버텍스를 포함하는 트리이다. 그러한 그래프가 edge에 weight를 가질때, weight의 합을 최소화하는 스패닝 트리를 Minimum spanning tree라 하며 그것을 구하는 알고리즘으로 Prim's algorithm과 Kruskal's algorithm이 있다. 위 두가지 방법은 Greedy Approach를 이용하여서 각자의 기준을 가지고 스패닝 트리를 만들게 된다. 우선 첫째로, Prim의 알고리즘은 하나의 버텍스에서 시작하여 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연결된 버텍스를 선택하고 연결한다. 여기에서 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연..

어떠한 선택을 연속적으로 하는데, 그 순간순간 가장 좋아보이는 것을 선택하여 솔루션을 만들어 내는 접근법을 Greedy Approach라고 한다. 각각의 선택은 locally optimal하지만 global optimal하지는 않을 수도 있다. Greedy approach의 장점은 쉽게 알고리즘을 풀어나갈 수 있다는 것이지만, 단점은 항상 optimal 하다는 것을 보장하지 못한다는 것이다. 따라서, 수학적인 증명을 통해 optimal 여부를 판단해야 한다. 일반적으로 이 접근법은 세가지 절차로 나눌 수 있다. 1. Selection Procedure 어떠한 기준(Greedy Criteria)을 가지고 선택한다. 2. Feasibility Check 새롭게 선택한 것이 해를 만드는데 있어서 적합한지 판단..

알고리즘 수업을 들을때도 이 부분은 안드로메다였는데, 뭔가 알겠다 싶었는데 다시 보니까 더 헷갈린다. 그래도 안볼수는 없으니 이해하며 정리해보자. 일단 Decision problem의 정의에 대해서 알아야 한다. Decision Problem은 어떠한 인스턴스에 대해서 "yes" or "no"로 답할 수 있는 문제를 말한다. 쉬운 예를 들자면, 스무고개를 하면 질문을 할때 예 또는 아니오로만 답할 수 있는 질문을 해야한다. 그러한 문제들을 decision problem이라고 보면 되겠다. 이어서 집합 P와 NP의 정의는 다음과 같다. P : 다항식 시간(polynomial-time)의 알고리즘으로 풀리는 decision problem의 집합 NP : 비결정적 다항식시간(polynomial-time non..

sort를 나타낼 때 stability로 구분하기도 하는데요. stable sort의 의미는 정렬 후에도 정렬된 순서가 그대로 유지되는 것을 말하며 unstable sort는 stable하지 않은 것을 의미합니다. stable sort 중 대표적인 것이 Merge sort이며 unstable sort 중 대표적인 것이 Quick sort입니다. 두 sort 다 average case의 경우에는 n lg n의 order를 가지지만 안정성에서 Merge가 낫고 또한 worst의 경우에도 Merge는 n lg n이므로 Merge를 사용하는게 더 낫다고 볼 수 있습니다. 하지만 Quick sort는 in-place sort로써 부가적인 공간을 필요로하지 않기 때문에 부가적인 공간에 제약이 있을 경우에는 merg..

재밌는것 같은데 너무 어려운 다이나믹 프로그래밍.ㅡㅜ Dynamic Programming(동적 프로그래밍)은 문제를 작은 인스턴스들로 나누고 Bottom-up order로 풀어나가면서 문제의 값을 저장해놓고 필요할때 가져와 쓰는 방식으로 문제를 해결하는 방식을 의미한다. Divide and conquer와의 공통점은 문제를 작은 단위로 나누어 해결한다는 것이고 차이점은 Divide and conquer는 Top-down 방식으로 위에서부터 진행하는 방식인데 Dynamic Programming은 Bottom-up 방식으로 작은 인스턴스부터 풀어나가면서 그 값을 더 큰 인스턴스를 풀 때 이용한다. 기존에 진행된 smaller instance의 값들은 주로 이차원 array에 저장되며 영향을 받는 변수의 수에..

Divide and Conquer(분할 후 정복) 방법은 어떠한 문제를 작은 단위로 나누고 그것이 해결하기에 충분히 작으면 그것을 풀고, 아니면 더 작은 단위로 쪼개어 알고리즘을 풀어나가는 방식을 의미한다. 대체적으로 확신할 수는 없지만 Divide and Conquer라 하면 재귀(Recursive) 방식으로 알고리즘을 풀어나간다. 그래서 Divide and Conquer를 Top-down approach라고 한다. (Dynamic Programming은 이와는 반대로 Bottom-Up approach이다) Divide and Conquer로 풀 수 있는 문제의 예는 Binary Search, Merge Sort, Quick Sort 등등이 있다. Divide and Conquer로 문제를 풀기에 적당..

알고리즘의 정의는 a finite set of instructions for solving a problem 이다. 어떠한 문제를 푸는 방법을 정의한 것이다. 즉 프로그램이라는 것은 Data Structure + Algorithms이라고 볼 수 있다. 그렇다면 어떠한 문제가 있을 때 그것을 해결할 수 있는 알고리즘은 많이 있을 것이고 그 알고리즘 간에 어떤것이 효율적인가를 결정할 수 있어야한다. 그래서 나온 개념이 복잡도(Complexity)이며 어떤 알고리즘의 complexity는 보통 Big-O notation으로 많이 나타내는데 엄밀히 따지면 Big-theta notation으로 나타내야 한다. 그리고 어떤 알고리즘이 어떠한 theta(x)의 복잡도를 가지면 그 알고리즘은 order of x의 복잡..

앞에서 언급했던 Binary Search Tree의 단점을 생각해 보자. 트리가 skewed tree 또는 지그재그 트리 형태로 자라난다면 비효율적인 자료구조가 된다. 우리의 목적은 효율적인 자료구조를 만드는 것이기 때문에 뭔가 보완이 필요하다는 것을 알수가 있다. 그래서 나오는 것들이 Balanced Tree 종류이다. 트리의 Leaf들의 Depth들이 균형 잡힌 형태로 되도록 한다. 그 예로는 B-tree, AVL tree, Red-black tree 등등이 있으며 B-tree와 AVL tree에 대해서 공부해 보았다. B-tree의 성질은 다음과 같다. 1) B-tree는 BST와 같은 Search tree를 구성하되 각 노드가 여러 개의 엔트리를 가진다.(하나의 노드에 값 여러개) 2) 노드의 엔..