Algorithm124 [Kotlin] 백준 12789 : 도키도키 간식드리미 문제 링크 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 해설 스택을 사용하여 문제를 해결할 수 있다. 간식을 받기 위해서는 1번부터 순서대로 간식 받는곳으로 이동해야 한다. 그런데 줄이 뒤죽박죽 섞여있어서 왼쪽에 있는 1열의 공간을 이용하여 줄을 순서대로 간식을 받을 수 있게 해야한다. 이 1열의 공간을 일종의 스택으로 취급하여 문제를 해결하면 된다. 입력받은 학생 번호 순서대로 아래와 같이 간식 받기를 시도한다. 만약 현재 간식을 받아야 할 번호와 줄 맨 앞의 학생 번호가 일치하지 않는다면 대기 공.. 2023. 8. 9. [Kotlin] 백준 13305 : 주유소 문제 링크 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 해설 그리디 입문 문제. 문제의 내용 중에 기름통의 크기가 무제한이라는 언급이 있다. 기름을 무한정 축적할 수 있기 때문에 문제를 쉽게 해결할 수 있다. 마지막 도시까지 이동하는 최소 비용을 구하기 위해서는 다음 도시로 이동해가면서 현재 도시까지의 가장 저렴한 기름값과 남은 거리를 계산하여 더해주면 된다. 각 도시마다 주유소가 있다고 되어있지만 마지막 도시가 곧 도착지점이기 때문에 계산 과정에 포함되지 않아서 굳이 입력받을 필요는 없.. 2023. 7. 27. [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. 이전 1 2 3 4 5 6 7 ··· 16 다음
