CodingTest/다이나믹 프로그래밍 6

병사 배치하기

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 기본 아이디어는 가장 긴 증가하는 부분 수열(LIS) 예를들어 array = {4,2,5,8,4,11,15} 가장 긴 증가하는 부분 수열은 {4,5,8,11,15} [Step 0] 우선 값이 1이 될 수 있도록 모두 1로 초기화한다. [Step 1] 2부터 시작한다. 앞에 4라는 인덱스가 1개존재한다. 점화식에 의해 4는 2보다 크므로 그대로 유지한다. [Step 2] i = 2일 경우를 살펴보자 인덱스2의 값인 5를 확인한다. 4와 비교했을때 5가 크므로 4의 값에 1을 더해 2가된다. 인덱스1의 값인 2를 비교했을때 1

금광

1. 문제 설명 2. 문제 조건 n은 3, m은 4 1 3 3 2 2 1 4 1 0 6 4 7 형태로 되어있다. 3. 문제 해결 아이디어 금광의 모든 위치에 대하여 다음의 세 가지만 고려 1. 왼쪽 위에서 오는 경우 2. 왼쪽 아래에서 오는 경우 3. 왼쪽에서 오는 경우 세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결한다. 이때 테이블에 접근할 때마다 리스트의 범위를 벗어나지 않는지 체크해야 한다. 4. 답안 #테스트 케이스 입력 for tc in range(int(input())): #금광 정보 입력 n, m = map(int, input().split()) array = list(map(int, input().split())) #DP 테이블 초기화 dp = [..

효율적인 화폐 구성

1. 문제 설명 2. 문제 조건 2가지(N)으로 총합 15(M)을 만들기 위해 2원화폐와 3원화폐 3가지(N)으로 총합 4(M)을 만들기 위해 3,5,7원 화폐 3. 문제 해결 아이디어 [Step 0] N = 3, M = 7이고, 각 화폐의 단위가 2, 3, 5인 경우를 확인 초기화 작업 먼저 각 인덱스에 해당하는 값으로 INF(무한)의 값을 설정 INF는 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다라는 의미 10,001을 사용가능 1~7까지는 만들수 없는 무작위의 값을 설정 인덱스(0) = 0원을 만들기 위한 최소한의 화폐 개수는 0 [Step 1] 첫 번째 화폐 단위인 2를 확인한다. 점화식에 따라서 다음과 같이 리스트가 갱신된다. 인덱스 2원을 만들 수 있는건 1개 인덱스 4원을 만들 수 ..

1로 만들기

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 피보나치 수열 문제를 도식화한 것처럼 함수가 호출되는 과정을 그림으로 그리면 이와같다. 최적 부분 구조와 중복되는 부분 문제를 만족 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 적용할 수 있다. 4. 답안 x = int(input()) d = [0] * 30001 #바텀 업방식 for i in range(2, x + 1): #현재의 수에서 1을 빼는 경우 d[i] = d[i - 1] + 1 #현재의 수가 2로 나누어 떨어지는 경우 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) #현재의 수가 3으로 나누어 떨어지는 경우 if i % 3 == 0: d[i] = min(d[i], d[i /..

개미 전사

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 N = 4일 때, 다음과 같은 경우들이 존재할 수 있다. 식량을 선택할 수 있는 경우의 수는 다음과 같이 8가지이다. 7번째 경우에서 8만큼의 식량을 얻을 수 있으므로 최적의 해는 8이다. i는 인덱스이므로 0부터 시작한다. 창고 0만 있을 때는 a(o) = 1이 최대 값 창고 0,1만 있을 때는 a(1) = 3이 최대 값 창고 0,1,2만 있을 때는 a(2) = 3이 최대 값 모든 창고일때는 창고1, 3 = 8이 최대 값 이렇게 DP 테이블 값을 재정의한다. 왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정 위 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다. 즉, i..

다이나믹 프로그래밍 개요 (피보나치 수열)

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록한다. 다이나믹 프로그래밍(동적 계획법)의 구현은 일반적으로 두 가지 방식(탑다운과 바텀업)으로 구성 동적(Dynamic)이란? 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 다이나믹 프로그래밍에서 다이나믹은 별다른 의미가 없다. 1. 다이나믹 프로그래밍의 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제(Overlapping Subproblem) ..