Algorithm | SQL/개념 검색 결과

해당 글 7건

[Python] 위상 정렬 알고리즘 (Topology sort)

위상 정렬은 정렬 알고리즘의 일종으로, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이다. 위상 정렬을 위해서는 먼저 진입차수 (Indegree) 를 알아야 한다. 진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다. 위상 정렬 과정 [1] 진입차수가 0인 노드를 큐에 넣는다. [2] 큐가 빌 때까지 다음의 과정을 반복한다. I. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. II. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 위상 정렬 코드 from collections import deque # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(int, input().split()) # 모든 노드에 대한 진입차수는 0으로 초기..
Algorithm | SQL/개념 2021. 5. 30. 01:51

[Python] 이진 탐색 (Binary Search)

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 정렬된 데이터에서 원하는 데이터를 빠르게 찾을 수 있다는 장점이 있다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용한다. 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색이다. 한번 확인할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다. 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근하는 것을 고려해보면 좋다. 구현하는 방법에는 두가지가 있다. 1. 재귀 함수로 구현 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(ar..
Algorithm | SQL/개념 2021. 5. 17. 23:34

[Python] 최소 스패닝 트리(MST), 크루스칼 알고리즘 (Kruskal Algorithm)

신장 트리 (Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 N개의 노드로 만드는 스패닝 트리는 N-1개의 노드로 구성되어 있다. 유니온 파인드 알고리즘을 활용하여 사이클을 검사할 수 있고, 이를 활용하여 스패닝 트리를 만들 수 있다. 이중 최소한의 비용으로 구성된 스패닝 트리를 최소 스패닝 트리 (MST) 라고 한다. 최소 스패닝 트리를 구하는 알고리즘으로 크루스칼, 프림 알고리즘이 있는데 크루스칼 알고리즘을 다뤄보겠다. 크루스칼 알고리즘 (Kruskal Algorithm) 핵심 원리 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다. 다만 사이클을 발생시키는 간선은 제외하고 연결한다. [1] 간선 비용에 따라 오름차순으로 정렬 [2..
Algorithm | SQL/개념 2021. 5. 15. 21:58

[Python] 유니온 파인드 알고리즘 (Union Find Algorithm)

노드들을 합치고(union), 부모를 찾아(find) 서로소 집합(disjoint set)을 찾아내는 알고리즘 트리 구조를 활용한다. find 연산은 부모 노드를 찾을 때까지 재귀적으로 호출한다. union 연산은 두 원소의 부모 노드를 찾고 번호가 큰 노드가 번호가 작은 노드의 부모를 가리키도록 한다. 이를 효과적으로 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 한다. # 특정 원소가 속한 집합을 찾기 def find(x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: return find(parent[x]) return x # 두 원소가 속한 집합을 합치기 def union(a, b): a = find(a) b = find(b) if a..
Algorithm | SQL/개념 2021. 5. 15. 19:47

[Python] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘 노드의 개수가 N개일 때 시간복잡도는 O(N^3) 각 단계에서 해당 노드를 거쳐가는 경우를 고려한다. 핵심 점화식 Dab : a를 거쳐 b로 가는 최단 거리 Dab = min(Dab, Dak + Dkb) 점화식을 이용하므로 DP라고 볼 수 있고 원리는 다소 어렵지만 코드는 아주 간단하다. 암기해서 사용하자. INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자..
Algorithm | SQL/개념 2021. 5. 15. 19:03

[Python] 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. '음의 간선'이 없을 때만 사용할 수 있다. 최단 거리 테이블을 이용하며, 그리디와 DP를 이용한다고 볼수 있다. 다익스트라 알고리즘 기본 원리 [1] 출발 노드 설정 [2] 최단 거리 테이블 초기화 [3] 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드 선택 [4] 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 [5] [3], [4] 번 반복 구현 방법 2가지 방법 1. 구현이 쉽지만, 동작이 느린 코드 (O(V^2)) 방법 2. 구현이 어렵지만, 동작이 빠른 코드 (O(ElogV)) 방법 1. 구현이 쉽지만, 동작이 느..
Algorithm | SQL/개념 2021. 5. 15. 18:39

[Java] 순열, 조합, 부분집합 (Permutation, Combination, Subset)

순열, 조합, 부분집합 알고리즘은 알고리즘의 기초이고 각종 코딩테스트 단골 주제이다. 하지만 항상 막상 구현하려고 하면, 손과 머리가 버벅이는 경우가 많았다. 이번 기회에 블로그에 정리를 해서 장기 기억으로 남기기위해 포스팅한다. 이번 포스팅에는 재귀함수를 이용하여 구현할 것이다. 비트마스크라던지 다른 좋은 방법들이 많지만 아직 미숙하여 기초부터! 1. 순열 ( Permutation ) import java.util.Arrays; public class Perm_Practice { static int[] src = { 1, 2, 3, 4, 5 }; static int[] tgt = new int[2]; static boolean[] select = new boolean[src.length]; public..
Algorithm | SQL/개념 2021. 5. 2. 19:44