코딩 테스트/다이나믹 프로그래밍11 [백준 15486번] 동전 1 문제풀이 이전에 풀던 문제는 다이나믹 프로그래밍을 이용해 최소 개수나 최대 개수를 구하는 것이었는데, 이 문제는 경우의 수를 구하라는 면에서 달랐다. 다이나믹 프로그래밍을 이용해 어떻게 값을 저장해야 좋을지 고민하였다. 가치 k가 되는 경우의 수 문제를 가치 i (1 2023. 8. 1. [백준 15486번] 퇴사 2 문제풀이 날짜당 걸리는 시간과 받을 수 있는 가격을 저장한 후, 다이나믹 프로그래밍을 통해 1번째날부터 받을 수 있는 가장 큰 값을 저장한다. import sys n = int(sys.stdin.readline()) time = [0 for i in range(n)] price = [0 for i in range(n)] max_price = [0 for i in range(n+1)] for i in range(n): # 시간과 가격 입력 받기 time[i], price[i] = map(int, sys.stdin.readline().split()) for i in range(n): if i + time[i] < n + 1: max_price[i + time[i]] = ma.. 2023. 7. 31. 다이나믹 프로그래밍 개념 한번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘으로, 피보나치 수열이 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시이다. 피보나치 수열의 점화식을 재귀 함수를 이용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다이나믹 프로그래밍은 조건은 이렇다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 다이나믹 프로그래밍 적용 안한 케이스 def fibo(x): if x==1 or x==2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) 다이나믹 프로그래밍 적용한 케이스.. 2023. 7. 23. 이전 1 2 3 다음
