본문 바로가기
  • 개발하는 곰돌이

Algorithm/BOJ114

[Kotlin] 백준 11866 : 요세푸스 문제 0 문제 링크 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 해설 문제의 예시를 그림으로 나타내면 다음과 같다. 그림을 보면 다음에 나갈 사람의 위치는 시작 위치 + \(k\) - 1인 것을 알 수 있다. 즉, 다음 순서로 나갈 사람의 위치는 이전에 나간 사람의 위치에 \(k-1\)을 더하면 된다. 이제 남은 사람의 수가 \(k\)보다 작아졌을 때의 처리만 하면 되는데, 이 때는 앞에서 구해진 다음 순서로 나갈 사람의 위치가 남은 사람의 수보다 작아질 때까지 남은 사람의 수를 빼주면 된다. 나간 사람의 번호는 별도의 배열에 저장하고 문제의 조건에 맞는 형태로 출력하면 된다. Code fun .. 2022. 12. 8.
[Kotlin] 백준 2563 : 색종이 문제 링크 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제 해설 2차원 배열을 이용하면 쉽게 풀 수 있는 문제다. 2차원 배열에서 한 칸의 넓이를 1이라고 생각하고 문제를 풀어나간다. 문제에 흰색 도화지의 가로, 세로 길이가 각각 100이라고 명시되어 있으므로 100\(\times\)100 크기의 Boolean 배열을 선언한다. 그 후 색종이의 개수만큼 입력받은 색종이의 위치부터 + 10까지의 값을 true로 변환하는 과정을 반복한다. 최종적으로 배열 내의 true의 개수가 색종이가 붙은 영역의 넓이가 된다.. 2022. 12. 7.
[Kotlin] 백준 11286 : 절댓값 힙 문제 링크 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해설 힙은 우선순위 큐를 이용하여 구현하면 되지만 우선순위에 대해서 조금 생각해볼 수 있는 문제다. 기본적으로 수를 담는 우선순위 큐는 작은 수의 우선순위가 높은데, Kotlin에서는 람다식을 이용하여 손쉽게 우선순위를 변경할 수 있다. 따라서 우선순위 큐 객체를 생성할 때 절대값이 같은 경우에는 작은 수가, 그 외에는 절대값이 작은 수가 우선순위가 높아지도록 변경한 후 문제의 조건을 구현하면 된다. Code import ja.. 2022. 12. 6.
[Kotlin] 백준 11723 : 집합 문제 링크 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 해설 단순한 구현 문제지만 메모리 제한이 매우 적다. 주어지는 입력의 수가 1부터 20까지밖에 되지 않으므로 크기가 21인 Byte 배열을 만들어서 구현하였다.(0 : 배열에 없음, 1 : 배열에 있음) Code import java.util.StringTokenizer fun main() = with(System.`in`.bufferedReader()) { val bw = System.out.bufferedWriter() val s = ByteArray(21) var st: Str.. 2022. 12. 5.
[Kotlin] 백준 5430 : AC 문제 링크 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 해설 리스트나 덱(Deque)을 이용해서 풀 수 있는 문제다. 풀이 과정은 두 방법 모두 동일하다. 가장 먼저 입력에서 [x1,...,xn] 형태로 주어진 배열을 덱에 삽입하기 위해 입력값을 파싱해줘야 한다. slice() 메소드로 입력의 시작과 끝에 있는 대괄호를 제외한 문자열을 만들고 콤마(,)를 구분자로 하여 각 정수값을 덱에 삽입한 후 주어진 함수 연산을 시작한다. 문제의 함수에서는 뒤집기 연산이라는 것이 있는데 R이 들어왔을 때 정말로 뒤집어서 계산하면 안된다. R이 들어올 때마다 뒤집기를 수.. 2022. 12. 4.
[Kotlin] 백준 7662 : 이중 우선순위 큐 문제 링크 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 해설 처음에는 최대힙과 최소힙을 하나씩 만들어서 구현하려고 했는데 시간 초과가 났다. 제거 연산을 수행할 때 'D 1'이면 최대힙에서 제거한 값을 최소힙에서 remove()로 제거하고, 'D -1'이면 최소힙에서 제거한 값을 최대힙에서 같은 방법으로 제거하는 방식으로 구현했는데 저 remove() 과정에서 힙을 탐색해야 하다보니 시간을 초과한 것 같아서 다른 방법을 찾아보기로 했다. 그런 이유로 TreeMap을 이용하여 문제를 풀어보았는데 성.. 2022. 12. 4.
[Kotlin] 백준 1654 : 랜선 자르기 문제 링크 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 해설 2805 - 나무 자르기와 유사한 이진 탐색 문제다. 차이점은 목표치와 동일하면 바로 종료할 수 있던 나무 자르기와 달리 이 문제는 목표치(필요한 랜선의 개수)에 도달하더라도 랜선의 길이를 최대로 하기 위해 계속 검사를 해야한다는 점이다. Code fun main() = with(System.`in`.bufferedReader()) { val (k, n) = readLine().split(' ').map { it.. 2022. 12. 3.
[Kotlin] 백준 1874 : 스택 수열 문제 링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 해설 문제를 이해하기만 하면 스택을 이용하여 손쉽게 풀 수 있다. 예제 입출력의 경우를 예로 들어 보자. 4, 3, 6을 수열에 넣기 위한 동작을 그림으로 표현하면 다음과 같다. 그림에 대해 설명하자면 처음에 수열에 4를 추가해야 하는데 스택에 4가 없기 때문에 1, 2, 3, 4를 차례대로 삽입한다. 이후 스택의 맨 위에 있는 4를 제거하여 수열에 추가한다. 다음.. 2022. 12. 2.

티스토리툴바