문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 제한 사항 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,..
동적 계획법
DP 제일 위에 있는 문제를 풀어보았다. 3kg과 5kg의 설탕으로 목표 무게를 만드는 것이다. 만들지 못하면 -1을 만들 수 있으면, 최소한의 수의 설탕으로 목표 무게를 만드는 것이다. 메모제이션을 이용하여 0부터 목표 무게까지 최소한의 수를 쌓아가면 된다. 0 = -1 1 = -1 2 = -1 3 = 1 4 = -1 5 = 1 은 기저 조건으로 설정한다. 만약 기저 조건보다 낮은 목표 무게가 있다면 예외 처리를 한다. 그리고, 이제 무게를 6부터 쌓아갈 때 3을 뺀 수와 5를 뺀 무게 중, 적은 수의 설탕 봉지를 쓴 경우를 택해 1을 더하면 된다. 또한, 15같은 무게는 3kg으로도 5kg으로도 만들 수 있다. 이런 경우를 생각해 3kg을 쓴 경우와 5kg을 쓴 경우 모두를 생각해 비교해야 한다. 다..
DP문제에 전형적인 풀이 방법인 메모제이션을 이용하여 문제를 풀었다. 처음에는 어떤 식으로 문제를 풀어 나가야 할지 감이 잡히지 않았다. 계속 생각한 결과 한가지만 주의하면 된다는 생각을 하게 되었다. 이웃한 집만 같은 색깔이 아니면 되기 때문에 하나의 집을 임의의 색으로 칠하면 다음 집에서는 선택할 수 있는 경우가 2가지로 좁혀지고, 그다음은 여전히 2가지의 선택의 경우가 생긴다. 즉, 소모 값들을 배열에 저장한다 생각하면, 같은 column에 있는 값만 선택하지 않으면 된다. 그렇다면 이제 index문제만 해결하면 문제는 풀린다. R은 [0]에, G는 [1]에, B는 [2]에 저장한다 하자. 2번 index의 요소를 처리한다 했을때, 0과 1에 접근할 수 있는 방법을 찾으면 된다. 링 버퍼의 개념을 ..
두 수열이 주어졌을 때, 가장 긴 공통 수열을 찾아내는 문제이다. 앞서 풀었던 가장 긴 증가하는 부분 수열과 비슷하다고 생각할 수 있지만 조금 다른 문제이다. for문을 여러 번 돌려 메모제이션을 이용하여 문제를 풀려했었다. 하지만, 문자열을 계속해서 반복하고 어디까지 일치하는지를 기록해야 하고, 건너뛰는 요소가 있을 수 있기 때문에 쉽지 않았다. 해답은 2차원 배열을 이용한 메모제이션이였다. 입력받은 두 문자열 길이보다 1씩 큰 2차원 배열을 생성한 뒤, 0번째 column과 0번째 row을 0으로 초기화 한 뒤, 문제를 풀어나가면 된다. 0으로 채우는 이유는 기저 조건을 설정하는 것이다. 2중 for문을 이용하여 row와 column의 각 요소들을 비교하며 진행한다. 그러다 일치하는 요소가 발견되면,..
증가하는 수열을 만드는 문제이다. 기준을 정해서 그 부분까지의 가장 긴 부분 수열을 구하는 문제로 분할할 수 있다. 즉 i번째까지의 가장 긴 증가하는 수열을 저장해놓고 계속해서 사용하며 마지막까지 수열을 구해 나간다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class partSequence { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int x = scan.nextInt(); //수열 저장 int arr[] = new int[x]; //가장 긴 증가하는 수열의 수 int solution[] = new int[x]; //입력을 받는 동시에 soluti..
동적 계획법을 이용하는 문제이다. 이 문제에는 총 세 가지의 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 얼핏 보면, 움직일 수 있는 두개의 계단 중 큰 수를 가진 계단을 이용하는 문제로 볼 수 있다. 하지만, 이것은 탐욕 법을 이용한 문제 풀이이며, 해답이 아니다. 동적 계획법으로 모든 경우의 수를 살펴 보아야 한다. 연속하는 세 개의 계단을 밟을 수 없고, 마지막 계단은 무조건 밟아야 하기 때문에 배열을 이용하여 i번째 계단이 마지막이라 가정하고 하나씩 풀어 나가면..
동적 계획법의 예제이다. 우선, 몇 개의 정수를 처리할지 입력받은 후 입력받은 개수만큼의 입력을 받는다. 그 후, 입력받은 수들을 1, 2, 3의 합으로만 나타내는 방법의 총 개수를 구하는 문제이다. 예를 들어 4는 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1로 총 7개이다. 규칙은 간단하다. 1과 2 그리고 3을 선택한다는 가정을하면 만들려는 수에서 선택한 수를 뺀 수를 만드는 경우의 수를 모두 더하면 되는 것이다. 1을 먼저 선택한 경우 1 + 3을 만드는 경우( 1+1+1, 1+2, 2+1, 3) => 4가지 2를 먼저 선택한 경우 2 + 2를 만드는 경우( 1+1, 2) => 2가지 3을 먼저 선택한 경우 3+ 1을 만드는 경우( 1 ) => 1가지 모두 더하면 ..
동적 계획법이란? 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 하위 문제의 해결책이 다른 하위 문제의 해결책과 같은 경우 유용하다. 탐욕 알고리즘과의 비교 탐욕 알고리즘은 문제가 발생하면 그 상황에서의 최적의 해를 선택하는 방식의 알고리즘을 말한다. 순간적으로 볼 때는 최적의 해를 반환하지만 전체적으로 보았을 때 그렇지만은 않은 상황이 존재한다. 예를 들어, 길을 찾는 문제가 주어졌다면 출발지부터 목적지까지 가는 중, 갈림길과 마주했을 때 그 순간 가장 짧은 길로 가는 것이다. 하지만 동적 계획법은 모든 갈림길을 살펴본 후 최적의 길을 탐색하게 된다. 동적 계획법은 모든 경우의 수를 살펴봐야 하기 때문에 시작시 조금의 시간이 걸릴..
