728x90 DynamicProgramming3 [BOJ/Python] 2579. 계단 오르기 📌 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 📌 문제 접근 방법 첫 번째 칸을 밟는 경우, 최대값은 첫 번째 칸의 점수 두 번째 칸을 밟는 경우, 최대값은 첫 번째 칸 + 두 번째 칸의 점수 세 번째 칸을 밟는 경우, 첫 번째 칸 + (2칸 이동) 세 번째 칸 두 번째 칸 + (1칸 이동) 세 번째 칸 i번째 칸을 밟는 경우, i-3번째 칸 + (2칸 이동) i-1번째 칸 + (1칸 이동) i번째 칸 i-2번째 칸 + (1칸 이동) i번째 칸 .. 2021. 10. 8. [BOJ/Python] 1520. 내리막 길 📌 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 📌 문제 접근 방법 이것저것 내 생각으로 할 수 있는 모든 시도를 다 해본 것 같다! (그냥 dfs, 방문 체크 리스트를 아예 가지고 다니기 등등) 결국 포기하고 구글링..! dp를 활용해야 하는 문제였다. 출발점에서 시작해서 도착점까지 도달할 수 있다면, dp 리스트에 값을 + 해준다. 이를 다 체크하면, (0, 0)에는 출발점에서 도착점까지 갈 수 있는 경우의 수가 남는다. 📌 코드.. 2021. 10. 4. [Algorithm] DP (Dynamic Programming) 동적 계획 (DP; Dynamic Programming) 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결 Memoization 피보나치 수열을 재귀함수로 구현하는 경우 '엄청난 중복 호출이 존재한다'는 문제점이 있음 def fibo(n): if n < 2: return 2 else: return fibo(n-1) + fibo(n-2) 메모이제이션 (Memoization) 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 동적 계획법의 핵심이 되는 기술 앞의 예에서 fibo(n)의 값을 계산하자마자 저장하면(.. 2021. 10. 3. 이전 1 다음 728x90
