Algorithm/이론(17)
-
최단거리(2) 플로이드
최단거리(2) 플로이드 플로이드는 벨만 포드, 다익스트라와 다르게 모든 정점에서 다른 모든 정점까지의 거리를 구하는 방법입니다. 일단 이전 다익스트라와 같이 Relax 함수가 핵심입니다. map[start][end] = min(map[start][mid] + map[mid][end], map[start][end]); 이렇듯 다른 정점을 거쳐서 가는 것이 더 빠르냐 아니면 바로 가는 것이 더 빠르냐 비교하여 작은 값을 넣는 것이 핵심입니다. 플로이드는 모든 출발 정점에서 도착 정점까지의 거리를 구하는 것임으로 n까지의 반복문을 3중으로 돌려야합니다. sudo 코드 처음에 각 지점 별 weight를 저장한 후 weight가 없는 곳이라면 INF로 설정하겠습니다. 왜냐하면 초기에 0이면 min연산을 통해 값을..
2020.04.11 -
최단 거리(1) 다익스트라 알고리즈
최단 거리(1) 다익스트라 알고리즘 최단거리 알고리즘에는 다익스트라, 플로이드, 벨만포드 세가지 방법이 있습니다. 다익스트라와 벨만포드는 한 시작점에서 다른 정점까지의 최단거리를 구하는 것이고 플로이드는 모든 정점에서 모든 정점까지의 최단 거리를 구하는 것입니다. 오늘은 3가지 중 다익스트라에 대해 정리해보겠습니다. 1. 다익스트라는 시작 정점에서 다른 정점까지의 거리를 모두 무한대로 세팅한 후 시작합니다. s 정점까지의 가중치와 연결된 정점까지의 가중치 값을 더해서 연결된 정점까지의 가중치 보다 작다면 값을 바꿔줍니다. 2. 이전 라운드를 제외한 다른 정점들 사이에서 최단 거리를 구해줍니다. 새로운 정점 s를 뽑는 방법은 가장 작은 가중치를 갖는 정점을 뽑습니다. 정점 s를 시작으로 다른 연결된 정점들..
2020.04.11 -
DP(2)
행렬경로문제 행렬 경로 문제는 우상단에서 좌하단까지 이동하는 방법이다. 단 오른쪽이나 아래쪽방향으로만 움직일 수 있다. 방문칸에 가중치를 최소화하여 이동해야한다. 위와 같이 해결하는 방법이다. 이 문제를 해결하기 위해 우리는 동적계획법을 사용해야하는데 동적 계획법의 절차는 1. 순환식을 세운다. 2. 순환식을 계산하는 방식이다. (i, j)까지 이동하는 방법의 이전 단계에서는 (i-1, j)이거나 (i, j-1)에서 이동하는 방법이다. 결과가 모두 최선이 되어야 하기 때문에 각각의 상황 (i-1, j)과 (i, j-1)는 최선의 상황이어야 한다. 순환식 mij는 (i, j)의 가중치이다. L[i, j]는 1, 1에서 부터 i, j 까지의 가중치이다. 첫번째 경우는 첫시작이니 당연히 첫번째 값의 값이 나올..
2019.06.03 -
DP(1) 메모제이션과 bottomUp방식
DP는 Dynamic Programming이라는 말은 줄인말이다. Memoization memoization은 같은 계산이 반복 될 때 이를 기록해두어 계산을 진행하지 않고 저장된 값을 불러오는 것이다. fibonacci의 예를 들면 int fibo(int n){ if( n == 1 || n == 2) return 1; else return fibo(n-1) + fibo(n-2); } 일반적인 코드는 위와 같이 작성한다. 하지만 위와 같이 작성되면 단점이 있는데 같은 계산이 반복되는 것이다. 아래의 경우 fib(2), fib(1), fib(3) 등의 재귀 함수가 반복되는 것을 볼 수 있다. 했던 계산식을 계속해서 반복하는 단점이 존재한다. 그래서 아래와 같이 작성을 한다. int fibo(int n){ ..
2019.06.03 -
(4)최소 비용 신장 트리(MST) Prim 알고리즘
Prim의 알고리즘 1. 임의의 노드를 출발 노드로 선택한다. 2. 출발 노드를 포함하는 트리를 점점 키워감 3. 매 단계에서 이미 트리에서 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택한다. 실제 실행 순서 실행 해보면 누가 봐도 특별한 어려움이 없을 것이다. 크루스칼이나 프림이나 이론은 별로 어려운 것이 없는 것 같다. 언제나 그렇듯 실제 구현이 문제이다. 가중치가 최소인 엣지 찾기에 대해 논해보겠다. key는 엣지가 가장 작은 정점 파이는 가장 작은 가중치의 도착점이다. 예를 들면 아래와 같다. 가중치가 최소인 엣지를 찾기 보단 key값이 최소인 엣지를 찾는 것이 중요하다. key값이 최소인 엣지를 찾는 것은 적어도 n개 보다 작은 수의 엣지를 봐야함으로 O..
2019.05.20 -
(3)최소 비용 신장 트리(MST) Kruskal 알고리즘
Kruskal 알고리즘 1. 에지들을 가중치가 오름차순으로 정렬한다. 2. 에지들을 그 순서대로 하나씩 선택해간다. 만약 사이클을 이루게 된다면 선택하지 않는다. 3. n-1개의 에지들이 선택되면 종료된다. 위의 그림을 보며 신장트리를 만들어보자! (웨이트가 같은 엣지가 있으면 아무거나 선택해도 된다.) 왜 신장트리가 찾아지고 만들어지는 것일까? 임의의 한단계를 생각해보자! A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자! 두개의 cut에 cross되지 않는 엣지들 중 최소를 고르면 당연히 사이클이 만들어지지 않고 안전하게 연결될 것이다. 그렇고 보니 이론은 정말 간단하다 ! 정렬 후! 사이클 확인! 최소 가중치의 엣지 더하기 순서를 반복하면 되는 것이..
2019.05.20