![]()
1. 동적 계획법이란? 동적 계획법(Dynamic Programming)은 주어진 문제를 작은 부분 문제로 분할하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다. 특히 부분 문제의 수가 기하급수적으로 증가할 때 유용하다. 분할 정복법과는 달리, 중복되는 부분 문제의 결과를 재활용하여 속도를 높인다.각 부분 문제가 서로 독립적일 때: 분할 정복법 사용.부분 문제가 중복될 때: 동적 계획법 사용.2. 메모이제이션이란?메모이제이션(Memoization)은 계산 결과를 저장해두고, 동일한 계산이 다시 필요할 때 저장된 값을 사용하는 최적화 기법이다. 이를 통해 중복 계산을 방지하고 속도를 향상시킬 수 있다. 메모리를 사용해 계산 시간을 줄이는 방식이다.3 - 1. 메모이제이션의 활용: 이항 계수..
![]()
문제 링크 문제 설명 현대모비스에서 전기차로 경사로 주행 테스트를 하려고 합니다. 경사로 테스트는 n×m 크기의 격자 형태의 공간에서 진행되며, 각 칸에 적힌 숫자는 높이를 나타냅니다. 전기차는 격자 내의 모든 칸에서 출발 가능하며, 상하좌우로 인접한 칸으로만 이동 가능하고 격자 밖을 벗어날 수는 없습니다. 전기차가 인접한 칸으로 이동하는 길의 경사는 이동하려는 칸의 높이에서 현재 칸의 높이를 뺀 값입니다. 예를 들어 높이가 5인 칸에서 7인 칸으로 이동하는 길의 경사는 2(= 7 - 5)이고, 높이가 6인 칸에서 높이가 1인 칸으로 이동하는 길의 경사는 -5(= 1 - 6)입니다. 경사 수열 d가 주어집니다. 경사 수열은 테스트에서 전기차가 이동할 길의 경사를 나타내며, d[i]는 전기차가 i+1번째로..
