다이나믹프로그래밍

문제 링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 문제 풀이 n = int(input()) array = list(map(int, input().split())) dp = [1]*n for i in range(n): for j in range(i): if array[i] > array[j]: dp[i] = max(dp[i], dp[j] + 1) prin..

문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 문제 풀이 i가 현재 숫자, j가 i보다 작은 제곱수들일 때, dp[i - j] 중 가장 최소항의 개수가 작은 것을 찾아낸다. 이 값에 1을 더해주면 i의 최소항의 개수가 나타난다. (1을 더해주는 이유는 제곱수에 대한 항의 수를 추가하기 위해서이다.) 점화식 => dp[i] = min(dp[i - j]) + 1 n = int(input())..

문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 문제 풀이 전형적인 DP 방식으로 풀리는 문제이다. 주의해야 할 점은 현재 계단(i), 바로 아래 계단을 오를 경우 두 계단을 연속으로 올랐기 때문에 i - 3까지의 최댓값에 두 계단의 값을 더해야 한다는 점이다! n = int(input()) array = [0] * 300 for i in range(n): array[i] = int(input()) dp = [0] * 300 dp[0] = ..

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 설명 문제 풀이 0 1 2 3 4 0 50 10 100 20 40 1 30 50 70 10 60 이 문제는 패턴이 잘 눈에 띄지 않아서 어려웠는데, 결과적으로 굉장히 간단한 패턴을 찾을 수 있다. 예를 들어, dp[0][2]를 선택하고 싶을 경우 앞에서는 dp[1][0] 혹은 dp[1][1]을 선택해야 하는데 둘 중 큰 것을 선택해야만 한다. dp[1][2]를 선택하고 ..

문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 문제 풀이 Dynamic Programming 문제이다. dp 테이블에 모든 원소를 0으로 초기화시켜준 후 하나씩 반복하여 계산을 하는 것이다. DP는 처음에는 이해가 잘 안되는데 생각해보면 간단하다. 예를 들어 4에 대한 연산의 결과를 생각해보자. 4는 4 -> 2 -> 1 의 연산을 하게된다. 그런데 이걸 하나씩 매번 해줄 필요가 없다. 2에 대한 연산의 횟수(DP(2))에 2를 도출해낸 연산(나누기 2) 한 번(+1)을 카운트해주면 DP[4] = DP[2] + 1이 된다. 이와 같은 ..

다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 조건) 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션 기법 (캐싱) 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 # 피보나치 수열 소스코드 - 메모이제이션의 예 [탑다운] # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍) def fibo(x): # 종료 조건(1 혹은 2일 때 1을 반환) if x ==..