최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘
2022. 10. 5. 01:20
컴퓨터/알고리즘&자료구조
신장 트리(Spanning Tree) 모든 정점을 연결하되, 사이클이 존재하지 않는 그래프 위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!! 원본 그래프의 부분 그래프이므로 여러 개가 생길 수 있다 최소 신장 트리(Minimum Spanning Tree, MST) 신장 트리 중에서 간선 가중치의 합이 최소인 것 사용 사례 - 도시를 모두 연결하는 도로의 비용이 최소가 되는 것을 구하기 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하기 대표 알고리즘 - 크루스칼(Kruskal) 알고리즘 - 프림(Prim) 알고리즘 크루스칼 알고리즘 - 그래프의 간선들을 가중치의 오름차순으로 정렬한다 - 정렬된 순서대로 간선들을 선택한다 - 사이클이 발생하지 않도록 한다 동..
합집합 찾기(union-find)
2022. 10. 5. 00:44
컴퓨터/알고리즘&자료구조
최소 신장 트리 찾기 문제를 풀어보려고 했더니, 크루스칼 알고리즘을 알아야 된다고 한다. 크루스칼 알고리즘을 공부하려고 했더니, 합집합 찾기 알고리즘을 알아야 한다고 한다. 오늘은 합집합 찾기 union find 알고리즘을 공부해보자! 크루스칼(Kruskal) 알고리즘 - 가장 적은 비용으로 모든 노드를 연결한다 - 그리디 알고리즘에 해당한다 - 최소 신장 트리에는 사이클이 존재하면 안 되는데, 사이클의 발생 여부를 union-find로 확인할 수 있다 - 노드 a 와 노드 d 가 이미 같은 그래프에 속하는데, 두 노드를 연결한다면 사이클이 발생한다!! - 따라서 두 노드가 같은 그래프에 속하는지 확인하기 위해 union-find 알고리즘을 사용한다 합집합 찾기(union find) - 서로소 집합 혹은..
[백준/약점체크] 1916번: 최소비용 구하기
2022. 10. 3. 23:50
컴퓨터/코딩테스트
[문제] [내 코드] N = int(input()) # 도시의 개수 M = int(input()) # 버스의 개수 # 버스의 출발도시, 도착도시, 비용 graph = {} for n in range(N): graph[n+1] = {} for _ in range(M): a, d, c = map(int, input().split()) graph[a][d] = c start, end = map(int, input().split()) def bellman_ford(graph, start): dist = {} for node in range(1, N+1): dist[node] = float('inf') dist[start] = 0 # V-1 번 반복 for i in range(N-1): for node in gr..
노션 포트폴리오 리뉴얼
2022. 9. 30. 03:54
진로/취업
벼르고 벼르던.. 노션 포트폴리오 정리 이번에 큰맘 먹고 제대로 정리했다. 아직 빠진 내용이 많아서 채워 넣을 게 많지만.. 이전보다 훨씬 깔끔해진 것 같아서 뿌듯하다. 혹 노션으로 포트폴리오를 만들고자 하는 사람에게 도움이 될까 싶어 공유해본다. 노션 포트폴리오의 링크는 여기에 있다. https://www.notion.so/Yunsoo-Woo-1a6880d11298453eaf2a692b931386fd
자료구조 : 힙(heap)
2022. 9. 27. 00:10
컴퓨터/알고리즘&자료구조
우선순위 큐를 구현한 완전 이진 트리의 일종 우선순위 큐 스택 - 가장 최근에 입력된 데이터부터 추출 큐 - 가장 먼저 입력된 데이터부터 추출 우선순위 큐 - 가장 우선순위가 높은 데이터부터 추출 우선순위 큐를 힙, 배열, 연결리스트로 구현할 수 있는데, 그중 힙으로 구현한 것이 가장 효율적 우선순위 큐 구현 입력 추출 순서 없는 배열 O(1) O(n) 순서 없는 연결리스트 O(1) O(n) 순서대로 정렬된 배열 O(n) O(1) 순서대로 정렬된 연결리스트 O(n) O(1) 힙 O(log n) O(log n) 특징과 종류 - 여러 값 가운데 최솟값이나 최댓값을 빠르게 찾을 수 있다 - 반정렬 상태(느슨한 정렬 상태) - 중복값 허용 - 계산의 편리를 위해 첫번째 인덱스가 1부터 시작함 - 종류 - 최대 ..
최단 경로 문제: 다익스트라 알고리즘
2022. 9. 26. 23:40
컴퓨터/알고리즘&자료구조
최단 경로 문제란? 벨만포드 알고리즘을 다룬 여기 문서 참고 다익스트라 알고리즘 - 하나의 시작점에서 도착점으로 가는 최단 경로를 찾는 알고리즘 - 간선이 음의 값을 가져선 안 된다 1. graph, weight, start 가 주어진다 2. start(자기 자신)까지의 거리는 0으로 상정한다 3. 모든 vertex 들을 queue에 넣고 반복한다 - queue에 들어간 v 중에서 가장 작은 값을 찾아 뽑는다 - 뽑힌 v에 대해서 relaxation 수행 예제 현재 Q에서 가장 작은 값을 찾는다 --> $s$ $s$의 인접 노드 중에서 더 작은 $y$ 선택 $y$에서 relaxation 시행, 가장 작은 $z$ 선택 $z$에서 relaxation 시행, Q에서 가장 작은 $t$로 다시 돌아감 $t$에서 ..
최단 경로 문제: 벨만포드 알고리즘
2022. 9. 26. 18:36
컴퓨터/알고리즘&자료구조
최단 경로 문제란? - 정점 $u$에서 정점 $v$까지의 경로 중에서 경로의 값이 가장 작은 경로를 찾는다 - $\delta (u, v)$ 벨만포드 알고리즘 음수 간선의 값(negative-weight edges) 이렇게 생긴 경로 그래프가 있고, $s$ 에서 $g$로 가는 경로를 구하려고 한다. 총 세 가지 경로를 생각해볼 수 있는데, (1) $ab$ 를 거쳐가는 경로 (2) $cd$ 를 거쳐 가는 경로 (3) $ef$ 를 거쳐 가는 경로다. (1) $ab$ 를 거쳐가는 경로 길이 하나 뿐이므로 경로의 값을 모두 더해서 구하면 된다 -> $3$ (2) $cd$ 를 거쳐 가는 경로 $c$ 와 $d$ 사이가 싸이클 형식으로 되어 있으므로 $cd$ 안에서 싸이클을 돌고 이동할 수 있다 단 이 경로의 경우 싸..
빅오표기법(Big-O notation)과 시간복잡도
2022. 9. 25. 23:41
컴퓨터/알고리즘&자료구조
빅오표기법과 시간복잡도 정의 - 인수가 특정 값이나 무한으로 향할 때 함수의 극한 행위(limiting behavior)를 표현해주는 수학적 표기 -> 데이터가 늘어날 때 알고리즘 성능이 어떻게 바뀌는가? - 알고리즘의 효율성을 상한선 기준으로 표기해준다 -> "최악의 시나리오" 복잡도 시간복잡도와 공간복잡도 - 시간복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수 ("데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가") - 공간복잡도 : 알고리즘이 실행될때 사용하는 메모리의 양 수학적 정의 $n \geq n_{0}$ 인 모든 $n$ 에 대해 $f(n) \leq cg(n)$ 인 양수 $c,\ n_{0}$ 가 존재한다면, $f(n)$ 을 $O(g(n))$ 이라고 나타낼 수 있다 $n$은 $O(n..