문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 설명 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 한다. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력된 간선 정보를 저장할 Edge 클래스를 만들고 리스트를 만들어 연결관계를 저장한다. 시작 정점에서부터 인덱스에 해당하는 정점까지의 최단 거리를 나타내는 minLength[] 배열을 만든다. 음의 가중치가 없는 그래프에서 최단 경..
최단 경로의 종류 단일 출발 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 단일 도착 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 단일 쌍 최단 경로 어떤 정점 v에서 w로 가는 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 전체 쌍 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 (플로이드-워셜 알고리즘) 다익스트라 알고리즘 음의 가중치를 갖지 않는 그래프에서 어떤 한 정..
문제 https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 설명 그 간선을 제거했을 때 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 단절선이라 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. 먼저 간선 정보를 저장할 CutLine 클래스를 만들고 단절선을 저장할 배열인 cutList를 만든다. 나중에 단절선을 사전순으로 출력해야 하므로 Comparable 인..
문제 https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 설명 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 각 정점들마다 방문 순서를 부여하기 위한 visited[] 배열과 단절점인지 판단하기 위한 isCutPoint[] 배열을 선언하고 정점간의 연결관계를 입력받아 인접리스트를 만들어준다. 방문하지 않은 정점을 시작으로 DFS 탐색을 수행하여 order를 저장하고 단절..
단절점 무향 연결 그래프에서 하나의 정점과 연결된 간선들을 모두 제거했을 때 두 개의 연결 그래프로 나눠진다면 해당 정점은 단절점이다. 위의 그림에서 주황색 정점들이 단절점이다. 2번 정점을 기준으로 { 1 } 과 { 3, 4, 5, 6, 7, 8 } 으로 나뉘어진다. 4번 정점을 기준으로 { 1, 2, 3 } 과 { 5, 6, 7, 8 } 으로 나뉘어진다. 6번 정점을 기준으로 { 1, 2, 3, 4, 5, 8 } 과 { 7 } 으로 나뉘어진다. 단절점 찾기 무향 연결 그래프에서 어떤 정점 A에 연결된 정점들에 대해서 우회경로(정점 A를 거치지 않는 경로)가 없는 경우가 존재한다면 A는 단절점이다. 어떤 정점 A와 해당 정점에 연결된 정점 B에 대해서, A가 시작 정점이 아닌 경우 : \(order_A..
정렬 알고리즘 (Sorting Algorithm) 정렬 알고리즘은 크게 비교 방식(Comparisons)과 미비교 방식(Non-Comparisons)으로 나눌 수 있다. 비교 기반 정렬 알고리즘에는 거품 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬이 있다. 미비교 기반 정렬 알고리즘에는 기수 정렬과 계수 정렬이 있다. 거품 정렬 (Bubble Sort) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 수행 과정 1회전에 첫번째 원소부터 마지막 원소까지 인접한 원소끼리 대소를 비교하여 조건에 맞춰 서로 교환한다. 1회전이 끝나면 가장 큰 원소가 맨 뒤에 위치해 있으므로 2회전에는 맨 끝에 있는 원소는 정렬에서 제외한다. 이러한 방식으로 원소..
문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 설명 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력해야 한다. 각 정점의 방문 여부를 체크하기 위한 check 배열과 각 정점의 깊이를 저장할 depth 배열을 만든다. 그리고 각 정점의 \(2^k\) 번째 부모를 저장하기 위해 parent[18][] 배열을 만든다...
최소 공통 조상 (Lowest Common Ancestor / LCA) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 정점 A 혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점 위의 그림에서 13번 정점과 15번 정점의 최소 공통 조상은 5번 정점이 된다. 최소 공통 조상 구하기 선형 탐색 : \(O(depth) = O(N)\) 1. 최상위 조상 정점을 시작으로 DFS 또는 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. 2. 최소 공통 조상을 찾을 두 정점을 확인한다. 3. 먼저 두 정점의 깊이가 같아질 때까지 각각 부모를 따라 거슬러 올라간다. 4. 이때, 가리키는 정점이 다르다면 다시 각각 부모를 따라 하..
