CS

위상 정렬(topology sort)

📔 위상 정렬(topology sort) 이란 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 어떤 일을 하는 순서를 찾는 알고리즘 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 선행 조건이 반드시 수행되어야 다음을 진행할 수 있다! 위의 그림을 보면 아비터트리뷰널을 짓기 위해서는 템플러아카이브와 스타게이트가 둘다 있어야 한다. 시간복잡도: O(V+E) | V-노드의 수, E-간선의 수 📔 위상 정렬(topology sort) 구현 큐와 스택을 사용할 수 있다. 일반적으로 큐를 사용 진입 차수( 현재 노드에 들어올 수 있는 노드의 수 ) 가 0인 정점을 큐에 삽입 (그림의 사이버네틱스코어) 큐에서 원소를 꺼내 연결..

플로이드 와샬(Floyd Warshall)

📔 플로이드 와샬(Floyd Warshall) 란 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. ( 출처: 위키백과 ) 모든 정점에서 모든 정점으로의 최단 경로를 구하는 것! 거쳐가는 정점을 기준으로 구한다. 다이나믹 프로그래밍 기법을 이용 다익스트라의 경우 한 정점에서 모든 정점까지 의 최단 경로 반복문이 3개이므로 시간복잡도는 O(N^3) 이다. 하지만 코드는 매우 간단하다. 📔 플..

에라토스테네스의 체(Sieve Of Eratosthenes)

📔 에라토스테네스의 체(Sieve Of Eratosthenes) 란 대표적인 소수 판별 알고리즘 ( 소수: Prime Number ) 한꺼번에 많은 숫자의 소수를 판별할 때 사용 숫자 한개의 소수를 판별하는 기본 소수 판별 알고리즘의 시간복잡도는 O(N) 하지만 수학적으로 접근해서 시간복잡도를 O(N^(1/2)) 까지 줄일 수 있다. 에라토스테네스의 체를 사용하면 시간복잡도는 O(n log log n) 📔 에라토스테네스의 체(Sieve Of Eratosthenes) 구현 자연수 50까지의 숫자 중에서 소수를 구한다고 생각해보자. 기본 알고리즘을 사용할 경우 O(N*N^(1/2)) 의 시간복잡도가 생긴다. 에라토스테네스의 체를 이용하여 구해보자. 먼저 51개의 값이 1(True)인 리스트를 만든다. for..

다익스트라(dijkstra)

📔 다익스트라(dijkstra) 란 다익스트라를 들어가기 전에... 최단 경로란 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 간선의 가중치가 균일(1)할 경우 BFS를 사용 음의 가중치를 허용하지 않음 하나의 시작 정점에서 끝 정점까지의 최단경로 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 시작 정점(s) 에서 끝 정점(t) 까지의 최단 경로에 정점 x 가 존재한다. 이때, 최단 경로는 s 에서 x 까지의 최단경로와 x 에서 t 까지의 최단경로로 구성된다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다. 아래 코드의 경우 시간복잡도는 O(N^2) 이다. 만약 우선순위큐를 이용하게 된다면 O(NlogN..

다이나믹프로그래밍(Dynamic Programming)

📔 다이나믹프로그래밍(Dynamic Programming)이란 하나의 문제는 단 한 번만 푸는 방법! 다이나믹프로그래밍 (이하 DP) 작은 문제를 해결하여 큰 문제를 해결하는 분할정복과 유사하다고 생각할 수 있지만, 분할정복의 경우 한번 풀었던 문제를 다시 푸는 비효율적인 단점을 가지고 있다. (일부 경우 제외 (병합정렬)) 분할정복과 DP의 차이를 보여주는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열: 바로 앞과 앞앞 두 칸의 숫자의 합을 구해서 나타내는 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 분할정복을 이용한다면 이미 구한 숫자들을 다시 계산하는 단점이 있다. 위의 사진을 보면 13을 구하는게 2번, 12 3번, 11 3번 계산하는 것을 볼 수 있다. 이런 문제를 ..

크루스칼 알고리즘(kruskal)

📔 크루스칼(kruskal) 이란 간선을 하나씩 선택해서 MST를 찾는 알고리즘 ( 프림은 정점을 선택, 크루스칼은 간선을 선택 ) 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다 사이클이 존재하면 패쓰 ( 사이클의 존재를 파악하는게 중요! ) V-1개의 간선이 선택될 때 까지 반복 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 disjoint-set 알고리즘을 이용한다. 📔 크루스칼(kruskal) 구현 def make_set(x): p[x] = x def find_set(x): if p[x] == x: return x else: p[x] = find_set(p[x]) return p[x] def union(x, y): px ..