다이나믹프로그래밍 (2) 썸네일형 리스트형 DP(다이나믹 프로그래밍): 백준 1463 파이썬 문제: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이: 이 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다. 예를 들어 n=6일 때, 함수가 호출되는 과정을 보면 다음과 같을 것이다. 확인해보면, 마찬가지로 f(2)와 같은 함수들이 동일하게 여러 번 호출되는 것을 알 수 있다. 이 문제에서 동일한 함수에서 구하는 값들은 동일해야 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다. 이제 문제에서 요구하는 내용을 점화식으로 표현해보자. 점화식 끝에 1을 더해주는 이유.. 다이나믹 프로그래밍(동적 계획법) 다이나믹 프로그래밍: 중복되는 연산을 줄이자 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법이다. 다이나믹 프로그래밍(Dynamic Programming) 기법은 동적 계획법이라고 표현하기도 한다. 다이나믹 프로그래밍에 대해 알아보기 전에 기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문제를 살펴보자. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치수열은 다음과 같은 형태로 끝없이 이어진다. 수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게.. 이전 1 다음
