https://www.acmicpc.net/problem/15559 15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net dfs 문제이다. 핵심 아래 알파벳에 따라 이동하는 길이 정해져 있고, 맵의 크기를 넘어서지 않는다. 즉 무조건 사이클이 생기게 된다. 이때 생기는 사이클의 수를 구하면 된다. 사이클을 구분하기 위해 depth를 증가시키면 탐색한다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; imp..
https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 우선순위 큐를 활용해야 한다. 핵심 시작 시간이 빠른 순으로 정렬 후에 우선큐에서 현재 진행 중인 강의 중 종료 시간이 가장 빠른 강의를 비교한다. 진행 중인 강의의 end값이 다음 강의 start보다 크면 강의실 개수를 1 늘리고, 큐에 다음 강의를 넣는다. 반대의 경우 강의실 1개를 제거한다. 코드를 통해 알아보자. 정답 코드 import java.io.BufferedReader..
https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net DFS를 사용하여 풀 수 있다. 핵심 사용할 알파벳이 있느냐, 이전 알파벳이 현재 알파벳과 같으냐 이것을 정의하고 풀 수 있다. 이러한 방법을 사용하면 같은 알파벳이지만, 배열위치가 다른 것도 1번만 확인하게 된다. ex) aba' == a'ba 정답 코드 import java.util.Scanner; public class Main{ static int[] alphabet = new int[27]; ..
https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 핵심 처음에 이 문제를 완전탐색을 해야 하는 줄 알았다. 하지만 시간복잡도에서 터지게 된다. 이 문제는 실제 스위치를 켜고 끄는 것이 아닌 행의 패턴을 비교하는 작업이 필요하다. 어떠한 패턴과 같은 행이 있다면 스위치를 눌렀을 때 모두 똑같이 변하게 된다. 이를 이용해서 풀어야 한다. 정답 코드 import java.io.BufferedReader; import java.io.IOExcep..
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 사용하여 풀 수 있다. 핵심 시작점으로부터 +1,-1, *2 위치로 이동할 수 있다. 한번 방문한 곳은 이전에 방문했을 때가 최소이므로 재방문할 필요가 없다. 또한 이동경로를 구해야 하기 때문에 parent배열을 선언하여 이동 전 위치를 저장한다. 정답 코드 import java.util.LinkedList; import java.util.Queue; i..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 문제이다. 핵심 이 문제는 가중치가 있는 다익스트라 문제이다. 가중치가 있기 때문에 클래스를 구현하는 것이 편리하다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; imp..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 이 문제는 부분합과 투포인터를 사용하면 쉽게 풀 수 있다. 핵심 연속된 수를 계속해서 더하다가 합이 원하는 s의 값 이상이 되면 시작점을 한 칸 앞으로 당겨온다. 이후 나머지의 합을 비교하여 계속 s이상이면 다시 시작점을 당기고, 아니면 끝지점을 한 칸 올린다. 자세한 건 코드를 통해 확인해 보자. 정답 코드 import java.io.BufferedReader; import jav..
https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net dfs를 사용하여 쉽게 풀 수 있다. 핵심 dfs를 사용하면 쉽게 풀 수 있다. 가중치가 있기 때문에 Node라는 클래스를 만들어서 활용하였다. 정답 코드 import java.io.*; import java.util.ArrayList; import java.util.List; public class Main{ static List[] nodes; static boolean[] visited; static int distance; public..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 핵심 DFS를 사용하여 풀 수 있다. 실제 부모와 자식관계의 트리이지만 양방향 매핑을 하는 인접 리스트로 표현하였다. 정답 코드 import java.io.*; import java.util.*; public class Main { static int N; static List nodes[]; static boolean[] visited; static int max; publi..
https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 핵심 x + y + z = k 가 돼야 한다. 각각의 원소는 집합에 포함되어 있다. 또한 각각은 같은 값을 가져도 된다. 단순하게 완전탐색으로 풀면 시간복잡도에서 걸리게 된다. (3중 for문) 따라서 이분탐색을 사용하여 더 빠르게 풀 수 있다. x + y = k -z라는 식을 이용하면 된다. 정답 코드 import java.util.ArrayLis..
