♣ 플로이드 워셜 알고리즘데이크스트라 알고리즘이 한 지점에서 다른 지점까지의 최단 경로를 구하는 알고리즘이라면 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘이다.  플로이드 워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장하기 때문에 2차원 테이블에 최단 거리 정보를 저장한다. 또한 플로이드 워셜은 DP 알고리즘에 속한다.  [단계별 설명]1단계. 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다. (노드 사이에 간선이 없는 경우는 무한으로 설정)  2단계. 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. 예를 들면 1단계에서는 노드 3에서 노드 2으로 가는 기본 경로가 없어서 거리가 무한이었으나 1번 노드를 거쳐가게 되면 3 ..

♣ 데이크스트라 알고리즘한 꼭짓점을 source 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 최단경로트리 알고리즘을 데이크스트라 알고리즘이라고 한다. 아래 정리한 내용을 참고할 수 있다.  https://jy-deeplearning.tistory.com/86 Dijkstra(데이크스트라 알고리즘, 백준 알고리즘 18352번)♣ 데이크스트라 알고리즘 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘으로, 컴퓨터 과학자 에츠허르 데이크스트라가 고안했다. 데이크스트라 알고리즘은 변형이 많은데, 원래 알고리jy-deeplearning.tistory.com  ♣ 백준 알고리즘 13549번(숨바꼭질3) 이해 위 문제는 수빈이의 위치에서 어떤 경로로 이동해야 가장 빠르게 동생을 찾을 수 있는..

♣ 유니온 파인드란?유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 아래 집합을 보면 왼쪽은 두 집합에서 공통된 원소가 없고, 오른쪽은 공통된 원소가 있다. 공통된 원소는 서로소 집합이라고 한다.  유니온 파인드는 서로소 집합 자료구조를 만들 수 있다. 집합에서 노드들을 합치고(union), 부모를 찾아(find) 서로소 집합을 찾는 알고리즘이다. 기본적으로 유니온 파인드는 트리 자료구조에서 사용한다.  아래 그림처럼 두 개의 트리 구조가 있다고 생각해보자.  이 두 개 트리를 하나로 합치려고 한다. 기본적으로 각 집합의 root node를 찾아서 더 높은 인덱스를 가진 쪽이 작은 쪽을 흡수하는 성질을 가진다. 즉 아래 그림과 같은 결과가 나올 것이다.  Un..

♣ CCW세 점 A, B, C가 존재할 때, 특정 선분에 대하여 특정 점이 왼쪽에 있는지(시계 방향) 오른쪽에 있는지(반시계 방향)를 판별할 수 있는 알고리즘이다. 아래 그림을 예로 들어보자. C -> B -> A로 진행하는데, 첫 번째 그림은 시계방향, 두 번째 그림은 직선, 세 번째 그림은 반시계 방향을 나타낸다. 즉 선분 CB에 대한 점 A의 위치라고 생각하면 점 A는 선분 CB에 대해 각 그림에 따라 시계방향, 직선, 반시계 방향에 위치하는 것이다.  CCW(Counter Clock Wise)는 이렇게 세 점을 이었을 때의 방향을 판단하는 데 유용하게 쓸 수 있는 알고리즘이다. 신발끈 공식 점  A, B, C를 보면 선분 CB에 대한 점 A의 위치(방향)을 구하는 것이므로 점 C를 (x1, y1)..

♣ 문제 이해 moo 수열이 규칙에 따라 반복되는데, 주어진 n번째 글자가 m인지 o인지를 판별하는 문제이다.   ♣ 문제 해결분할정복으로 분류되어 있지만 마치 DP처럼 풀었다. 어떤 부분에서 분할정복과 DP를 구분할 수 있는지 잘 모르겠다.  DP처럼 함수를 만드는데, 조건을 네 가지로 나누어서 코드를 구성하였다. 1. 예외 처리n이 3과 같거나 작아서 0번째 Moo 수열에서 판별이 가능할 때   2. 예외 처리가 되지 않을 때는 이전 단계의 Moo 수열의 길이, 중간에 들어갈 m + o *(k+2) 의 길이, 이번 단계의 Moo 수열의 길이를 이용하여 세 가지 경우로 나눈다. 2-1. n이 이전 단계의 Moo 수열의 길이보다 작거나 같을 때. 이전 단계에서도 구할 수 있으므로 k-1 단계에서의 Moo..

♣ 분할정복(divide and conquer)하나의 문제를 작은 문제로 분할하여 해결하는 방법을 의미한다. 퀵 정렬, 합병 정렬, 이진탐색, 선택 문제, 고속푸리에 변환 문제들이 대표적으로 분할정복 알고리즘으로 해결할 수 있는 문제들이다.   ♣ 분할정복 설계1. Divide문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할때까지 나눈다.  2. Conquer각 하위 문제를 재귀적으로 해결한다. 하위 문제가 더 이상 나눌 수 없는 단위가 되면 탈출 조건을 설정하여 해결한다.  3. CombineConquer한 문제들을 통합하여 원래의 문제의 답을 얻어 해결한다.   ♣ 분할 정복의 특징 및 장단점1. 분할된 작은 문제는 원래 문제와 성격이 동일하다2. 분할된 문제는 서로 독립적이다. 3...