다이나믹 프로그래밍
-
[Java] 백준 1003 피보나치 함수Programming/Algorithm 2021. 3. 24. 21:30
문제 0이상 40이하의 정수가 주어질 때, 해당 숫자를 가지고 피보나치 함수를 호출한다. 이 때 n이 0과 1에 다다르는 횟수를 출력하는 문제이다. 문제에서 요구하는 바를 재귀로 구현하게 되면 40 level의 트리가 만들어지게 되고 O(40!)이라는 시간 복잡도가 나오게된다. (0.25초 안에 당연히 통과 불가) 따라서 만들어질 수 있는 수들의 규칙을 찾아서 점화식을 만들어야 한다. N = 0 1 0 N = 1 0 1 N = 2 1 1 N = 3 2 1 위의 숫자를 토대로 0의 개수, 1의 개수를 각각 담는 DP 배열을 만들 수 있다. N 0 1 2 3 4 [0의 개수] 1 0 1 1 2 [1의 개수] 0 1 1 2 3 코드 import java.io.BufferedReader; import java...
-
[Java] 백준 12852 1로 만들기 2Programming/Algorithm 2021. 3. 24. 01:37
문제 숫자 N이 주어지고, 가능한 연산은 3가지가 주어진다. 3으로 나누어 떨어진다면 3으로 나누기, 2로 나누어 떨어진다면 2로 나누기, 1을 빼기. 이 때 최소의 연산 횟수로 1을 만든다고 할 때 최소 연산 횟수와 해당 경우에 사용되는 숫자를 출력하는 문제. 풀이 기존의 '1로 만들기' 문제에서 사용되는 숫자를 출력하는 로직만 넣어주면된다고 생각했다. 처음엔 MAP 자료구조를 이용해서 DP의 인덱스 값을 KEY로 해당 인덱스를 만들어주기 위한 숫자들을 VALUE로(ArrayList)로 저장하게끔 했다. 통과는 했다. 하지만 다른 분들의 답안을 보고 int 배열을 둔 뒤 재귀 호출로 출력하는 방식이 있다는 것을 발견했다. 처음에 푼 풀이보다 시간이 10분의 1로 줄어들었다. 코드 import java...
-
[Java] 백준 11726 2 x n 타일링Programming/Algorithm 2021. 3. 19. 11:12
문제 2 x n 크기의 직사각형을 채우는 경우의 수를 출력한다 사용할 수 있는 타일의 크기 - 1 x 2 - 2 x 1 풀이 - dp[i]는 2가지 타일을 사용해서 2 x i 직사각형을 채울 수 있는 방법의 수이다. - 2 x i를 만들 수 있는 경우의 수는 다음의 두 경우를 더한 값이다. - 2 x (i - 1)까지 만든 타일 + [2x1타일] - 2 x (i - 2)까지 만든 타일 + [1x2타일+1x2타일] - 이것을 점화식으로 나타내면, dp[i] = dp[i-1] + dp[i-2] 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class b11726__2 { ..
-
[Java] 백준 2579 계단 오르기Programming/Algorithm 2021. 3. 10. 20:38
문제 계단을 밟으면 해당 계단에 쓰인 점수를 얻을 수 있다고 할 때, 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 규칙 - 한 번에 1계단 or 2계단 - 연속 3계단 불가능 - 시작점은 계단 아님 - 도착점은 반드시 밟기 풀이 현재 위치가 n번째 계단이라고 할 때, n번째 계단에서 얻을 수 있는 점수의 최댓값을 생각해보자. 연속 3칸을 밟은 것은 불가능하기 때문에 고려해야할 경우는 2가지이다. 1) n-2번째 계단을 밟은 뒤 n번째 계단을 밟은 경우 - dp[n-2] + scores[n] 2) n-3번째 계단을 밟은 뒤 n-1번째 계단을 밟고 n번째 계단을 밟은 경우 - dp[n-3] + scores[n-1] + scores[n] 즉, 다음의 두 가지 경우 중 큰 값으로 dp[n]을 초기화 시키면 ..