타뷸레이션

파이썬 알고리즘 인터뷰 23장 다이나믹 프로그래밍(DP)

오늘 TIL 3줄 요약 최적 부분 구조 - 문제의 최적 해결방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제 DP 알고리즘을 이용하면 최적 부분 구조를 갖고있는 문제를 풀이할 수 있다. 최적 부분 구조를 푸는 또 다른 알고리즘으로는 그리디 알고리즘이 있다. 그리디는 그 순간에 최적이라 생각하는 것을 선택하며 풀이 DP는 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해 나간다. 중복되지 않은 문제들은 DP로 풀지 않고 병합정렬, 퀵 정렬 등을 이용해 분할정복으로 풀어나간다. 다익스트라 알고리즘은 최적 부분 구조, 중복된 하위 문제들, 탐욕 선택 속성을 모두 갖는 알고리즘이다. TIL (Today I Learned) 날짜 2020 11. 12. FRI 오늘 읽은 범위 파이썬 알고리즘 인터뷰 ..