전체 글
백준 1238 파티(최단경로 - 다익스트라)★★
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 가중치가 있는 방향 그래프 문제이며 From 특정 노드 To 다른 모든 노드 : 최단 경로 알고리즘 집 -> 파티장소 파티장소 -> 집 각각의 최단 경로는 다를 수 밖에 없다. 따라서 각각의 다익스트라를 구하고 각 케이스마다 경로를 합하여 가장 큰 값을 출력한다. package practice; import java.io.BufferedReader; import java.io.IOException; import java.io.Inp..
Coding Test(최단 경로 - Dijkstra, Bellman-Ford, Floyd-Warsahall)
다익스트라 알고리즘(Dijkstra Algorithm) 특정한 노드에서 다른 모든 노드로의 최단경로를 구하는 알고리즘 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구함 그리디를 이용한 알고리즘으로 MST의 PRIM()과 유사 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 가중치 없는 경우 1 BFS 가중치 있는 경우 하나의 정점 양수 Dijkstra 음수 Bellman-Ford 모든 정점 Flod-Warsahall 1. 출발 노드를 설정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 5. 위 과정..
Coding Test(Prim Algorithm)
Prim의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 한다. PriorityQueue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 구현 방식이 유사하다. BFS + PriorityQueue 1. 임의 정점을 하나 선택해서 시작 2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 3. 모든 정점이 선택될 때 까지 1,2과정 반복 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리르 구성 하므로 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입 하면서 트리를 구성하기 때문에 사이클..
Coding Test(Kruskal Algorithm)
최소 신장 트리(MST : Minunum Spanning Tree) 신장 트리(Spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리 신장 트리(Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않은 부분 그래프 정점이 N개인 무방향 그래프에서 나올 수 있는 최대 간선의 수 : N(N-1)/2 정점이 N개인 방향 그래프에서 나올 수 있는 최대 간선의 수 : N(N-1) 크루스칼 알고리즘(Kruskal Algorithm) O(ElogE) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 = 최소 신장 트리를 만들기 위한 알고리즘 그리디 알고리즘(결정의 순간..
백준 17135 캐슬 디펜스(구현, 조합, BFS) ★★
https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 단순 구현 문제인 줄 알고 쉽게 접근했지만 다양한 알고리즘을 사용해야 했던 문제였다. 1. 궁수의 위치를 정해야 하기 때문에 Combination 사용 2. 궁수가 공격을 해야하는데 동일한 거리의 적이 여러명 있으면 가장 왼쪽인 적을 죽인다 => BFS를 통해 가장 가까운거리를 탐색하고 방향벡터를 [좌 상 우] 방향으로 탐색함으로써 가장 가까운 애들 중 가장 왼쪽에 있는 적을 탐색하게 만든다 why?) 만약..
백준 1826 연료 채우기(우선순위 큐, 그리디)★★
https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 주유소에 최대한 적게 가야한다는 것을 보고 그리디적으로 접근해야됨을 알았다. 어떻게 하면 최대한 적게 갈 수 있을까? 내가 보유한 P만큼 앞으로 나갈 수 있는데 P만큼 전진 했을 때 만약 도착지점에 가지 못했다면 지나친 주유소들 중 연료를 가장 많이 주는 곳에서 채우는게 가장 이득이지 않겠는가?! ==> Max-Heap 거리는 1,000,000이기 때문에 크기..
백준 최소 회의실 개수(우선순위 큐, 그리디)★★
https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 매우 어려운 문제였지만 원리를 이해한다면 쉽다. > 접근방법 우리는 회의실을 가장 적게 쓰고 싶어한다. 주어지는 입력은 무작위로 들어올텐데 문제를 읽어보면 진행되는 회의의 종료시간과 다음 회의 시작시간의 상관관계가 가장 중요하다는 것은 알 수 있다. 즉, 회의 데이터들의 입력을 받고 시작시간 기준으로 정렬해줄 필요가 있다. why?) 그래야 순차적으로 회의실을 늘릴지말지 판별할 수 있지 않..