with with

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

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

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