코딩스토리

배낭 알고리즘 배낭 알고리즘은 크게 2가지로 나뉜다. 1) 분할 가능 배낭 문제 (Fractional Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼개서 담을 수 있을 때 2) 0 - 1 배낭 문제 (0 - 1 Knapsack Problem) -> 배낭에 담아야 할 물건을 쪼갤 수 없을 때 1번 경우는 보통 그리디 알고리즘으로 해결한다. 뭐.. 풀어보진 않았지만 가치가 높은 물건을 최대한 많이 쪼개서 넣으면 되겠죠? 문제는 2번 경우이다. 사실 0 - 1 배낭 문제는 NP - Complete 문제에 속한다. 알린이라도 NP-Complete는 한 번쯤은 들어봤을 것이다. 내 기억에 NP-Complete 문제 중 하나라도 다항 시간 안에 해결할 수 있다면 모든 NP 문제를 다항 시간에 해결..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 본격적인 행렬 제곱 DP를 사용한 문제이다. 피보나치 수를 구하는 문제는 다이나믹 프로그래밍의 전형적인 문제 유형이다. 대부분 DP를 시작하는 사람들은 피보나치 수를 처음 접하면서 시작한다. 이 문제 역시 피보나치 수를 구하는 문제이다. 다른 점은 n 제한 하나이다. 이 문제의 n제한은 "1,000,000,000,000,000,000"이다. 이번에도 이 숫자가 내 통장잔고였으면.. 하지만 이번 건 스케일이 좀 남다르다. 내 통장잔고의 문제가 아니라 몇 년치 국가 예산보다 크지 ..

www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net KOALA의 이번 주 모의테스트 문제였다. 누가 봐도 DP 문제였다. 처음에 문제를 제대로 안 읽고 풀다가 시간을 많이 날렸다. 돌다리의 길이가 최대 100인데 10으로 보고 풀다가.. 내 시간ㅠㅠ 핵심은 반드시 한 번씩 마법의 두루마리에 적힌 문자열을 모두 밟아야 한다는 것이다. dp 문제의 핵심은 당연히 dp를 어떻게 정의하냐이다. 나는 dp[ i ][ j ][ k ]를 아래와 같이 정의했다. 마법의 두루마리에 적힌 ..

www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 오랜만에 정말 오랫동안 고민한 문제다. 물론 새벽이라 피곤했다는 핑계가 있지만.. 최근 들어서는 오래 고민하는 습관을 버리려고 노력했는데 실패.. 도저히 떠오르지가 않아서 구글링을 해보았다. 더 놀라운건 구글링을 한 페이지 가까이했는데도 이해가 잘 안 간다........ㅠ 너무나도 길고 복잡한 재귀 코드들... 난 이해하고 싶지 않았다 (제가 구글링을 하면서 느낀 건데 코드가 간단할수록 이해하기 좋더라고요.. 그래서 스포? 지..

www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP를 공부했던 사람들이라면 아마 대부분 RGB거리 1을 풀어봤을 것이다. 나 역시 RGB거리 1을 얼마 전에 풀어봤고, 어렵지 않게 점화식을 구할 수 있었기에 RGB2에 도전하였다. 빨리 풀고 그냥 딴 거 하려 했는데 코드가 생각보다 더럽고.. 뭐 일단 맞긴 했는데 정확한 풀이인지 확신이 안 서서 딴 사람들 풀이가 궁금해서 구글링 해봤는데.. 뭔 소린지 모르겠어 이게 컴공의 특성인..