Algorithm/Algorithm Problem

백준 1956 운동(Floyd-Warshall)

1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제를 보면 가중치가 있는 방향 그래프에서 시작점을 따로 정하지 않고 단순히 두 마을이 사이클을 도는지 확인 하는 문제다. 언뜻보면 사이클이라는 단어에서 Union-Find가 생각날 수 있지만 무방향그래프일 때 사용 가능하며 방향 그래프일 때는 DFS로 자기 자신으로 돌아왔을 떄 해주면 되지만 플로이드-와샬을 이용하면 쉽게 가능 플로이드-와샬 후 (i,j)와 (j,i)가 INF가 아니라면 사이클이 있다는 뜻! package pr..

백준 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..

백준 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?) 그래야 순차적으로 회의실을 늘릴지말지 판별할 수 있지 않..

백준 17406 배열 돌리기4(구현)

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 1. 배열에 대해서 permutation을 돌리는 기법이 자바에서 구현하기 많이 힘들었다. ==> row에 대한 인덱스들만 따로 모은 1차원 배열을 permutation 돌리는 기법으로 하는게 정석인 것 같음 2. rotation 시키는 방법 2-1. (in java) list에 넣고 Collections.rotate() 2-1-1 (in python) queue.r..