다이나믹 프로그래밍

[백준 - Python] 2579번 : 계단 오르기

🌱 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 💡 설명 필자는 해당 문제를 BFS로 해결하려 했으나 채점 7% 에서 메모리 초과가 발생하였습니다. 아무리 n이 300이라고 해도 주어진 메모리가 128MB인 상황에서 메모리를 많이 요구하는 BFS로 문제를 해결하기에는 문제가 있어 보였습니다. 다음 방법으로 다이나믹 프로그래밍(DP)로 접근을 시도하였습니다. Memoization 기법을 통해 이전에 구한 최적값(해당 층까지 구한 최대 스코어)을 dp..

[백준 - Python] 2839번 : 설탕 배달

🌱 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 💡 설명 해당 문제는 다이나믹 프로그래밍 또는 그리디 알고리즘을 요구하는 문제입니다. 우선 다이나믹 프로그래밍으로 풀이가 가능한지 확인하기 위해서는 2가지 조건이 있습니다. 1. 최적 부분 구조 (Optimal substructure) 2. 중복 부분 문제 (Overlapping subproblems) 즉, 큰 문제 상황을 작게 나누어서 해결하고자 할 때, 중복되는 상황이 발생 하며, 작게 나눠진 ..

[백준/파이썬] 1003번 문제 '피보나치 함수'

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)..