# 다이내믹 프로그래밍, 흑마법이 아니다

> Clean Markdown view of GeekNews topic #12872. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=12872](https://news.hada.io/topic?id=12872)
- GeekNews Markdown: [https://news.hada.io/topic/12872.md](https://news.hada.io/topic/12872.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-01-15T12:35:53+09:00
- Updated: 2024-01-15T12:35:53+09:00
- Original source: [qsantos.fr](https://qsantos.fr/2024/01/04/dynamic-programming-is-not-black-magic/)
- Points: 2
- Comments: 1

## Topic Body

### 동적 프로그래밍은 마법이 아니다

- 동적 프로그래밍은 복잡한 문제를 해결하는 데 사용되는 기술로, 작은 문제들로 분할하여 접근하는 방식.
- 이 기술은 자연스러운 것이며, 많은 일반적인 알고리즘들이 특정 문제에 동적 프로그래밍을 적용한 것임.
- 동적 프로그래밍에 대한 이해를 돕기 위해, 더 쉬운 소개와 상세한 설명을 제공함.

### 불평

- 소프트웨어 엔지니어링은 명명에 있어서 형편없는 경우가 많음.
- '부트스트랩', '데몬', '캐스케이딩 스타일 시트', '쿠키', '인공 지능' 등의 용어들이 모호하거나 오해의 소지가 있음.
- '동적 프로그래밍'이라는 용어도 그 자체로는 '동적'과 관련이 없으며, 실제로는 알고리즘 설계에 사용되는 아이디어임.

### 기본 캐싱

- 작은 유사한 문제들로 문제를 나누어 해결하려 할 때, 같은 작은 문제들을 여러 번 해결해야 할 수 있음.
- 피보나치 수열의 예시를 들면, 간단한 재귀 함수로 구현하면 같은 계산을 여러 번 반복하게 됨.
- 결과를 캐시(또는 메모이제이션)하여 중복 계산을 피할 수 있음.

### 최적화된 캐싱

- 메모이제이션을 사용하면 재귀를 유지하되, 필요한 것을 필요할 때마다 계산함.
- 대신, 필요한 모든 것을 미리 계산하는 방식으로 접근할 수 있음.
- 이 방식은 재귀 호출 없이 문제를 해결하며, 이것이 바로 동적 프로그래밍임.

### 편집 거리

- 두 문자열 사이의 편집 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 횟수임.
- 편집 거리는 문자 교체, 삽입, 삭제를 포함하여 계산할 수 있으며, 이는 동적 프로그래밍을 사용하여 효율적으로 해결할 수 있음.
- 작은 문제들의 해결책에서 전체 해결책을 도출하는 방법을 찾아야 함.

### Advent of Code, Day 12

- 2023년 12월 12일의 Advent of Code 문제에서는 1D 노노그램을 해결해야 함.
- 무차별 대입 방식으로 해결할 수 있지만, 지수적 복잡도를 가짐.
- 대신 동적 프로그래밍을 적용하여 효율적으로 해결할 수 있음.

### 결론

- 동적 프로그래밍은 쉽지 않지만, 대부분의 프로그래머에게 도달할 수 없는 것은 아님.
- 문제를 작은 문제로 나누는 방법을 이해하면, 메모이제이션을 다양한 상황에서 사용할 수 있으며, 이는 순진한 구현보다 큰 개선을 의미함.
- 동적 프로그래밍을 마스터하면, 전체 알고리즘 클래스를 이해하고, 트레이드오프를 더 잘 이해하며, 다른 최적화를 가능하게 함.

#### GN⁺의 의견

- 동적 프로그래밍은 복잡한 문제를 효율적으로 해결하기 위한 중요한 기술로, 재귀적 접근 대신 작은 문제의 해결책을 캐싱하여 중복 계산을 줄임으로써 성능을 크게 향상시킬 수 있음.
- 이 기사는 동적 프로그래밍의 기본 개념을 이해하고 싶어하는 초급 소프트웨어 엔지니어들에게 매우 유익함.
- 피보나치 수열과 편집 거리 예시는 동적 프로그래밍의 개념을 이해하는 데 도움이 되며, 실제 문제 해결에 적용할 수 있는 좋은 출발점을 제공함.

## Comments



### Comment 22269

- Author: neo
- Created: 2024-01-15T12:35:53+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=38988948) 
- 기사가 동적 프로그래밍(DP) 알고리즘을 재귀의 캐싱으로 설명하는 것은 좋은 점임.
  - 재귀적 해결책을 찾는 것이 DP 해결책을 찾는 시작점으로 최적임.
  - 재귀적 해결책을 메모이제이션(memoization)하면 속도 향상에 큰 도움이 될 수 있음.
  - 중요한 것은 호출 트리에 많은 수의 하위 문제가 있는 것이 아니라, 상대적으로 적은 수의 **독특한** 하위 문제가 있어야 한다는 점임.

- 기사가 먼저 재귀적으로 문제를 다루고 점차 캐싱을 추가한 다음 필요한 캐시 크기만큼 줄이는 방식을 좋아함.
  - 동적 프로그래밍 해결책을 직접 찾으려고 하다가 막히거나 큰 노력이 필요했던 경험이 있음.
  - 앞으로는 순서대로 접근하는 방식을 강제할 것임.

- 동적 프로그래밍의 멋진 응용 중 하나는 핵산/단백질 서열의 쌍별 정렬임.
  - 예를 들어, [시퀀스 정렬](https://en.wikipedia.org/wiki/Sequence_alignment), [니들먼-운슈 알고리즘](https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm), [스미스-워터맨 알고리즘](https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm) 등이 있음.

- 매우 뛰어난 알고리즘 교수님에 대한 경험을 공유함.
  - 교수님은 UCLA에서 공부하셨고, 동적 프로그래밍에 대한 수업이 탁월했음.
  - 간단하지만 지수적 복잡도를 가진 문제로 시작하여 문제를 작은 문제로 나누고 복잡도를 다항식으로 줄인 후 메모이제이션을 적용하여 선형 복잡도로 떨어뜨림.
  - 사용된 문제들을 기억하고 싶음.

- [동적 프로그래밍은 블랙 매직이 아니다](https://web.archive.org/web/20240114111200/https://qsantos.fr/2024/01/04/dynamic-programming-is-not-black-magic/)라는 글에 대한 링크를 공유함.
  - 해당 글이 많은 접속으로 인해 접근이 어려워짐(허그 오브 데스).

- 주로 독학으로 프로그래밍을 배운 사람이 직장을 찾을 때 면접에서 동적 프로그래밍을 사용하라고 하면 몰랐을 것이라고 함.
  - 다행히 그런 일은 없었고, 기술을 알고 있어서 여러 면접에서 사용함.

- "동적 프로그래밍"이라는 이름이 프로그래밍 분야에서 나온 것처럼 보이지 않을 수 있음.
  - 실제로는 최적화와 관련이 있으며, 이산 시간에 대한 결정 문제를 해결하는 방법임.
  - 동적 프로그래밍은 값 함수 V*를 정의하여 최적화 문제의 차원을 크게 줄이는 방법임.

- "동적 프로그래밍"을 들었을 때 "메모이제이션"만 생각하는 것이 잘못된 것인지에 대한 의문을 제기함.
  - 메모이제이션을 효과적으로 사용하기 위해 문제를 영리하게 분할하는 것이 빠진 부분일 수 있음.

- 동적 프로그래밍이 블랙 매직이 아니라, 그것을 동적으로 프로그래밍할 수 있음을 증명하고 그 정확성을 증명하는 것이 어려움.
  - 수학적 귀납법을 사용하여 그리디 알고리즘과 마찬가지로 정식 증명이 필요함.

- 동적 프로그래밍을 마스터하기 위해 DPV 알고리즘 책과 조지아 공과대학의 유다시티 강의를 추천함.
  - 문제를 풀어보는 연습을 통해 동적 프로그래밍을 익힐 수 있음.