with with

Computational Complexity Analysis - Sorting problem 정렬문제를 해결하기 위해 사용할 수 있는 모든 알고리즘의 복잡도의 한계를 알아보자. 즉, 정렬을 Θ(n)에 끝낼 수 있는지 알아보자. (이 것이 불가능하다는 것을 증명) 정렬을 하는 기본적인 방 with611.tistory.com 이전에는 알고리즘이 갖는 한계를 알아봤었다. 이번에는 문제 자체가 갖는 한계를 알아보자. (즉, 어떠한 알고리즘을 써도 이보다 낫게 풀 수 없다는 것) 문제의 종류는 아래의 세 종류가 있다. Polynomial-Time algorithm found 다항식의 차수 시간 복잡도를 갖는 알고리즘으로 문제를 풀 수 있는 경우. - Sorting - Shortest paths problem - ..

정렬문제를 해결하기 위해 사용할 수 있는 모든 알고리즘의 복잡도의 한계를 알아보자. 즉, 정렬을 Θ(n)에 끝낼 수 있는지 알아보자. (이 것이 불가능하다는 것을 증명) 정렬을 하는 기본적인 방법은 key값을 통한 비교를 이용한 방법을 사용한다. key값의 비교를 사용하는 알고리즘의 각각의 시간 복잡도의 하한선, lower bound를 알아보고, 각각의 정렬 방법의 한계를 알아보자. - Insertion Sort 삽입 정렬은 key값 하나를 지정하고 뒤로가며 비교하는데, 보다 큰 원소를 만나면 모두 앞으로 한 칸씩 말고 본인이 그 자리에 들어가는 식으로 정렬한다. 시간 복잡도는 다음과 같다. Worst case: n(n-1)/2 = Θ(n^2) Average case: (n+4)(n-1)/4 - ln n..

0-1 Knapsack Promble은 각각의 가치(profit)와 무게(weight)를 갖는 여러 아이템을 가방에 추가하는데, 최대 가방이 담을 수 있는 무게를 초과하지 않는 범위에서 아이템의 가치가 최대가 되도록하는 아이템의 집합을 찾는 알고리즘이다. 이 문제를 접근하는 방법은 여러개가 있어 한 번에 소개해보고자 한다. Greedy Approach 그리디한 방법으로 해결하는 접근방식은 다음과 같다. 단위무게당 가격으로 내림차순 정렬을 하고, 무게가 가득 찰 때 까지 집어넣는 방식이다. 하지만 이 방식에는 문제가 존재한다. 바로 항상 최적해를 도출하지는 못한다는 것이다. 단, fractional knapsack problem의 경우에는 그리디한 방법으로도 최적해를 도출할 수 있다. (fractional..

Traveling SalesPerson Problem (Dynamic Programming) - 알고리즘 정의 주어진 Graph의 모든 노드를 한 번씩 방문하여 출발했던 노드로 돌아오는 방법 중, 가장 최단 시간으로 걸리는 경로를 찾는 문제이다. 일명 TSP 알고리즘이다. 위 예시에서는 v1 - v3 with611.tistory.com TSP문제는 DP방식으로 접근해 본 적이 있다. 이번에는 Branch and Bound방식을 사용해 접근해보려 한다. Branch and Bound 방식은 탐색(상태 저장) 공간을 트리구조를 이용한다는 점에서 백 트래킹 방식과 유사하 차이점은, 백 트래킹 방식은 앞서 언급한 적이 있듯 depth-first search 방식으로 탐색을 진행하며, 구현에 따라 모든(여러) 최..

n개의 양의 정수가 있을 때, 그 합이 특정 양의 정수 W가 되도록 하는 정수들의 집합을 찾는 문제이다. 이 문제 역시 Backtracking 기법과 promising 개념으로 해결할 수 있다. 문제에 대한 접근은 우선 작은 양의 정수부터 트리에 추가할지 말지 결정한다. 그 이후 해당 노드가 promising한지 검사하고 추가로 탐색할 것인지를 결정한다. - NonPromising Node 가망이 없는 노드는 아래 두 가지 경우 중에 하나이다. 아직 W에 도달하지 못했으나, 남은 수 중에 가장 작은 수를 추가했을 때 W보다 무거워지는 경우 남은 모든 수를 추가해도 W에 도달하지 못하는 경우 - Promising Node NonPromising Node가 아닌 노드. 즉, 위 두 조건이 모두 거짓이 나오는..

N*N 크기의 체스보드에 서로의 퀸이 공격하지 못하게 배치하는 방법을 찾는 문제이다. 이 문제를 해결하기 위해선 Backtracking 이라는 기법을 사용할 예정이다. 백 트래킹 기법은 각 스탭에서 조건을 충족시키는 경우의 수만 다음 스탭을 진행시킨다는 점에서 그리디 기법과 유사하다. 하지만, 그와 다르게 백 트래킹은 조건을 충족하지 않는 경우 이전의 선택지로 돌아갈 수 있다는 특징이 있다. 따라서 기본적으로 백 트래킹 기법은 Depth-first search를 진행하여 트리를 탐색한다. N Queens Problem 우선 문제에 대한 접근은 한 행에는 하나의 퀸만 배치한다. 이렇게 되면 퀸이 공격 가능한지 검사할 때, 대각선과 열에 대해서만 검사하면 된다. 이 문제를 해결하기 위해 여기서도 promis..

Huffman Code는 데이터를 압축하는데 있어 효과적인 인코딩 방법으로, 텍스트 파일을 가변길이의 이진코드로 변환하는데 사용된다. 예로 들어 허프만 코드로 a: 10, b: 0, c: 11로 변환한다면 ababcbbbc는 1001001100011로 변환된다. ababcbbbc는 9bytes 즉, 72bit를 사용해서 저장해야 하지만, 허프만 체계로 변환된 1001001100011은 13bit면 저장이 가능하다. (복호화에 필요한 헤더 제외) a: 10, b: 0, c: 11와 같은 코드로 변환할 때는 prefix code로 변환해야만 한다. prefix code란, 어떤 문자를 나타내는 코드는 다른 문자를 나타내는 코드의 앞 부분과 반드시 다른 코드체계를 의미한다. prefix code로 구성해야지만..

Prim's Algorithm Minimum Spanning Tree Greedy 알고리즘의 예시인 Prim's Algorithm을 살펴보기 전에 그 알고리즘이 다루는 Minimum Spanning Tree의 정의부터 알아보자. - Tree Graph 구조에서 cycle 구조가 존재하지 않고, 연결되지 않 with611.tistory.com 저번에는 Prim's Algoritm을 이용해서 graph에서 minimum spanning tree를 구하는 방법을 알아봤다. Kruskal's Algorithm역시 graph에서 minimum spanning tree를 구하는 알고리즘이지만, 접근 방식에서 약간의 차이가 있다. Prim 알고리즘은 vertex를 중심으로 설계했다면, Kruskal 알고리즘은 edg..