본문 바로가기

Programming

 (110)
벨만 포드 알고리즘 (Bellman-Ford-Moore Algorithm) 1. 개념 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘. 다익스트라 알고리즘과는 다르게 음의 가중치를 가지는 간선이 있어도 가능하다. 또한, 그래프에 음의 가중치를 가진 사이클의 존재 여부를 확인할 수 있다. 2. 구현 V개의 정점과 E개의 간선을 가진 가중 그래프에서 어떤 정점 A에서 B까지의 최단거리는 최대 V-1개의 간선을 사용한다는 아이디어로 시작한다. 1) Distance[i] : 출발점(S)에서부터 i 정점까지의 최단거리를 저장하는 배열. Distance[S] = 0 으로 초기화하고, 나머지는 모두 무한대로 초기화 2) V-1 번 모든 간선을 확인해 아래의 조건을 만족할 때마다 최단거리배열을 갱신한다. - ..
[백준 1735번] 분수 합 link : https://www.acmicpc.net/problem/1735 분수 합 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB72653012255543.298%문제분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.입력첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.출력첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출..
유클리드 호제법(Euclidean algorithm) 1. 개념 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다. 호제법이란 두 수가 서로의 수를 나누어 원하는 수를 얻는 알고리즘이다. 2개의 자연수 A B (A>B)에 대해 A를 B로 나눈 나머지를 r이라고 했을 때 A와 B의 최대공약수는 B와 r의 최대공약수와 같다는 성질을 이용한다. 2. 구현 1) 재귀호출 1234int gcd(int a, int b){ return b ? gcd(b, a%b) : a;}cs 2) 반복문 12345678910int gcd(int a, int b){ while (b > 0) { int q = a; a = b; b = q % b; } return a;}cs * 응용 유클리드 호제법을 응용하면 최소공배수 또한 구할 수 있다. 간단하게 곱하고 나누..
크루스칼 알고리즘(Kruskal's Algorithm) - 최소 신장 트리(Minimum Spanning Tree) 1. 개념 크루스칼 알고리즘은 최소 신장 트리를 찾는 알고리즘이다. 최소 신장 트리는 무향 연결 G에서 간선의 가중치의 합이 최소인 신장 트리이다. 간선의 개수 E, 정점의 개수 V 일때 O(ElogV)의 시간복잡도를 가지는 알고리즘이다. 2. 구현 1) V개의 정점, E개의 간선을 가진 가중 그래프 G에서 모든 간선을 오름차순으로 정렬한다. 2) 정렬된 간선 목록에서 처음부터 마지막까지 아래의 과정을 반복한다. - 간선 목록에서 하나를 꺼내 해당 간선의 두 정점이 연결되어 있는지 확인한다. - 연결되어있지 않다면 두 정점을 연결한다. 구현할 때 팁은 오름차순 정리는 '우선순위 큐'를 사용하고, 두 정점의 연결 확인은 'Union-find'를 사용하는 것이다. 또한, cnt 변수를 따로 주어서 정점이 하..
다익스트라 알고리즘(Dijkstra Algorithm) 1. 개념 다익스트라 알고리즘은 어떤 노드에서 다른 노드까지의 거리(가중치)가 주어졌을 때 특정 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 이때 음의 가중치가 존재해서는 안되고, 방향-무방향 그래프 모두 가능하다. 2. 구현 Distance[i] : 출발점(S)에서 i 정점까지의 최단거리를 저장하는 배열 --> 초기화 과정에서 Distance[S] = 0 을 제외한 나머지는 모두 무한대로 초기화한다. 방문하지 않은 정점 중에서 Distance가 최소인 정점 I를 선택한다. 정점 I와 인접한 모든 정점 J에 대해서 현재까지 저장된 최단거리보다 새로운 정점을 거쳐서 가는 거리가 더 작을 경우에는 D[j] = D[i] + 새로운 정점까지의 거리로 갱신한다. 말로만 설명해서는 알기 힘들고 ..
서로소 집합(Disjoint Set: Union-Find) 1. 개념 Disjoing Set란 공통 원소가 없는 "상호 배타적"인 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 서로소 집합을 만드는 과정을 Union-Find 라고 한다. 2. 구현 Union-Find는 3가지 과정을 통해 진행된다. 1) 초기화 : N 개의 원소가 각 정해진 초기 집합에 있도록 설정 2) Union : 두 원소 a,b가 주어졌을 때 이들이 속한 두 집합을 하나로 합함 3) Find : 원소 a가 주어졌을 때 이 원소의 속한 집합을 찾음 1234567891011121314151617vector parent, rank_cnt; for(int i=0; i rank_cnt[v]) swap(u,v); parent[u] = v; if(rank_cnt[u] ==..
[백준 1753번] 최단경로 link : https://www.acmicpc.net/problem/1753 최단경로 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB251867237339525.808%문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 ..
[백준 1922번] 네트워크 연결 link : https://www.acmicpc.net/problem/1922 네트워크 연결 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB74113952232651.563%문제도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 ..

티스토리툴바