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/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐를 사용해야 하는 문제이다. 핵심 단순하게 풀려고 하면 시간복잡도에 의해 실패하게 된다. 따라서 우선순위 큐를 활용하여 풀어야 한다. 작은 값, 큰 값을 우선순위로 갖는 큐를 2개 만든다. 이후 minQ, maxQ라고 한다면, 아래와 같은 로직으로 작동하게 된다. 최대/최소 우선순위 큐의 크기가 같다면 최대 큐에 숫자를 입력해 준다. 같지 않다면 최소 큐에 숫자를 입력해..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 핵심 우선 소수를 리스트에 담아야 한다. 그러기 위해서는 소수를 찾아야 하는데, 단순한 방법으로 찾게 되면 너무 많은 시간이 걸리게 된다. 따라서 에라토스테네스의 체를 사용해야 한다. 이를 활용해 투포인트를 사용하면 쉽게 구할 수 있다. 정답 코드 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List List = ne..
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..
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 예전에 프로그래머스에서 똑같은 문제를 풀이했던 적이 있다. 이번에는 우선순위 큐를 사용하는 것이 아닌 다른 방법을 사용하였다. 핵심 https://kimtaesoo99.tistory.com/135 [프로그래머스] 이중우선순위큐 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포..
