인접행렬 사용 경유지를 뽑을 때, for문을 2번 사용 시간복잡도가 O(n^2) 인접리스트 사용 경유지를 뽑을 때 우선순위 큐 사용 시간복잡도가 O(nlogN) - 유투브 영상 더보기 ▷ 기본 개념 및 흐름 설명 https://www.youtube.com/watch?v=RKGX2_O18vs&list=PL1vwZeA5Kax0RXU1Ls5zkFSGKQr02njP2&index=6 https://www.youtube.com/watch?v=j0gGdJ-Cs1M&list=PL1vwZeA5Kax0RXU1Ls5zkFSGKQr02njP2&index=7

한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘 시간복잡도 On^3) 1. 시작점이 주어지고, 가중치가 양수일 때 => 다익스트라 알고리즘 O(n^2) / O(nlogN) 2. 시작점이 주어지지만, 가중치가 음수일 때 BellmanFord 알고리즘 O(n^2) 3. 시작점이 주어지지 않고, 가중치가 음수일 때 Floyd Warshall O(n^2) ▷ 기본 개념설명 더보기 Floyd Warshall 1부 https://www.youtube.com/watch?v=i9PqXWHAaLQ&list=PL1vwZeA5Kax0RXU1Ls5zkFSGKQr02njP2&index=9&t=355s Floyd Warshall 1부 https://www.youtube.com/watch?..

우선순위 큐 (Priority Queue) O(logN)의 속도로 자료를 넣었다 뺐다 할 수 있다 처음에 시간복잡도를 계산하고 O(n^2)이 안될 거 같다 싶으면 쓰기 사용자의 우선순위가 높은 값부터 먼저 출력하는데, 그 우선순위는 정하기 나름이다. 예를 들어서 max heap이라고 하면, 큰 값이 우선순위가 높고 min heap이라고 하면, 작은 값이 우선순위가 높다. 그 우선순위는 짝수가 될 수도 있고, 홀수가 될 수도 있다. 우선순위 큐의 안의 내부원리를 살펴보면, 힙이라는 자료구조로 되어있다. 파이썬에서는 import heapq를 사용하는데, 그렇게 하면 완벽한 이진트리의 형태를 유진하다는 특징이 있다. 예를 들어 Max heap을 구하는 문제를 살펴보자. Max heap을 출력하는 방법은 3가지..

유니온 find 방법을 이용하면, 정점과 간선의 정보가 주어졌을 때, 그 안에서 사이클이 발생하는지 아닌지를 알 수 있다. Ex) 정점의 개수를 n개 입력받고 간선의 개수 m개 입력 받겠다. 이 그래프에서 싸이클이 발생하는지, 아닌지를 union find 방법을 통해 확인하시오 입력 # n, m 6 4 # edge A B B C D E A D C D 출력 : 싸이클 발생

▶ 신장 트리(Spanning Tree) 그래프 내에 있는 모든 정점이 연결되어 있고 사이클이 없는 그래프 n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 된다 ▶ 최소 신장 트리 (Minimum Spanning Tree) 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리 (가중치는 거리, 비용, 시간 등이 될 수 있다) 즉, 최소 신장 트리는 정점과 간선이 주어졌을 때, 최소 비용으로 정점들을 연결시키는 방법을 찾는 것이다. 이런 유형의 문제를 풀기 위해서는 프림 알고리즘(Prim’s Algorithm) 이나 크루스칼 알고리즘(Kruskal’s Algorithm) 을 사용해야한다. 사이클의 존재 유무를 확인할 때는 이전에 배웠던 유니온 find 방법을 이용하면 된다. Ex) A, B,..

탐색 구간이 정해져있지 않을 때, 빠른 검색을 위해 사용한다. 만약 탐색 구간이 정해져있다면, Sliding Window 알고리즘을 사용하면 된다. 딱 봐서는 Two Pointer처럼 보이지 않지만, sort()를 했을 때 보이는 경우가 있다. 그래서 일단은 정렬 먼저 해보기 - 유투브 영상 더보기 ▷ 개념설명 https://www.youtube.com/watch?v=vfuCLVnlDNs&list=PL1vwZeA5Kax0RXU1Ls5zkFSGKQr02njP2&index=10

/ ▷ 슬라이딩 윈도우 알고리즘 탐색 구간이 정해져있을 때 빠른 검색을 위해 사용한다 (시간복잡도를 줄이려고) 만약 탐색 구간이 정해져있지 않다면, Two pointer를 쓰면 된다. 예를 들어) 10개의 정수 중 연속된 3개의 구간의 합이 최대일 경우 그 최대값을 구하라는 문제가 있을 수 있다. ex) n개의 정수 중 연속된 m개의 구간의 합이 최대일 경우 그 최대값은? ** 10 5 3 -2 -4 -9 0 3 7 13 8 -3 입력시 출력결과: 31 10 2 3 -2 -4 -9 0 3 7 13 8 -3 입력시 출력결과는: 21 # 슬라이딩 윈도우 n, m = map(int, input().split()) arr = list(map(int, input().split())) sum = 0 # 첫 M개 구..

▷ Hash (해시) Hash 이전에 자료구조의 근간이 되던 것은 DAT이다. DAT(Direct Address Table) -> Hash DAT는 리스트 안에 있는 값을 새로운 리스트의 인덱스로 활용하는 방법이다. 인덱스를 담을 bucket을 만드는 것 그런데 이러한 DAT의 단점은, 마이너스 인덱스를 사용할 수 없다는 것이다 (파이썬은 괜찮지만, 자바나 C에서는 어렵다) 또, 원하는 값이 문자열일 경우 인덱스로 활용할 수가 없다. 이것을 극복해서 만든 것이 바로 Hash이다. 먼저, HASH 함수를 하나 만들고, 여기에 키 값을 하나씩 넣어준다. 그리고 키를 매개변수로 받아주면 된다. 1. Changing 방식 링크드 리스트로 연결시키는 것 리턴에 해당하는 곳에 주렁주렁 달아준다. 2. Open ad..

/

/