성덕이의 개발공간

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. 문제 설명 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) ..