공부하는 블로그

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존� www.acmicpc.net 다익스트라 알고리즘을 이용하여 최단 경로를 찾는 문제에서 경유지 두 군데가 추가된 문제이다. import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static class Node implements Comparable{ int v; int d; public Node(int v, in..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 알고리즘을 이용하여 가중 그래프에서 출발 정점으로부터 각 정점의 최단 경로를 구하는 문제이다. import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static class Graph implements Comparable { int vertex; int weight; public Graph(..

Dijkstra Algorithm ? 다익스트라 알고리즘(Dijkstra Algorithm)은 가중치를 가진 그래프에서 최단 경로를 탐색하는 알고리즘이다. 단, 가중치가 양수일 경우에만 사용이 가능하다. 다익스트라 알고리즘의 기본 로직은 출발 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단 거리를 갱신해나간다. 이러한 방식으로 출발 정점에서부터 다른 모든 정점까지의 최단 경로를 구할 수 있다. 그 과정은 다음과 같다. 1. 출발 정점으로부터 각 정점에 도달하는데까지 걸리는 시간을 계산한다. (연결이 되지 않았다면 가중치는 ∞) 2. 방문하지 않은 정점 중에서 제일 짧은 시간이 걸리는 정점을 찾는다. 3. 찾아낸 정점에서 이웃 정점에 도달하는데 걸리는 시간을 계산한다. 만약 이전에 기록한 시간보다 ..

위상 정렬(Topological Sort) ? 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조이다. 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프는 여러 위상 정렬이 가능하다. 위상 정렬 구현(in JAVA) import java.util.ArrayDeque; import java.util.ArrayList; public clas..

힙 정렬(Heap Sort) ? 힙 정렬은 말 그대로 자료구조 중 하나인 힙을 이용하여 정렬을 하는 방법이다. 내림차순 정렬을 위해서는 최대힙을, 오름차순 정렬을 위해서는 최소힙을 구성하면 된다. 힙에 대한 설명은 아래의 포스팅을 참고하자. Algorithm | 자료구조 : 힙(Heap) Heap ? 힙(Heap)은 부모 노드와 자식 노드 간에는 키 값의 대소관계가 존재하는 완전 이진트리이다. 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며 형제 사이에는 대소관계가 정해지지 gongbu-ing.tistory.com 힙의 삭제 연산은 최상위 노드를 삭제한 후 최하위 노드를 최상위로 끌어와 다시 힙의 구조를 만족시키는 방향으로 재정렬 한다. 그러므로 힙의 삭제연산을 이용하여 최상위에 위치한 루트 노..

퀵 정렬(Quick Sort) ? 퀵 정렬은 분할 정복 알고리즘의 하나로 피벗(pivot)을 정한 뒤 피벗의 위치를 확정해가며 정렬한다. 피벗을 선정하는 기준은 가장 왼쪽, 가장 오른쪽, 가운데, 랜덤 등 다양하며 어떤 피벗이 좋은 피벗인지는 확답할 수 없다. 분할 정복은 대개 재귀호출을 이용하여 구현한다. * 분할 정복 알고리즘 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략 퀵 정렬은 O(nlog2n)의 시간복잡도를 가지는 매우 효과적인 정렬 알고리즘으로, 자바 스크립트의 배열 객체의 내장 함수인 sort의 내부 구조도 퀵 정렬을 따른다. 퀵 정렬의 과정은 다음과 같다. 각 반복 과정에서는 재귀호출이 사용된다. 1. 배열의 안에 있는 요소 하나를 ..

선택 정렬 (Selection Sort) ? 선택 정렬은 제자리 정렬 알고리즘 중 하나로 배열의 첫번째 원소를 두번째 원소부터 마지막 원소까지, 그 다음은 두번째 원소를 세번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 수를 배열의 앞에 순서대로 가져다 놓는 정렬이다. 1회전마다 N개의 모든 원소를 전부 검사하며 이를 원소의 갯수(N개)만큼 반복하게 되므로 O(n^2)의 시간복잡도를 가지게 된다. 선택 정렬은 O(N^2)의 시간 복잡도를 가지고 있어 성능이 다른 정렬에 비해 좋지 못하다. 하지만 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용하면 좋다. 성능이 좋은 정렬들은 오히려 30 이하의 작은 수에서는 성능이 안좋은 경우가 있다. 선택정렬 구현 (in JAVA) publ..

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 우선순위가 정해진 문제를 푸는 순서를 찾아내는 문제이다. 문제를 푸는 순서에 대한 조건은 두 가지가 있다. 1. 순서가 정해진 문제는 순서에 맞춰 풀어야 한다. ---- 위상정렬 2. 가능한 쉬운 문제(문제 번호가 낮은 문제) 먼저 풀어야 한다. ---- 우선순위 큐 import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public ..