Hacker News 의견

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

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

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

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

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

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

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

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

• 동적 프로그래밍은 블랙 매직이 아니다라는 글에 대한 링크를 공유함.

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

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

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

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

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

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

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

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

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

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

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