문제 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 Queue를 활용해 풀이하면 된다. 먼저 1 ~ num 까지 Queue에 담는다. 이후 while문을 통해 한 장은 버리면서 출력하고 한 장은 뒤로 이동시킨다. 버릴 카드가 없거나 맨 뒤로 이동시킬 카드가 없다면 while문을 종료한다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val num = b..

문제 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 이 문제는 '11053번 가장 긴 증가하는 수열' 문제와 유사하지만 입력 범위가 크기 때문에 DP로 풀이하면 시간초과가 발생한다. 대신 LIS를 구하는 다른 방법인 이분 탐색을 활용해 풀이해야한다. 우선 입력 받은 수열을 가장 긴 증가하는 수열로 만드는 방법을 확인해보자. 어느 수열의 첫 5개의 원소가 [30, 35, 40, 10, 20, ...]일 때 현재까지의 LIS는 [30, 35, 40]이 될 것이다. 여기서 이 LIS는 수열의 다음 원소들에 따..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP를 활용하여 해결할 수 있으며 주어진 예제 입력을 dp 배열로 메모이제이션한다면 다음과 같다. arr 10 20 10 30 20 50 dp 1 2 1 3 2 4 10은 10보다 작은 값이 없기 때문에 길이가 1인 수열이 되고, 50은 10, 20, 30, 50으로 길이가 4인 수열이 된다. 이를 DP로 해결하기 위한 반복문을 만들어보자. 입력 받은 배열을 순회하며 각 원소..

문제 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이 for문을 통해 입력받은 배열을 탐색하며 각 위치에서 현재 색상을 기준으로 아래쪽이나 오른쪽을 바꾸어 가며 확인해주면 된다. 연속된 동일한 색을 찾는 함수에서는 가로 방향과 세로 방향으로 색을 확인해 준다, 코드 import kotlin.math.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() // 오른쪽, 아래로 이동하는 배열 val dx = arrayOf(1, 0) val dy = arrayOf(0, 1) val num = br.readLine().toI..

문제 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 8 X 8 크기의 확인용 배열을 활용하여 입력받은 체스판 배열에서 최소값을 찾아내면 된다. 최소값을 찾는 방법은 for문을 통해 해당 배열의 각 칸을 확인하고, 해당 칸이 홀수 자리에 있는지 짝수 자리에 있는지 확인한다. 그리고 그 칸이 'B'인지 'W'인지를 판별하여 자리에 맞지 않는 색일 경우 값을 증가해주면 된다. 코드 import java.util.* import kotlin.math.* fun main() { val br = Syste..