동적계획법

[백준 알고리즘][파이썬/Python] 2293번: 동전 1

문제 시간 제한 : 0.5 초 (추가 시간 없음), 메모리 제한 : 4 MB n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2 ³¹ 보다 작다. 입출력 예 제출 코드 n, k = map(int, input().split()) c = ..

[파이썬/Python] 재귀함수(Recursive function)와 메모이제이션(Memoization)

재귀함수(recursive function)란 함수 내부에서 자기 자신(함수)을 다시 호출하는 함수이다. 잘만 활용하면 참 좋다고 생각하는데, 가장 중요한 탈출 조건을 생각해내는 것이 상당히 까다로운 편이라 권장되지는 않고 있다. 또한, 재귀함수만 이용할 경우 과도하게 스택메모리를 이용하게 되고 탈출 조건을 잘못 세울 경우 스택오버플로우 에러가 발생할 위험도 존재한다. 그래서 동적 프로그래밍(Dynamic Progrmming)처럼 재귀함수의 각 단계 결과값을 저장하여 성능을 높여주는 방법도 존재한다. 우선 재귀함수의 예시를 두 개 들어보자. 1. 팩토리얼 구하기 일반적인 for문을 이용하여 팩토리얼을 구하면 다음과 같은 코드를 짤 수 있다. def factorial_for(n): if n == 0 or ..