하노이의 탑(Tower of Hanoi) 문제란? 유례나 역사 같은 것은 다 생략하고, 문제의 조건 같은 본론부터 바로 말하겠다. 3개의 기둥과 이 기둥에 꽂을 수 있는 다양한 크기에 원판들이 존재한다. 맨 처음 시작할 때, 원판의 크기가 큰 것부터 1번 기둥에 모두 쌓는다. 맨 왼쪽 기둥부터 순서대로 1번, 2번, 3번 기둥이라고 한다. 문제에서 요구하는 것은 아래의 조건을 만족하면서, 1번 기둥에 쌓여있는 모든 원판들을 3번 기둥으로 옮기는 것이다. 조건 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. N개의 원판이 최소 경로로 이동할 때의 경로를 출력하라는 것이 문제에서 요구하는 것이다. 이 문제를 왜 알아야 할까? 중요한 것은 학습의 목적이다. 프로..

배낭 알고리즘이란? 배낭 문제(Knapsack)는 n개의 물건과 배낭 있을 때, 각 물건에는 가치와 무게가 존재한다. 또한 각 물건은 1개씩만 있다. 배낭에는 담을 수 있는 최대 용량이 존재한다. 이러한 조건일 때, 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제이다. 해당 그림은 배낭 문제의 예시이다. 지금부터 알고리즘을 설명할 때 해당 예시를 가지고 계속 설명하겠다. 0-1 KnapSack Problem 배낭 문제는 물건을 쪼갤 수 있는 Fraction Knaspack Problem과 물건을 쪼갤 수 없는 0-1 knapSack Problem으로 나뉜다. 이 글에서 설명하고자 하는 것은 0-1 KanpSack Problem이다. 대표적인 DP(Dynamic Pr..