L.O.K

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net ◎ 문제풀이 사건의 전후관계라는 말에서 Floyd-Warshall 알고리즘을 떠올릴 수 있어야 한다. Floyd-Warshall은 A->B를 가고 B->C를 갈 수 있으면 A->C를 갈 수 있다는 원리를 적용하여 최단경로를 구하는 알고리즘이다. A사건 후 B사건이 발생하고 B사건 후 C사건이 발생하면 A사건 후 C사건이 발생한다. 이것이 성립한다면 B사건 전 A사건이 발생하고 C사건 전 B사건이 발생하면 C사건 전 A사건이 발생함을 의미하기도 한다. 이런..

1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net ◎ 문제풀이 문제를 풀려면 우선순위큐 두 개를 사용해야 한다. 입력받은 주유소는 우선순위큐에 저장하고 거리를 기준으로 오름차순하여 정렬한다. 오름차순으로 정렬해야 현재 자동차 주유량을 기준으로 주유소에 차례로 접근이 가능하다. 현재 자동차 주유량이 10L라고 해보자. 10L로 접근가능한 주유소를 우선순위큐에서 하나씩 꺼낸다. 주유소의 주유량을 주유량 우선순위큐에 저장한다. 주유량 우선순위큐는 내림차순이다. 주유량 우선순위큐에..

1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net ◎ 문제풀이 풀이를 알면 굉장히 쉬운 문제인데... 쉬운 풀이까지 가기란 참으로 어려운 것 같다. 변수(range)를 하나 선언한다. 변수(range)는 현재 설치된 널빤지 정보를 갖는다. range가 9이면 현재 9까지 널빤지가 설치된 것이다. 처음에는 설치된 널빤지가 없으니 range는 0이다. 다음 물웅덩이가 3(start)부터 10(end)까지라고 가정해보자. start(3)가 range(0)보다 크므로 range를 start(3..

10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net ◎ 문제풀이 ( 1의 무게 ) > ( 4의 무게 ) 이고 ( 4의 무게 ) > ( 3의 무게 ) 이면 ( 1의 무게 ) > ( 4의 무게 ) > ( 3의 무게 ) 가 성립된다. 위 관계가 성립되지 않는 것의 개수를 구해야 한다. 1,2,3,4 .. 를 노드로 보고 크고 작음의 관계를 간선으로 한다면 그래프를 떠올릴 수 있다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란? [Algorithm] 다익스트라 알고..

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net ◎ 문제풀이 각 지점에서 트럭이 택배를 싣고 내릴 때, 최대 몇 개의 택배를 전달할 수 있는지 묻는 문제이다. 가장 최적의 상황을 발상하기 어려운 문제였다. 처음에는 시작점을 오름차순하고 그 다음 도착점을 오름차순하여 택배를 트럭에 싣는 방식을 생각했다. 그러나 문제가 있었다. 지점이 1 부터 5까지 있다고 해보자. 1을 시작으로 하고 5를 도착으로 하는 택배는 1부터 5까지 트럭이 이동하는 동안 공간을 차지하고 있게 된다. 이는 최적의 상황..

11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net ◎ 문제풀이 아직까지는 하나의 알고리즘 문제에 다른 알고리즘이 응용되는 문제를 푸는게 쉽지 않은 것 같다. '파일 합치기' 문제도 DP 알고리즘에 누적합 알고리즘을 적용해야 풀리는 문제이다. 파일은 최종적으로 두개의 묶음으로 합쳐진다. dp[i][j]가 i부터 j까지 묶음의 최대값이라고 해보자. > dp[1][5] = dp[1][1] + dp[2][5] + C1 ~ C5까지의 합 > dp[1][5] = dp[1][3] + dp[4][5] + C1 ~ C5..

https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net ◎ 문제풀이 [백준] 13334 - 철로 문제 링크: https://www.acmicpc.net/problem/13334 알고리즘 실력이 나름 된다고 근본없는 자만심에 가득... blog.naver.com 위 포스팅을 참고하여 풀었다. 아무리 생각해도 시간복잡도가 O(N²) 풀이만 생각났는데 최소Heap을 이용하면 O(NlogN) 시간복잡도가 가..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net ◎ 문제풀이 근처 빵집에 위치한 가스관(열)과 원웅이네 빵집의 가스관(열)을 연결하는 경로의 최대 개수를 구하는 문제이다. 중요한 조건은 세 가지가 있다. 1) 파이프라인 연결은 중간에 건물이 있으면 연결되지 못한다. 2) 한번 설치된 파이프라인 경로는 다른 경로와 겹치지 않는다. 3) 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래로만 설치가 가능하다. 1)은 백트래킹 가자치기 조건이다. 2)는 한번 방문한 노드는 ..

9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net ◎ 문제풀이 사전 순서로 할 때, 주어진 단어의 알파벳으로 구성된 주어진 단어의 다음 단어를 찾는 문제이다. 처음에는 DFS로 풀었다. DFS로 사전순서대로 탐색하다가 주어진 단어의 다음 단어를 찾는 식이었다. 그런데 이는 메모리 초과가 발생했다. DFS를 하려면 방문처리를 위한 배열도 생성해야 하는데, 그런거 없이 오로지 문자열만을 조작하여 문제를 풀어야 했다. 어떠한 알고리즘이 필요한 거였는데, 잘 몰라서 구글링을 하였다. 원리는 생각보다 복잡했다..

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net ◎ 문제풀이 두 개의 노드에서 공통 부모를 찾는 문제이다. 1) 부모테이블을 만든다. 2) 루트를 찾는다. 3) While문 안에 While문을 넣어 이중for문처럼 하나씩 비교하여 공통부모를 찾는다. ◎ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..