반응형 알고리즘창고7 [코드조각] union-find (분리집합) python에서 분리집합을 하기 위한 find 함수와 union함수. 둘 다 최악의 경우 시간복잡도 O(n)을 기록한다 # P[i]는 i가 속한 집합의 대표값이 담겨있다. def find(n): if P[n] == n: return n P[n] = find(P[n]) return P[n] def union(u, v): u = find(u) v = find(v) if u == v: return if u != v: P[v] = u 2021. 9. 13. [코드조각] 플로이드-워셜 플로이드-워셜 알고리즘은 그래프 간의 모든 정점에서 다른 정점까지의 최단거리를 쉽게 구하는 알고리즘이다. 모든 정점과 정점 사이의 최단거리가 필요하거나, 키 비교, 줄 세우기 등의 문제에서 사용할 수 있다. import math N = int(input()) #정점의 개수 M = int(input()) #입력할 간선 정보의 개수 #정점과 정점사이의 거리. d[i][j]는 노드 i에서 노드 j까지의 거리 d = [[math.inf for i in range(N)] for j in range(N)] #자기 자신부터 자기 자신의 거리가 0 for i in range(N): d[i][i] = 0 #간선 정보 입력 while M: # 출발지점, 끝지점, 비용 S, E, C = map(int, input().spl.. 2021. 6. 11. [코드조각] 다익스트라 최소힙을 이용한 다익스트라. 기본으로는 start부터 모든 지점까지의 최소거리가 담긴 list를 반환한다. import heapq import math def dijkstra(nodes, start): N = len(nodes) d = [math.inf] * (N+1) q = [] qlen = 1 d[start] = 0 heapq.heappush(q, (d[start], start)) while qlen > 0: tmp = heapq.heappop(q) qlen -= 1 if d[tmp[1]] dtmp: d[i[0]] = dtmp heapq.heappush(q, .. 2021. 5. 7. [C] 보고 정렬 (bogo sort, stupid sort) 정렬 알고리즘을 찾아보는 도중에 신기한 이름을 봤다. 보고 정렬, 멍청이 정렬.. 무슨 알고리즘이길래 멍청이라는 이름을 붙여줬나 했더니 무려 랜덤으로 데이터를 재배열해서 정렬을 하는 알고리즘이다! 정렬이 될 때까지 랜덤으로 돌리기 때문에 최악의 경우에는 영원히 정렬이 안될 수도 있다! 언제 정렬이 완료될 지는 아무도 모른다. 이름값을 하는 정렬이다. #include #include #include const int MAX_NUM = 10; void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int isSorted(int *arr, int len) { int i, j; for (i = 0; i < len; i++) { for (j = i + 1;.. 2018. 7. 13. [C] 버블 정렬 (bubble sort) 가장 짧고 간단한 코드로 나타낼 수 있는 정렬 알고리즘이다. 하지만 이러한 알고리즘이 다 그렇듯 단점은 거의 모든 상황에서 최악의 성능을 보인다는 점이다. 시간 복잡도는 O(n^2)이다. 적은 양의 데이터에서는 굳이 다른 정렬법을 쓰지 않아도 되는 성능을 발휘하지만, 현업에서는 방대한 양의 데이터를 관리하기 떄문에 버블정렬은 웬만해서는 안쓴다고 한다. 버블 정렬은 1번째와 2번째, 2번째와 3번쨰 .... n-1번째와 n번째를 비교하여 정렬하고 그 다음엔 n-2, n-1번째 까지, 그 다음엔 n-3, n-2번째 까지 하나씩 줄여가면서 정렬한다. #include #include #include const int MAX_NUM = 100; void swap(int *a, int *b) { int tmp = .. 2018. 7. 12. [C] 배열 기반 스택 (array stack) 배열로 만든 스택은 연결리스트에 비해 매우 간단해서 좋다. 그래서 빠르게 코딩을 해야할 때 자주 사용한다. 하지만 C++에는 stack 헤더가 있다. 배열로 구현할 때의 장점은 연결리스트에 비해 메모리를 아낄 수 있다는 점, 그리고 구조가 간단하다..! 제한을 걸어놓은 과제나 문제를 풀 때 용이하다. 단점은 크기가 제한되어 있다는 것. 하지만 realloc이 있다면? 연결리스트로 구현했던 코드와 다른 점은 실행하고 명령어 입력 전에 스택의 크기를 먼저 입력한다. 명령어 push N -> 정수 N을 push한다 pop -> 스택을 pop하고 그 값을 출력한다. 스택이 비어있으면 Stack Empty 출력 size -> 스택의 크기를 출력한다. top -> top에 위치한 값을 출력한다. 스택이 비어있으면 .. 2018. 7. 10. 이전 1 2 다음 반응형
