with with

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..

Minimum Spanning Tree Greedy 알고리즘의 예시인 Prim's Algorithm을 살펴보기 전에 그 알고리즘이 다루는 Minimum Spanning Tree의 정의부터 알아보자. - Tree Graph 구조에서 cycle 구조가 존재하지 않고, 연결되지 않은 vertex가 없고, edge에 방향성이 없는 그래프. - Spanning Tree 오리지널 Tree의 부분 트리. 즉, 오리지널 Tree에서 일부 edge가 없는 트리를 의미한다. - Minimum Spanning Tree Spanning Tree 중, edge의 weight의 합이 최소가 되는 트리. G1이 오리지널 트리라 했을 때, G4, G5만이 G1의 Minimum Spanning Tree이다. G2의 경우에는 G1에 S..

물리 메모리의 크기와 상관없이 프로세스에 거대한 메모리 공간을 제공하는 기술로, 가상 메모리를 이용하면 프로세스는 운영체제가 어디에 있는지, 물리 메모리의 크기가 어느 정도인지 신경 쓰지 않고 메모리를 마음대로 사용할 수 있게 된다. 가상 메모리의 크기는 실제 메모리의 크기와 스왑 영역의 크기를 합친 만큼이 되는데, 가상 메모리 공간에 접근하기 위해서는 동적 주소 변환이 필요하다. 즉, 가상 주소를 실제 주소로 변환해야 데이터를 물리 메모리에 저장할 수 있는 것이다. 가상 메모리의 메모리 분할 방식은 물리 메모리에서 가변 분할 방식을 채택한 것 처럼 세그먼테이션 방식을 채택하는 경우와, 고정 분할 방식을 채택한 것 처럼 페이징을 채택하는 경우가 있다. 버디 시스템처럼 두 단점을 보완한 세그먼테이션-페이징..