결국 빛나리라

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net > 다이나믹 프로그래밍 아래 그림과 같은 규칙을 생각하면 풀 수 있었던 문제이다. 규칙을 코드로 작성하면 다음과 같다. + 계단의 개수가 하나인 경우에 if절을 넣어주지 않으면 dp[2]를 구하는 과정에서 인덱스 에러가 나기 때문에 if문을 통해 하나인 경우를 고려해주어야 한다.

1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net > 다이나믹 프로그래밍 7부터 시작하여 아래 그래프로 내려가며 최대가 되는 수를 찾는 문제이다. 위부터 아래로 내려오며 더한 값들이 최대가 되도록 하는 방법을 사용했다. 더한 값들이 최대가 되기 위해선 수에 더할 윗 값들 중 더 큰 수를 더할 수 있을 것이다. 한 행에서 맨 앞에 위치한 수나 맨 마지막에 위치한 수의 경우 위의 줄에서 더할 수 있는 수가 하나밖에 없으므로 다음 그림과 같이 그릴 수 있다. 해당 그림대로 수를 더해보면 다음과 같다. 맨 아래 줄에서 최대값인 30이 7에서..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 다이나믹 프로그래밍이란? 메모리를 적절히 사용하여 수행시간의 효율성을 향상시키는 방법이다. 즉 한번 계산된 결과는 별도 메모리 영역에 저장해 다시 계산하지 않도록한다. 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용한다. 1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있어 작은 문제를 모아 큰 문제를 해결할 수 있을 때 2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 때 현재 주어진 문제가 다이나믹 프로그래밍 유형인지 아닌지 고민하여 파악한느 것이 중요하다. 문제를 보고 위의 조건들..