♣ 플로이드 워셜 알고리즘데이크스트라 알고리즘이 한 지점에서 다른 지점까지의 최단 경로를 구하는 알고리즘이라면 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘이다.  플로이드 워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장하기 때문에 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)..

더 많은 데이터 문자 단위 RNN 구현하기 ♣ 훈련 데이터 처리하기 문서 집합을 생성하고, 각 문자에 고유한 정수를 부여한다. 각 문자에 정수가 부여되었으며 총 25개의 문자가 존재한다.  하이퍼파라미터를 설정한다.  hidden_size(은닉 상태의 크기)를 입력의 크기와 동일하게 하였는데 다른 값을 주어도 무방하다. 앞서 만든 샘플을 10개 단위로 끊어서 샘플을 만들 예정이기 때문에 sequence_length 라는 변수를 10으로 선언한다.  임의로 지정한 sequence_length 값인 10의 단위로 샘플들을 잘라서 데이터를 만든다.    총 170개의 샘플이 생성되었다. 각 샘플의 각 문자들은 고유한 정수로 인코딩 된 상태이다.  x_data[0] 는 if you wan 에 해당한다. y_da..

모든 시점의 입력에 대해서 모든 시점에서 출력을 하는 다대다 RNN ♣ 문자 단위 RNN입출력의 단위를 단어 레벨이 아니라 문자 레벨로 하여 RNN을 구현한 것을 문자 단위 RNN이라고 한다. RNN 구조는 같지만 입, 출력의 단위가 문자로 바뀌었을 뿐이다.  필요한 도구 import 하기 훈련 데이터 전처리하기문자 시퀀스 apple을 입력받으면 pple!를 출력하는 RNN을 구현한다. RNN의 동작을 이해하는 것이 목적이다. 입력 데이터와 레이블 데이터에 대해서 문자 집합(vocabulary)를 만든다. 이 문자 집합은 중복을 제거한 문자들의 집합이다. 현재 문자 집합에는 총 5개의 문자가 있다. !, a, e, l, p이다. 이제 하이퍼파라미터를 정의하는데, 이때 입력은 원-핫 벡터를 사용할 것이므로..