알고리즘

플로이드 와샬 알고리즘은 다익스트라, 벨만 포드 알고리즘과 달리 '모든 정점에서 다른 정점까지의 최단거리'를 구한다. 다익스트라처럼 큐에 넣어서 거쳐가는 지점을 뽑아 쓰는 것과 달리 플로이드 와샬은 거쳐가는 지점을 중심으로 해서 다시 모든 노드를 탐색한다. 따라서 시간 복잡도는 \(O(N^3)\) 이 걸린다. www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 � www.acmicpc.net 문제 풀이를 통해 알아보면 시간 복잡도가 높은 만큼 입력 범위는 작게 1..

Bellman - Ford 알고리즘은 다익스트라 알고리즘과 달리 모든 노드를 주기적으로 갱신시켜주기 때문에 \(O(V*E)\)가 걸리지만 음의 가중치를 포함한 노드들에 대해서도 성공적으로 탐색할 수 있다. www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 대표적인 벨만 - 포드를 사용한 문제이다. 우선 각 간선의 수만큼 입력을 받는데 편하게 계산하기 위해 좌표들에 -1씩 해서 받아줬다. cin >> ..

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구의 관계가 주어진다. 예제를 보면 Fred Barney Betty Wilma Barney Betty 가 주어지는데 Fred - Barney 가 연결되었으니 총 2명 Betty - Wilma 가 연결되었으니 총 2명 Barney - Betty 인데 Betty - Wilma, Barney - Fred 가 서로 친구이니 총 4명 즉, 집합이 주어지는데 같은 부모 노드 같은 구성원이 존재한다면 Union..

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 도시의 수가 주어지고 인접 행렬이 반사 행렬로 주어지니 무향 그래프로 봐도 된다. 이후 여행 갈 도시의 동선이 주어지는데 이를 path 배열로 받아줬다. 처음에는 DFS로 접근해서 void DFS(int cur) { vis[cur] = true; for (int i = 1; i j를 union 해준다 이후 path 배열을 입력받고 path[0] 의 루트 노드를 찾는다 path 배열을 돌면서 path[0] 의 루..

Disjoint-Set (서로수 집합) 이라고도 불리는 유니온 파인드는 여러 집합이 주어지면 각 집합의 루트 노드가 무엇인지, 또는 Union(합집합) 연산을 손쉽게 하기 위한 일종의 자료구조이다. 큰 틀로는 집합의 부모 노드를 찾는 find 함수, 각 집합을 병합하는 union 함수를 만들어주면 된다. int find(int x) { if (parent[x] < 0) return x; parent[x] = find(parent[x]); return parent[x]; } find 함수부터 살펴보면 parent배열의 초기값은 -1로 설정해둔다(이후에 집합의 크기를 알기 쉽게 하기 위해) 만약 parent [x]가 0보다 작다는 소리는 그 노드가 루트 노드임을 알 수 있다. 그대로 x를 반환하면 된다. 만..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 양수인 산성 용액과 음수인 알칼리성 용액이 주어지면 0과 가장 가까운 값의 두 구간을 찾는 문제다. 투 포인터를 활용하기 위해서 배열을 정렬해준다 왼쪽 포인터와 오른쪽 포인터 S = 0, E = n - 1로 설정해준다 vector에 로 입력받고 두 구간의 합이 양수면 오른쪽을 줄이고 음수면 왼쪽을 줄인다 두 포인터가 서로 교차하면 종료 #include #include #incl..