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 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs문제이다. 핵심 1은 벽을 의미하고, 0은 이동할 수 있는 길이다. 만약 벽이 있더라도 1번 부수고 이동할 수 있다. 즉 한 번도 벽을 부수지 않음 -> 벽을 부수고 이동 벽을 이미 부순 경우 -> 이동 불가 가 된다. 하지만 벽을 부수지 않고 이동한 경우가 더 빠를 수도 있다. 따라서 벽을 부수고 탐색하는 경우와 부수지 않고 탐색하는 경우를 가지고 처리해 주었다. ..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net bfs 문제이다. 핵심 이 문제는 시작점이 여러 개인 bfs 문제이다. 시작점이 여러 개라고 해서 크게 달라지는 것은 없다. 각 시작점에서 점차 값을 증가시키면 쉽게 풀 수 있다. 정답 코드 import java.util.*; import java.io.*; public class Main { static int N; static int M; static int[][] map; s..
https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합 문제이다. 핵심 이 문제는 연속한 합이 입력값 M으로 나누어지는 케이스를 구하는 것이다. 이를 각 배열의 합, 그때의 나머지를 구하면 아래와 같다. index 0 1 2 3 4 5 arr[i] 1 2 3 1 2 sum[i] 1 3 6 7 9 sum[i]%M 1 0 0 1 0 이때 우선 나머지가 0인 곳은 이전까지의 합이라 생각할 수 있으며, ..
https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이 문제는 이름에서도 알 수 있듯이 힙 문제이다. 문제자체는 매우 단순하다. 핵심 문제를 그대로 해석하면 0이면 절댓값이 작은 수를 반환하고, 0이 아닌 수이면 큐에 넣는 것이다. 우선큐의 Comparator를 재정의하면 쉽게 풀 수 있다. 정답 코드 import java.util.PriorityQueue; import java.util.Scanner; public class..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 그리디 카테고리에 있는 문제이다. 핵심 이 문제의 핵심은 어떻게 배정을 해야 많은 사람이 이용할 수 있을까?이다. 끝나는 시간이 빠른 순서대로 정렬을 하고 그에 맞게 회의실에 넣어주면 된다. 코드를 보면 쉽게 이해할 수 있다. 정답 코드 import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Scanner; public class Main { public static void main(..
https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 핵심 완전탐색을 하면 시간초과가 뜨게 된다. 따라서 다른 방법을 사용해야 한다. 그리디를 사용해서 풀면 쉽게 풀린다. 자기 자신의 스위치를 누르면 양옆과 본인의 스위치가 변한다. 0~n까지 이동할 때, i-1을 바꿀 수 있는 전구는 i 뿐이다. 즉 첫 번째 전구가 꺼진 경우와 켜진 경우 2가지를 나누어서 풀 수 있다. 정답 코드 import java.util.Scann..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 핵심 이 문제는 DP를 사용하여 쉽게 풀 수 있다. 테이블 정의 - DP [i] = 카드가 i개일 때 지불해야 하는 최대 금액 점화식 찾기 카드가 1개 들어있는 카드팩을 구매하고 카드 i-1개를 구입한다. 카드가 2개 들어있는 카드팩을 구매하고 카드 i-2개를 구입한다. 카드가 3개 들어있는 카드팩을 구매하고 카드 i-3개를 구입한다. 정답 코드 import java.util.Scanner; class ..
https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 핵심 bfs를 안다면 매우 쉽게 풀 수 있는 문제이다. 기존에 다루었던 네 방향에서 조금 응용된 느낌이다. 하지만 똑같은 방식으로 풀 수 있다. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { ..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 이 문제를 해석해 보면, 육지에서 갈 수 있는 끝지점과 끝지점사이의 거리를 구하는 것이다. 단 이동할 때, 가장 빠른 방법으로 간다 즉 BFS를 사용하라는 것이다. 바로 풀어보자. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main{ static int[][] result; stat..
