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

문제 이해 단계 https://www.acmicpc.net/problem/14719 2차원 맵이 주어진다. 이때 같은 층에 열로 가둬질 때 (위 그림처럼) 빗물을 담을 수 있다. 이 조건에서 2차원 맵의 크기가 주어지고, 각 행마다의 높이가 주어질 때 빗물의 총량을 구하는 문제이다. 문제 접근 단계 빗물의 총량을 구하기 위해서는 주어진 2차원 맵을 탐색 하면서 연산할 수 있는 일반화된 알고리즘이 필요하다고 생각했다. 그래서 일반화된 연산식을 만드는 것을 중점으로 생각했다. 첫 번째부터 쌓인 블록부터 탐색한다고 생각한다. 첫 번째 블록과 어떤 블록 사이에는 빗물이 쌓인다. 첫 번째 블록이 빗물을 담는 시작점이라고 생각(즉, 왼쪽 벽)하자. 그렇다면 첫 번째 블록과 쌍이 되는 오른쪽 벽은 어떻게 결정할까? ..

문제 이해 단계 쉽게 말하면 2차원 표가 주어지고 그 표 안에는 사람 수가 적혀 있다. 그리고 입력으로 시작좌표(x, y)와 끝좌표(x, y)가 들어온다 그 사이를 사각형으로 둘러쌓을 때, 그 안에 들어오는 사람수의 총합을 구하는 문제이다. 문제 접근 단계 일단 이 문제를 읽자마자 너무 당연해서 당황했다. 그냥 당연히 좌표제한해서 하나하나씩 세면 되지 않을까? 근데 그러면 문제를 냈을 리가 없지, 하면서 문제 조건을 잘 읽어봤다. 영토 크기는 최대 1024X1024 = 즉 2^20으로 엄청나게 크다. 무엇보다도 계산을 한 번만 하는 게 아니다. 궁금해하는 영토의 개수 K가 최소 100,000개이기 때문에 일반적으로 개수를 세서 더하는 걸로는 딱 봐도 시간초과가 뜰 것 같다. 이전 계산의 결과를 저장하거나..

문제 이해 단계 빨간색 : 누르는 버튼과 대응되는 스위치 파란색 : 버튼에 영향을 받는 스위치 문제는 N개의 스위치와 버튼이 나열되어 있는데 각각 1대 1 대응된다. I번 버튼을 누르면, 그 버튼 번호의 스위치와 양옆에 있는 스위치가 반전된다. 초기 상태와 결과 상태가 주어질 때 초기 상태에서 결과 상태까지 만드는 최수를 구하는 문제이다. 문제 접근 단계 일단 대략적으로 문제의 유형부터 생각해 보기로 했다. DP? 처음에는 Dp로 풀까 생각했었는데, 1. 처음 시작하는 수가 고정되어 있지 않다. 2. n = 1 일 때 3, n = 2 일 때 4.. 뭐 이런 식으로 값이 고정된 것도 아니다. 위의 근거로, dp는 아닌 것 같았다. Greedy? 그리디로 생각한 이유는 간단하다. 그냥 문제에서 "최소를 구해..

문제 이해 단계 https://www.acmicpc.net/problem/17485 맵(표)이 하나 주어진다. 목표는 위에서 아래로 가는 것이다. 각 칸에는 점수가 있고 그 점수의 합이 최소가 되도록 하는 것이다. 여기서 규칙이 두 가지 존재한다. 1. 아래쪽으로만 이동 가능하다.(옆, 위로 이동 불가능) 2. 갔단 방향으로 연속 이동 불가능 (왼쪽 대각선, 왼쪽 대각선 이런 식으로 불가능) 이 조건일 때 점수의 합이 최소가 될 때, 그 최소의 점수가 얼마인지 구하는 문제 문제 접근 단계 일단 어떤 식으로 문제를 풀어야 하는지가 중요하다. 규칙 중 '아래쪽으로만 이동 가능하다'를 곰곰이 생각해 보자. 이 말은 한번 내려오면 위로는 다시 가지 못한다는 뜻이다. 즉, 만약 N번째 행까지 이동했다고 했을 때,..

문제 이해 단계 Dp에서 흔히 볼 수 있는 k개의 동전으로 합이 n이 동전을 만드는 문제이다. 이 문제에서 다른 점은 동전마다 개수 제한이 있다는 점이다. 문제 접근 단계 일반적은 동전문제라면 이전에 계산해 놨던 결과 중에서 가장 많은 것을 찾는 방법을 사용한다. 하지만. 이 문제에서는 개수 제한이 있기 때문에 다른 방법을 사용한다. 가장 많은 것을 찾는 방법을 사용할 수 없는 이유는, 예제케이스에서 20과 15의 경우의 수를 구한다고 가정하자. 15원에서 5원이 사용되는 경우의 수는 (5x3), (5x2 + 1x5), (5x1 + 10x1)이다. 20원에서 5원이 사용되는 경우의 수는 (5x3 + 1x5), (5x2 + 10x1), (5x1 + 10x1 + 1x5)이다. 어떤 한 수를 더해서 20원이 ..

문제 이해 단계 입력으로 N 개의 숫자들이 하나씩 띄어져서 주어진다. 마지막 수 앞에는 무조건 등호(=)가 들어가고 맨 앞을 제외하고는 +나 -를 자유롭게 넣을 수 있다. 여기서 조건이 하나 주어지는데, 중간 계산 가운데에 연산 값이 0 ~ 20 사이여야 한다. 즉 음수가 나오거나 20이 넘어가면 안 된다는 점을 유의해야 한다. 이러한 조건에서 수식을 올바르게 일치시키는 경우의 수를 구하는 문제이다. 힌트를 보면 대충 무슨 소리인지 이해가 될 것이다. 문제 접근 단계 힌트라고 주긴 줬는데, 솔직히 매직아이 올 거 같아서 힌트는 생각 안 하는 게 나을 것 같다. 위의 예제들로 생각해 보자. 위에 숫자들이 너무 많은데 8이 나오도록 끝에서부터 계산한다고 생각해 보자. 8 3 2 4 8 7 2 4 0 8 = ..

문제 이해 단계 문제를 이해하는데 굉장히 헷갈렸다. 설명이 짧아서 이게 무슨 소리인가 싶어서 한참을 봤다. 두 개의 대문자 문자열이 주어지고, 그 두 문자열 중 공통 문자 중 가장 긴 수열을 구한다는 것인데 이런 것이다. 예제에서는 공통 문자가 'A, C, K, P' 총 4개인데, ACAYKP 입장에서 공통된 것을 나열해 보면 ACAKP CAPCAK 입장에서는 CAPCAK이다. 이 중에서 이 형태를 유지하면서 얻을 수 있는 가장 긴 수열은 ACAK라는 뜻이다. P를 사용하지 못하는 이유는 P를 사용하면 배열 형태가 달라지기 때문이다. 아무튼 이런 식으로 접근하면 된다. 문제 접근 단계 해당 문제는 총 2가지의 풀이법이 존재한다. 1. 논리적 풀이 2. 수학적 풀이 풀이법을 하나하나씩 풀어보겠다. 1. 논..