Kotlin162 [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] 코틀린으로 알고리즘 문제를 풀 때 출력 방식별 속도에 대하여 [Kotlin] 백준 23309 : 철도 공사 문제 링크 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500 colabear754.tistory.com 위 링크의 문제풀이에서 BufferedWriter를 사용한 풀이는 시간 초과로 통과에 실패했는데 StringBuilder로 문자열을 하나로 만들어 출력한 풀이는 통과에 성공했다고 얘기한 적이 있다. 기본적으로 코틀린은 자바의 함수와 클래스를 사용하여 출력하기 때문에 백준님이 측정한 출력 방식별 속도 측정을 기반으로 문제를 풀고 있었다. 그래서 BufferedWriter.. 2023. 1. 20. [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. [Spring Boot] 스프링부트 3.0.0 이상 버전을 사용하려고 할 때 빌드 과정부터 에러가 나는 경우(Kotlin/Java 동일) 작성일 기준으로 Spring Initializr를 사용하여 스프링 부트 프로젝트를 생성할 때 3.0.0 이상인 버전과 2.7.X 버전 중에서 선택할 수 있다. 아직은 2.6.X나 2.7.X 버전을 사용하는 경우가 많으나, 언젠가는 3.0.0 이상인 버전을 사용하게 되는 경우가 더 많아질 수가 있다. 하지만 Java 버전을 국내에서 주로 사용하는 11이나 1.8로 설정하고 3.0.0 이상인 버전의 스프링 부트 프로젝트를 생성하면 최초 빌드 과정에서부터 에러가 발생하게 된다. 에러 로그의 핵심적인 부분만 추려내면 다음과 같다. Incompatible because this component declares an API of a component compatible with Java 17 and the con.. 2023. 1. 17. 이전 1 ··· 7 8 9 10 11 12 13 ··· 21 다음
