Algorithm114 [Kotlin] 백준 1021 : 회전하는 큐 문제 링크 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 해설 덱의 양방향 삽입, 삭제 연산을 통해 회전하는 큐를 구현할 수 있다. 수를 뽑아내기 위한 인덱스는 항상 가장 앞으로 고정되어 있으므로 주어진 입력의 순서대로 수를 뽑으려면 원소들을 좌우로 이동시키면서 주어진 수가 가장 앞으로 오게 만들어야 한다. 예제 2의 경우는 아래 그림과 같은 과정을 거치게 된다. 이 때 뽑아낼 수가 큐의 가장 앞에 오려면 왼쪽 또는 오른쪽 중에 더 가까운 쪽으로 \(x\)번 수를 이동시켜야 한다. 이 방향은 큐에서.. 2023. 7. 11. [Kotlin] 백준 2485 : 가로수 문제 링크 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 문제 해설 각 가로수의 거리 간격이 동일해지도록 새로운 가로수를 심어야한다. 단순히 생각하면 각 가로수 사이의 거리를 구해서 거리의 최소값 간격으로 심으면 될 것 같지만 예제 2번의 경우가 반례가 된다. 이 경우에는 각 가로수 사이의 거리가 4, 6, 6이 되어 최소 거리가 4가 된다. 이렇게 되면 2부터 4의 간격으로 나무를 심게 되면 [2, 6, 10, 12, 14, 18]이 되기 때문에 각 가로수 사이의 거리가 일치하지 않는다. 이 문제는.. 2023. 7. 5. [Kotlin] 백준 1002 : 터렛 문제 링크 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제 해설 2개의 점과 각 점에서 류재명까지의 거리가 주어지고 이를 이용하여 류재명이 있을 수 있는 좌표의 수를 구하는 문제이다. 문제를 잘 보면 조규현과 백승환의 좌표를 각각 A, B라고 했을 때, A가 중심이고 반지름이 r1인 원과 B가 중심이고 반지름이 r2인 원이 만나는 점의 개수를 구하는 문제라는 것을 알 수 있다. 이제 각 경우에 대해 그림을 보면서 생각해보자. 1. 두 원의 접점이 무수히 많은 경우 두 원의 중심과 반지름의 길이가 모두 같은 경우는 곧 두 원이 일치하는 경우이다. 문제의 입력.. 2023. 6. 22. [Kotlin] 백준 14943 : 벼룩 시장 문제 링크 14943번: 벼룩 시장 벼룩시장에서 사람들이 벼룩을 사고 판다. 놀랍게도 각 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합은 같다. 벼룩을 사거나 파는 사람들은 서로 일렬로 길게 서 있으며, 인접한 가게 사이 www.acmicpc.net 문제 해설 각 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합이 같다는 점이 문제 풀이에 큰 도움이 된다. 벼룩을 가장 저렴하게 배달하려면 결국 가장 가까운 사람들에게 벼룩을 배달해야 한다. 문제에서 양수는 벼룩을 파는 사람, 음수는 벼룩을 사는 사람이라는 조건이 있다. 사려고 하는 벼룩의 합이 파는 벼룩의 합과 같고, 벼룩을 가장 저렴하게 배달하려면 가장 가까운 사람에게 배달해야 하기 때문에 시작점에서 출발하여 각 지점의 모든 벼룩을 배달할 벼룩에 추.. 2023. 5. 15. [Kotlin] 백준 1700 : 멀티탭 스케줄링 문제 링크 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 해설 OS의 페이징 기법을 모티브로 한 문제인 것 같다. 멀티탭 구멍의 개수는 메모리의 크기를, 각 전기용품은 메모리에 적재되는 페이지라고 볼 수 있다. 페이징 기법을 위한 페이지 교체 알고리즘은 FIFO, LRU, LFU 등 다양한 종류가 있는데, 이 문제에서 사용할 알고리즘은 OPT(Optimal) 알고리즘이다. OPT 알고리즘은 아래와 같이 동작한다. 이미 메모리에 페이지가 적재되어 있으면 다음 페이지로 넘어간다. 메모리에 페이지가 적재되어.. 2023. 5. 4. [Kotlin] 백준 27435 : 파도반 수열 2 문제 링크 27435번: 파도반 수열 2 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ T ≤ 1,000, 1 ≤ N ≤ 1018) www.acmicpc.net 문제 해설 [Kotlin] 백준 9461 : 파도반 수열의 확장 버전 문제이다. 이전 문제는 입력값이 최대 100이었기 때문에 DP로 충분히 해결할 수 있는 문제였지만, 이 문제는 입력값이 최대 1018이나 되기 때문에 DP로 풀게 되면 시간초과가 발생한다. 따라서 파도반 수열의 성질을 이용하여 풀어야 한다. 파도반 수열에 대해 다음과 같이 피보나치 Q-행렬과 유사한 행렬(이하 Q-행렬)이 존재한다. $$Q=\begin{bmatrix}0&1&0\\0&0&1\\1&1&0\\\e.. 2023. 4. 27. [Kotlin] 백준 27450 : 플래그 대사 좀 그만 말해요 문제 링크 27450번: 플래그 대사 그만 좀 말해요 “해치웠나?” 악의 단체의 리더 한별이는 자신의 부하들이 “해치웠나?”라는 말을 들을 때마다 강해지는 것을 보고 이를 악용해 부하들을 강화시켜 세계를 정복하려고 한다. 부하들은 좌우 www.acmicpc.net 문제 해설 가장 기본적인 풀이 방법은 한별이가 각 위치에서 "해치웠나?"를 외칠때마다 외침의 영향을 받는 부하들의 강함을 증가시켜 주는 것이다. 하지만 \(N\)과 \(K\)가 각각 최대 50만이기 때문에 이 방법을 사용하면 각 위치에서 1번의 연산만 수행하더라도 1250억번의 연산을 수행하게 되어 시간 초과가 발생한다. 이 문제를 좀 더 효율적으로 해결하기 위해서는 누적 합을 응용하는 방법을 사용할 수 있다. 어떤 지점 \(p\)에서 \(i\.. 2023. 4. 23. [Kotlin] 백준 27960 : 사격 내기 문제 링크 27960번: 사격 내기 A, B, C는 올해에도 예비군 훈련을 받으러 간다. 이번 예비군 훈련 과정 중에는 영점 사격이 있으며, 10개의 과녁 각각에 점수를 매겨 맞춘 과녁 점수의 총합을 측정한다. 과녁을 맞혔을 때, 과녁별 www.acmicpc.net 문제 해설 과녁별 점수가 \(2^n\)의 형태이고 각 과녁은 사람별로 최대 한 번만 맞힐 수 있다는 점에 주목하면 된다. 즉, A와 B의 점수는 2진수로 표현했을 때 맞힌 표적이 1이고 빗맞힌 표적이 0으로 표현된다. 여기서 C는 둘 중 한명만 맞힌 표적은 다 맞히고, 둘 다 맞히거나 둘 다 빗맞힌 표적은 빗맞혔다고 한다. 이는 C의 점수가 곧 각 비트를 XOR 연산한 결과와 같다는 뜻이 된다. Code fun main()=print(read.. 2023. 4. 20. 이전 1 2 3 4 5 6 ··· 15 다음
