[엘리스 AI 트랙 2기] Day 10 - 동적계획법, 그래프

동적계획법

정의

계산 복잡도가 큰 문제를 풀 때, 중복되는 문제는 풀지 않고 이전에 계산한 결과를 참조하여 중복 연산의 수를 줄여 빠르고 효율적으로 문제를 푸는 방식이다.
참조는 리스트의 인덱싱을 사용할 수도 있고 해시테이블(딕셔너리)를 사용할 수도 있다.

기저조건은 미리 딕셔너리나 리스트에 저장해두고 시작한다.

탑 다운 방식의 풀이

우리가 구하고자 하는 함수를 F라고 했을 때, F(n)의 값에서부터 f(n) = f(n-1) + f(n-2) 식으로 계속 내려와 기저조건까지 오는 방법이다. (딕셔너리 사용)

바텀-업 방식의 풀이

n=1일 때, n=2일 때 정도까지의 값을 미리 저장해두고, 리스트에 n=3, n=4, ... 처럼 하나씩 값을 계속 추가하면서 N까지 도달하는 방법이다.

그래프

그래프는 표현하는 방법이 두가지이다. 인접 행렬과 인접 리스트인데, 인접 행렬은 NxN의 행렬을 만들어 각각 그래프가 연결되어있는지 1과 0으로 나타내는 방법이고 인접리스트는 첫번째 axis가 노드의 번호를 가리키고, 두번째  axis의 값들은 해당 노드가 어떤 노드들과 연결되어있는지 알려준다.

너비 우선 탐색(큐)

1. 루트를 큐에 삽입
2. 맨 앞 노드를 pop
3. 팝과 연결되어 있지만 방문하지 않은 노드를 큐에 저장

큐가 빌 때 까지 2와 3을 반복한다.

깊이 우선(스택)

1. 루트노드를 스택에 삽입
2. 루트와 연결된 노드 중, 가장 앞에 있는 노드를 스택에 추가한다.
3. 2를 계속 하다가 더 이상 갈 곳이 없으면 pop한다.
4. 갈 곳이 있으면 2, 없으면 3을 계속 반복한다.

스택이 빌 때 까지 수행.

그래프 알고리즘

최단거리 알고리즘 - 다익스트라, 벨만포드

벨만포드는 다익스트라와는 달리 음의 가중치도 허용한다.
단, 싸이클이 생기지 않도록 하는 알고리즘도 신경써야 한다.

최소신장트리 - 프림, 크루스칼

....잘 모르겠다..

있다는 것만 알아두자.

우하하하하