Algorithm/개념정리

다이나믹 프로그래밍 (DP) - 접근 방법

2023.08.15

DP의 기본적인 개념정리는 아래에 적어두었습니다. 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 위의 문제 풀이를 진행했었습니다. 두가지 모두로 풀이를 진행하다 보니 [백준] 2579번 - 계단 오르기 (C++) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 jun-13.tistory.com 결론 위와 같은 결과가 나오게 되었는데 핵심만 정리를 해보자면 "그냥 제약조건이 없는 ..

Algorithm/개념정리

다이나믹 프로그래밍 (Dynamic Programming)

2023.08.09

다이나믹 프로그래밍 (Dynamic Programming)란. 앞자에 글자를 따서 dp 라고도 불리고 동적 계획법이라고도 불린다. "특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘" 알고리즘에서 주어진 문제에 접근하기위해 여러개의 하위문제의 풀이를 만들고, 그 풀이를 바탕으로 진행하여 최종적인 문제의 도달하는 알고리즘이라고 생각을 하면 된다고합니다. 위와 같은 설명으로는 dp를 처음 접하는 사람에서는 크게 와닿을 수 없는 이야기라서 간단하게 이야기를 하자면 문제를 해결하기 위한 점화식을 찾아낸 후 점화식을 바탕으로 하위문제부터 차례로 구해나가서 최종적인 답을도출해내는 형태의 알고리즘 으로 설명을 할 수 있다. 그래도 예제 없이는 이해하기가 힘들어 ..

다이나믹 프로그래밍 (DP) - 접근 방법

다이나믹 프로그래밍 (Dynamic Programming)

티스토리툴바