dp8 백준 2579번 파이썬 | 계단 오르기 (DP) 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 .. 2020. 11. 2. 백준 1463번 파이썬 | 1로 만들기 (DP) 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 1로 만들기는 대표적인 DP가 쓰이는 문제이다. 그리디의 1로 만들기도 있지만 이 문제의 경우 무조건 나눈다고 최적의 해를 얻는게 아니다. 따라서 매 경우 min을 따로 구해서 계산하면 된다. 점화식은 2 이상일때 d[i]=d[i-1 or i//2 or i//3] +.. 2020. 11. 1. 백준 1003번 파이썬 | 피보나치 함수 (DP) 문제 fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 0을 출력하고, 0을 리턴한다. fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다. 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다. fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다. 1은 2번 출력되고, 0.. 2020. 11. 1. 다이나믹 프로그래밍 DP 다이나믹 프로그래밍 = 동적 계획법 = DP -메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 -이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. -다이나믹 프로그래밍의 구현은 일반적으로 탑다운, 바텀업 방식으로 구성된다. (일반적인 프로그래밍에서의 동적: 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당). 여기서는 다른 의미로 쓰인다. 조건 1.최적 부분 구조 (optimal substructure) -큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답이 모이면 큰 문제를 해결할 수있다. 2.중복되는 부분 문제(Overlapping subproblem) -동일한 작은 문제를 반복적으로 해결 예시 *점화식 : 인접한 항들 사이의 .. 2020. 11. 1. 이전 1 2 다음
