L.O.K

https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net ◎ 문제풀이 그래프에서 싸이클을 찾고 싸이클과 노드 사이의 거리를 구하는 문제이다. 풀이과정은 3가지 STEP으로 진행된다. STEP1) 그래프를 인접리스트로 구현 STEP2) 싸이클 DFS 알고리즘으로 탐색하기 STEP3) 싸이클과 노드사이의 거리를 DFS로 구하기 - 싸이클 DFS 알고리즘으로 탐색하기 싸이클은 DFS, BFS로 탐색이 가능하다. 문제에서 싸이클은 1..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net ◎ 문제풀이 트리에서 너비가 가장 넓은 레벨과 레벨의 너비를 구하는 문제이다. 위 그림에 힌트가 있다. 세로축은 레벨을 의미한다. 가로축을 보면 좌측부터 노드의 번호가 매겨진다. 8번 노드는 1, 4번 노드는 2, 2번 노드는 3, 14번 노드는 4이다. 가로축을 이용하면 너비를 쉽게 구할 수 있다. 레벨2의 2번노드의 가로축 숫자는 3이고 3번 노드의 가로축 숫자는 15이다. ..

1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net ◎ 문제풀이 수열의 수는 음수 , 0, 양수가 가능하고 두개의 수를 묶어 곱한 뒤 합하는게 가능하다. 이때의 최대값을 구하는 문제이다. 합이 최대가 나오려면 음수와 양수는 분리되어야 한다. 음수와 양수의 곱은 음수가 나오기 때문이다. - 음수인 경우 1) 절대값이 큰값끼리 곱해야 한다. 2) 곱할 음수가 없는 음수는 0과 곱하여 상쇄되어야 한다. 3) 0도 없으면 그대로 음수를 합해야 한다. - 양수인 경우 1) 절대값이 큰값끼리 곱해야 한다. 2) 1은 곱셈..

10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ◎ 문제풀이 N개의 수열에 M개의 수들이 포함되어 있는지를 탐색하려고 한다. N과M은 최대 500,000으로 이중for을 이용한 탐색은 시간복잡도가 O(NM)으로 시간초과가 발생한다. 그러므로 시간복잡도를 O(MlogN)으로 줄일 수 있는 이분탐색을 해야 한다. ◎ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;..

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net ◎ 문제풀이 행렬그래프가 주어지고 싸이클을 찾는 문제이다. 이는 DFS로 접근하면 된다. ◎ 코드 package org.example.dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; //BOJ16929 Two Dots public class Dfs1 { static in..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net ◎ 문제풀이 노드와 노드를 이동하는데 최단거리를 구하는 문제이다. 비용이 동일하면 BFS 알고리즘이 적절하지만 노드와 노드 사이의 비용이 상이하므로 최단경로를 구하는 알고리즘을 사용해야 한다. 특정한 시작점이 주어지고 모든 간선의 비용이 양수라면 다익스트라 알고리즘으로 최단경로를 계산한다. [Algorithm] 다익스트라 알고리즘(Dijkstra)이란? 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘은 특정지점에서 ..

2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net ◎ 문제풀이 일렬로 나열된 와인을 마실 때, 최대 비용으로 마시는 경우를 구하는 문제이다. 단, 연속으로 3잔을 마시지 못한다.  와인의 모든 경우를 따져서 최대 비용을 구하는 문제이니 메모리제이션을 활용한 DP로 풀어주는 것이 좋다. DP로 풀려면 점화식을 구해야 한다.     와인 3잔이 있다. 와인은 마시거나 안 마시거나 2가지 경우를 선택할 수 있다. 그럼 총 8가지 경우의 수가 나온다. 1) O O O2) O O X3) O X O4) X O O5) X X O..

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net ◎ 문제풀이 선이 겹치지 않도록 회로를 구성할 때, 회로가 가질 수 있는 최대 선의 개수를 구하는 문제이다. 1 부터 4까지 선을 하나씩 추가하며 최적의 회로를 만들어 가면 된다. ( Greedy ) 회로에 Start Point 순서대로 선을 하나씩 추가하려고 한다. '현재' 회로의 End Point 중 가장 큰 EndPoint가 추가하려는 선의 End Point보다 작으면 선..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ◎ 문제풀이 여러 개의 나무를 동일한 크기로 잘랐을 때, 자투리로 남는 나무를 가져가는 문제이다. 원하는 만큼의 나무를 가져가려면 어느 정도 동일한 크기로 잘라야 할까? 자르는 크기를 h라고 하면 h는 1 부터 가장 큰 나무의 크기 사이에 있다. 범위 안에서 적절한 값을 구하는 문제인데, 나무의 크기가 1 ≤ M ≤ 2,000,000,000 이므로 엄청나게 ..

7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ◎ 문제해결 이동시 비용이 동일하고 목표까지 최단거리를 구하는 문제이니 BFS 알고리즘으로 풀어야 하는 문제이다. ◎ 코드 package org.example.bfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Stri..