다이나믹 프로그래밍
2xn 타일링 _ 백준 11726, 백준 11727
11726번 문제와 11727문제는 하나의 조건만 달라서 한번에 정리해보려고 한다. 11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 2×n 타일의 우측에 칸을 채워넣는 방식으로 생각하면, 방법은 두가지이다. 1×2가 들어가게 되면 한칸이 완전히 차게 되고, 2 X n-1이 남는다. → d[n-1] 2 X 1 이 들어가게 되면 두칸이 차게되고, 2 X n-2가 남는다 → d[n-2] DP문제이니만큼, 점화식을 세워보면, 2 x n 크기의 타일을 채우는 방법의 수를 d[n]이라고 하면 d[n] = d[n-1] + d[n-2]이 되는 것이다. 여기서 조금 헤맨 부분을 이야기하자면, 그냥 이렇게 세워서 문제를 풀다보니 계속 답이 틀렸다고 하는 문제가 ..
1로 만들기_ 백준 1463
1로만들기는 DP를 활용해서 푸는 문제이다. 문제에서 제시되는 내용으로는 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이고, 이를 활용하여 정수 N이 주어졌을 때, 연산 세 개를 적절히 사용해서 1을 만드는 연산횟수의 최솟값을 구하는 것이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 그러면 D[i]가 i를 1로 만드는데 필요한 최소 연산횟수라고 했을 때, D[i] = D[i/3] + 1 D[i] = D[i/2] + 1 D[i] = D[i-1] + 1 셋중에 하나가 최솟값으로 들어가게 된다. 기본적으로 D[1] = 0이므로, 이를 기반으로 해서 bottom up 방식으로 코드를 구현하면 아래와 같다. #include #include u..
다이나믹 프로그래밍 기초
오늘부터는 다이나믹 프로그래밍 (DP)와 관련되어서 문제를 쭉 풀어보려고 한다. 다이나믹 프로그래밍의 구현 방식에는 크게 두가지 방법이 있다. 1. Top-down 방식 : 재귀를 활용해서, 큰 문제를 작은 문제로 쪼개는 방식 (ex 피보나치) 2. Bottom-up 방식 : 반복문을 활용해서, 작은 문제를 모아 큰 문제를 해결하는 방식 이 두 방식의 시간차이는 경우에 따라 다르게 때문에, 일단 둘중에 하나를 먼저 골라서 공부하면서 익숙해지는 것이 중요하다고 한다. 기본적으로는 스택오버플로우와 같은 문제가 발생한다면 이는 시간차이라기보다는 코드의 문제일 가능성이 크기 때문에 일단 기초적인 수준에서는 둘중 하나를 중점적으로 공부하는 것이 중요하다는 것! 다이나믹 문제 풀이의 전략으로는 "문제에서 구하려는 ..