BOJ107 [Kotlin] 백준 11637 : 인기 투표 문제 링크 11637번: 인기 투표 각 테스트 케이스는 첫 번째 줄부터 순서대로 출력된다. 최다 득표자가 과반수 득표를 했을경우에는 "majority winner R", 절반 이하의 득표를 하였을 경우엔 "minority winner R"가 되며, 최다 득표자가 없 www.acmicpc.net 문제 해설 간단한 구현 문제이다. 각 테스트 케이스마다 매 입력으로 주어지는 득표 수 중 최대치와 득표 수의 합계를 구한다. 최대 득표 수의 개수가 1이 아니면(= 최다 득표자가 2명 이상이면) "no winner"를 출력한다. 최대 득표 수의 개수가 1이라면 득표 수의 합계를 2로 나눈 값과 최대 득표 수를 비교하여 "majority winner R" 또는 "minority winner R"를 출력한다. Code.. 2023. 2. 8. [Kotlin] 백준 12931 : 두 배 더하기 문제 링크 12931번: 두 배 더하기모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주www.acmicpc.net문제 해설문제는 모든 값이 0으로 채워진 배열을 입력으로 주어진 배열로 만드는 것이지만, 역으로 생각해보면 입력으로 주어진 배열의 모든 값을 0으로 만들기 위한 연산의 최소 횟수를 구하는 문제라는 것을 알 수 있다. 역으로 접근하면 된다는 것을 알았으니 어떻게 연산을 진행할 지 생각해보자. 배열의 모든 값을 반으로 나누는 것이 값 하나를 1 감소시키는 것보다 훨씬 효율적이다. 그런데 홀수는 반으로 나눌 수 없으니 1 .. 2023. 2. 5. [Kotlin] 백준 1629 : 곱셈 문제 링크 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 해설 \(A^B\mod C\)를 구해야 한다. 그런데 \(A\), \(B\), \(C\) 모두 최대치가 Int.MAX_VALUE이기 때문에 정말 정직하게 거듭제곱을 하면 무조건 시간초과가 발생한다. 따라서 효율적인 방법을 찾아서 해결해야 한다. 이 문제는 지수 법칙을 이용하면 수월하게 해결할 수 있다. \(x^{2n}=(x^2)^n\)인 성질과 \(x{n+m}=x^n\times x^m\)인 성질을 이용하여 지수를 계속 반으로 나누면서 밑을 제곱하는 것이다. 예를 들어 \(2^{14}\)를 지수 법칙을 이용해서 .. 2023. 2. 2. [Kotlin] 백준 25306 : 연속 XOR 문제 링크 25306번: 연속 XOR 3에서 5까지의 자연수는 3, 4, 5로, 세 개 존재한다. 세 수를 XOR한 값은 (3 XOR 4) XOR 5 = 7 XOR 5 = 2 이다. www.acmicpc.net 문제 해설 \(A\)와 \(B\)가 최대 \(10^{18}\)이기 때문에 하나씩 차근차근 XOR 연산을 하면 시간 초과가 발생한다. 이 문제를 시간 내에 해결하기 위해선 누적 XOR의 성질을 알 필요가 있다. \(1\leq N\leq 100\)인 \(N\)에 대하여 각 구간별로 누적 XOR을 구해보면 다음과 같은 결과를 얻을 수 있다. 결과를 잘 보면 \(N\)을 4로 나눈 나머지의 값에 따라 규칙적으로 결과가 변한다는 것을 알 수 있다. 1 → 1 2 → \(N+1\) 3 → 0 0 → \(N\.. 2023. 1. 29. [Kotlin] 백준 23300 : 웹 브라우저 2 문제 링크 23300번: 웹 브라우저 2 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 가 각각 주어진다.(1 ≤ N, Q ≤ 2,000) 둘째 줄부터는 Q개의 작업이 주어지며, 각 작업이 의미하는 바는 다음 www.acmicpc.net 문제 해설 뒤로가기 목록을 저장할 스택과 앞으로가기 목록을 저장할 큐를 각각 만들면 손쉽게 해결할 수 있다. 본 코드에서는 덱을 사용했지만 크게 상관은 없다고 생각한다. 압축 기능은 뒤로가기 목록의 2번째 페이지부터 마지막 페이지까지 이동하면서 이전 페이지와 같으면 제거하는 식으로 구현했다. Code import java.util.StringTokenizer fun main() = with(System.`in`.bufferedRe.. 2023. 1. 26. [Kotlin] 백준 11444 : 피보나치 수 6 문제 링크 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 피보나치 수를 구하는 문제지만 입력이 굉장히 큰 경우다. 이 경우 피보나치 수를 구하는 일반적인 식인 \(F_n=F_{n-1}+F_{n-2}\)을 사용하게 되면 최대 \(10^{18}\)번의 연산을 수행해야 하기 때문에 이 방법은 사용할 수 없다. 문제를 해결하기 위해서는 더 효율적인 방법을 찾아야 하는데, 피보나치 수를 구하는 방법 중에는 도가뉴 항등식(d'Ocagne's identity)이라는 것이 있다. 도가뉴 항등식의 형태는 다음과 같다. $$F_{m+n}=F_{m-1}F_n+F_mF_{n+1}$$ 여기서 \(m.. 2023. 1. 24. [Kotlin] 백준 23309 : 철도 공사 문제 링크 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$) 두 번째 줄에는 공사 www.acmicpc.net 문제 해설 시간 초과 때문에 골머리를 썩힌 문제다. 분류상으로는 연결 리스트 문제인데 그렇다고 연결 리스트를 사용할 수는 없다. 연결 리스트의 경우 탐색하는데 걸리는 시간 복잡도가 \(O(n)\)인데, \(500,000 \times 1,500,000=7500\)억이 되어 너무 많은 시간이 걸리기 때문이다. 따라서 훨씬 효율적인 탐색 방법이 필요하다. 결국 배열을 사용하기로 했다. 역 고유 번호를.. 2023. 1. 19. [Kotlin] 백준 1283 : 단축키 지정 문제 링크 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 문제 해설 문제의 로직 자체는 여러울 것이 없다. 단축키를 저장할 Set을 선언한 후 단축키를 지정하는 방법을 순서대로 진행하며 지정되는 단축키를 Set에 삽입하고, 지정된 단축키에 대괄호를 씌워서 출력하는 것을 반복하기만 하면 된다. 다만, 단축키는 대소문자를 구분하지 않으므로 Set에 단축키를 삽입할 때 대문자 또는 소문자로 통일해야 한다. 세부적인 로직은 다음과 같다. 각 줄로 입력받은 옵션의 이름을 공백을 구분자로 분리하여 각 단.. 2023. 1. 18. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음
