반응형
다이나믹이 뭐예요?
-
[백준] 14494 다이나믹이 뭐예요? with PythonPS 2022. 7. 14. 23:07
📌 BOJ 14494 다이나믹이 뭐예요? 💡 조건 다이나믹 프로그래밍(동적 계획법), 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 (= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션.) 반복되는 똑같은 연산 횟수를 줄이는 것. 다차원 배열로도 가능하다. 오른쪽, 아래쪽으로만 움직일 수 있을 때, D[1][1]에서 D[x][y]까지 도달하는 경우의 수를 구하는 문제는 일일히 모든 경우를 다 계산할 필요 없이, D[i][j] = (i, j)에 도달하는 누적 경우의 수 = D[i-1][j] + D[i][j-1]를 세워서 해결할 수도 있다. →, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 때, 왼쪽 위 (1..