dfs1 [엘리스 AI 트랙 2기] Day 10 - 동적계획법, 그래프 동적계획법 정의 계산 복잡도가 큰 문제를 풀 때, 중복되는 문제는 풀지 않고 이전에 계산한 결과를 참조하여 중복 연산의 수를 줄여 빠르고 효율적으로 문제를 푸는 방식이다. 참조는 리스트의 인덱싱을 사용할 수도 있고 해시테이블(딕셔너리)를 사용할 수도 있다. 기저조건은 미리 딕셔너리나 리스트에 저장해두고 시작한다. 탑 다운 방식의 풀이 우리가 구하고자 하는 함수를 F라고 했을 때, F(n)의 값에서부터 f(n) = f(n-1) + f(n-2) 식으로 계속 내려와 기저조건까지 오는 방법이다. (딕셔너리 사용) 바텀-업 방식의 풀이 n=1일 때, n=2일 때 정도까지의 값을 미리 저장해두고, 리스트에 n=3, n=4, ... 처럼 하나씩 값을 계속 추가하면서 N까지 도달하는 방법이다. 그래프 그래프는 표현하는.. 2021. 7. 11. 이전 1 다음