GN⁺: 다이내믹 프로그래밍, 흑마법이 아니다

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

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

불평

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

기본 캐싱

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

최적화된 캐싱

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

편집 거리

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

Advent of Code, Day 12

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

결론

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

GN⁺의 의견

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

[neo]

Hacker News 의견

• 기사가 동적 프로그래밍(DP) 알고리즘을 재귀의 캐싱으로 설명하는 것은 좋은 점임.

  • 재귀적 해결책을 찾는 것이 DP 해결책을 찾는 시작점으로 최적임.
  • 재귀적 해결책을 메모이제이션(memoization)하면 속도 향상에 큰 도움이 될 수 있음.
  • 중요한 것은 호출 트리에 많은 수의 하위 문제가 있는 것이 아니라, 상대적으로 적은 수의 독특한 하위 문제가 있어야 한다는 점임.

• 기사가 먼저 재귀적으로 문제를 다루고 점차 캐싱을 추가한 다음 필요한 캐시 크기만큼 줄이는 방식을 좋아함.

  • 동적 프로그래밍 해결책을 직접 찾으려고 하다가 막히거나 큰 노력이 필요했던 경험이 있음.
  • 앞으로는 순서대로 접근하는 방식을 강제할 것임.

• 동적 프로그래밍의 멋진 응용 중 하나는 핵산/단백질 서열의 쌍별 정렬임.

  • 예를 들어, 시퀀스 정렬, 니들먼-운슈 알고리즘, 스미스-워터맨 알고리즘 등이 있음.

• 매우 뛰어난 알고리즘 교수님에 대한 경험을 공유함.

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

• https://qsantos.fr/2024/01/04/dynamic-programming-is-not-black-magic/">동적 프로그래밍은 블랙 매직이 아니다라는 글에 대한 링크를 공유함.

  • 해당 글이 많은 접속으로 인해 접근이 어려워짐(허그 오브 데스).

• 주로 독학으로 프로그래밍을 배운 사람이 직장을 찾을 때 면접에서 동적 프로그래밍을 사용하라고 하면 몰랐을 것이라고 함.

  • 다행히 그런 일은 없었고, 기술을 알고 있어서 여러 면접에서 사용함.

• "동적 프로그래밍"이라는 이름이 프로그래밍 분야에서 나온 것처럼 보이지 않을 수 있음.

  • 실제로는 최적화와 관련이 있으며, 이산 시간에 대한 결정 문제를 해결하는 방법임.
  • 동적 프로그래밍은 값 함수 V*를 정의하여 최적화 문제의 차원을 크게 줄이는 방법임.

• "동적 프로그래밍"을 들었을 때 "메모이제이션"만 생각하는 것이 잘못된 것인지에 대한 의문을 제기함.

  • 메모이제이션을 효과적으로 사용하기 위해 문제를 영리하게 분할하는 것이 빠진 부분일 수 있음.

• 동적 프로그래밍이 블랙 매직이 아니라, 그것을 동적으로 프로그래밍할 수 있음을 증명하고 그 정확성을 증명하는 것이 어려움.

  • 수학적 귀납법을 사용하여 그리디 알고리즘과 마찬가지로 정식 증명이 필요함.

• 동적 프로그래밍을 마스터하기 위해 DPV 알고리즘 책과 조지아 공과대학의 유다시티 강의를 추천함.

  • 문제를 풀어보는 연습을 통해 동적 프로그래밍을 익힐 수 있음.