n = int(input()) k = list(map(int, input().split())) d = [0]*100 # 식량창고 개수 d[0] = k[0] d[1] = max(k[0], k[1]) # (i-1)번째 창고를 털면 i를 털 수 없음 = d(i-1) # (i-2)번째 창고를 털면 i를 털 수 있음 = d(i-2)+k[i] # 둘 중 더 큰 곳을 찾으면 됨 for i in range(2, n): d[i] = max(d[i-1], d[i-2]+k[i]) # print(f'd[{i}] = max({d[i-1]}, {d[i-2]+k[i]})') print(d[n-1])
8-1. 다이나믹 프로그래밍
다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과는 메모리에 저장하여 다시 계산하지 않도록 한다. DP의 구현은 탑다운(위에서 아래로), 보텀업(아래서 위로)으로 구성된다. 동적 계획법이라고도 한다. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있다. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야 한다. DP 대표문제 (피보나치 수열) 1 1 2 3 5 8 13 21 34 55 ... 이 수열에서 알아낸 항들 사이의 관계식을 점화식이라고 한다. 계산되는 과정을 나타내는 표를 배열이나 리스트로 표현할 수 있다. 점화식으로 표현될 수 있는 구조는 재귀함수를 이용해 프로그램 상에 ..
x = int(input()) d = [0]*30001 for i in range(2, x+1): # 1로 만드니까 2부터시작 d[i] = d[i-1]+1 # 가정 (최소연산횟수) if i % 2 == 0: d[i] = min(d[i], d[i//2]+1) # 2로 나누어 떨어졌을때나, 1을 뺀값중에 더 작은 값을 넣음 if i % 3 == 0: d[i] = min(d[i], d[i//3]+1) if i % 5 == 0: d[i] = min(d[i], d[i//5]+1) print(d[x])
이진 탐색 알고리즘 순차 탐색: 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법 이진 탐색: 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (시작점, 끝점, 중간점을 이용하여 탐색 범위 설정) 이진 탐색 소스코드: 재귀적 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start+end)//2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array, target, start, m..
n, m = map(int, input().split()) length = list(map(int, input().split())) # 최적의 수(=h)를 찾기 위해 이진탐색을 해야 함 start = 0 end = max(length) # 떡 중에 가장 긴 떡 h = 0 while start mid: # 떡이 mid보다 길면 자름, 안 길면 못 자름 total += i - mid # 잘린 떡 합하기 if total < m: # 반토막내면서 자르다가 떡이 m보다 부족해지면 끝점을 감소시킴 (더 자른다) end = mid-1 else: # 잘린 떡의 합이 m보다 크거나 같을 때 # 떡이 아직 m보다 크면 시작점을 늘림 (덜 자른다) h = mid # 최적의 h를 구하므로 기록해두고 start = mid+1 ..