CS/알고리즘

트리(Tree) 그래프의 특수한 경우. 사이클이 없이 모든 정점이 연결되어 있는 그래프. 2개의 노드 사이에 반드시 1개의 간선만을 가짐. 부모-자식 관계가 존재하여 계층형 모델이라고도 함. 최상위에 Root 노드 존재. 스패닝 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 그래프. 그러므로 간선의 개수는 (V-1)개 (V는 정점의 개수) 스패닝 트리 = 신장 트리 최소 스패닝 트리(MST, Minimum Spanning Tree) 스패닝 트리 중 간선 가중치의 합이 최소가 되는 스패닝 트리 MST를 구하는 알고리즘은 보통 아래의 2가지를 많이 사용 크루스칼 알고리즘 (Kruskal Algorithm) 프림 알고리즘 (Prim Algorithm) 크루스칼 알고..

다익스트라(Dijkstra) 알고리즘 한 정점에서 다른 모든 정점으로 가는 최단거리를 구하는 알고리즘. 매번 방문하지 않은 노드 중 가장 가까운 노드를 선택하여 하나씩 최단 거리를 구해나간다. 다이나믹 프로그래밍, 그리디 알고리즘에 포함됨. 음의 가중치를 가진 간선을 포함할 수 없음. 음의 가중치를 간선이 있다면 벨만-포드 알고리즘 사용. import heapq graph = [[] for _ in range(v)] def dijkstra(start): distance = [int(1e9)] * (v) distance[start] = 0 q = [] heapq.heappush(q, (0, start)) while q: dist, now = heapq.heappop(q) if distance[now] < ..

피보나치 수열은 0번째 항이 0, 1번째 항이 1, 그리고 그 이후의 항은 앞의 두 항의 합인 수열을 말한다. 점화식으로 살펴보면 다음과 같다. $$ F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 0) $$ 피보나치 수열의 n번째 항을 구하는 방법은 여러 가지가 있는데 그 중 3가지를 살펴볼 것이다. 반복 재귀함수 메모이제이션 반복 def fibo(n): if n

순열 (Permutation) 서로 다른 n개 중 순서에 상관있게 r개를 선택하는 경우의 수 서로 다른 n개에서 r개를 택하는 순열의 수는 다음과 같다.예를 들어, 서로 다른 5개에서 3개를 고르는 순열의 수 $_5P_3$은 5 X 4 X 3 = 60 즉, $_nP_r$은 n부터 내림차순으로 r번째 수까지 곱하면 된다. 팩토리얼을 이용하여 간단하게 나타내보면 다음과 같다. $$0!=1,,_nP_0=1,,_nP_n=n!$$ $$ _nP_r=n(n-1)(n-2)\cdot \cdot \cdot(n-r+1),(단,0

에라토스테네스의 체는 소수를 판별하는 알고리즘이다. 2 이상의 수에 대해 소수를 판별할 때 사용할 수 있다. 어떻게 하는지 단계별로 알아보자면 다음과 같다. 2부터 소수를 구하고자 하는 구간의 수를 나열한다. 2는 소수이므로 2는 남기고 2의 배수를 모두 지운다 3도 소수이므로 3은 남기고 3의 배수를 모두 지운다. 이렇게 수를 증가시켜가며 지워지지 않은 수들에 대해 자기자신만 남기고 그의 배수들은 지우는 과정을 반복하면 지정한 구간의 소수들을 구할 수 있다. 지워지지 않은 숫자들이 바로 소수이다. 이때 2부터 N까지 구간의 소수를 구한다고 하면 우리는 $int(\sqrt N) + 1$까지만 확인해보면 된다. 예를 들어 2부터 120까지의 소수를 판별한다고 하면 $120 < 11^2$ 이므로 11까지만 ..