알고리즘/동적 계획법2 [알고리즘] algosopt - 여행 짐 싸기 (동적계획법) 여행 짐 싸기 문제 정보 시간 제한 메모리 제한 2000ms 65536kb 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다. 물건 노트북 컴퓨터 카메라 XBOX365 커피그라인더 아령 백과사전 부피 4 2 6 4 2 10 절박도 7 10 6 7 5 4 캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 w 이하여야 합니다. 이때 .. 2022. 4. 1. [알고리즘] 다이나믹 프로그래밍 정의 중복되는 연산을 줄이기 위하여 메모리 공간을 최대한 활용하여 연산 속도를 증가시키는 방법이다. 다이나믹 프로그래밍(dynamic programming)이라 표기하고 한국어 표기로는 "동적 계획법" 이라고 한다. 방식 탑다운 방식 (메모이제이션 활용) 보텀업 방식 구현 예시로 피보나치 수열이 있다 탑다운 방식 def fibo(x): if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = fibo(x - 1) + fibo(x - 2) return d[x] d = [0] * 100 answer = fibo(99) print('answer: {}'.format(answer)) # answer: 218922995834555169026 보텀업 방식 de.. 2020. 11. 8. 이전 1 다음 728x90 반응형
