동적 계획법이란? 동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 여러 개의 하위 문제(subproblem)로 나누어 푸는 알고리즘 기법 중 하나입니다. DP는 부분 문제의 결과 값을 저장해놓고 재활용하여 전체 문제를 해결하는 방식으로 동작합니다. 동적 계획법의 조건 DP는 크게 2가지 조건을 만족해야 합니다. 작은 부분 문제들이 반복되어 나타나는 구조여야 합니다. 한 부분 문제에서의 정답이 다른 부분 문제에서의 정답을 결정하는 데 영향을 미쳐서는 안 됩니다. 동적 계획법의 절차 DP 알고리즘은 일반적으로 다음과 같이 세가지 절차를 따릅니다. 주어진 문제를 작은 부분 문제로 분할합니다. 부분 문제의 해결을 위해 이전 단계에서 구한 값을 저장하고 재귀로써 문제를 해결합니다...
파이썬에서는 딕셔너리로 이미 구현이 되어있는 해쉬테이블을 굳이 구현해보겠습니다. 개인적인 이해를 위한 글이니 재미있게(?) 봐주셨으면 합니다. 해쉬테이블(Hash table) 해쉬테이블은 키(Key)에 데이터(Value)를 저장하는 데이터 구조입니다. 나열의 구조인 스택이나 큐와는 다르게 Key를 통해 바로 데이터를 받아올 수 있습니다. 다루기 편하고 검색 속도가 엄청나게 빨라진다는 장점이 있습니다. 파이썬에서는 딕셔너리로 구현이 되어있고 다른 언어는 공간을 확보하고 해쉬테이블을 사용하지만 파이썬은 그럴 필요는 없습니다. 해쉬테이블은 Key-Value의 함수역할을 하는 해싱 함수를 통해 데이터를 반환하는 방식입니다. 즉, 해싱함수를 h라 할 때h(Key)=Value가 됩니다. 함수역할을 하긴 하지만 va..