Algorithm114 [Kotlin] 백준 23294 : 웹 브라우저 1 문제 링크 23294번: 웹 브라우저 1 첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 와 최대 캐시 용량 C 이 순서대로 주어진다.(1 ≤ N, Q ≤ 2,000, 1 ≤ C ≤ 200,000) 둘째 줄에는 N개의 정수 CAPi www.acmicpc.net 문제 해설 [Kotlin] 백준 23300 : 웹 브라우저 2와 유사한 문제지만 캐시 용량의 제한이 추가되어 있는 문제이다. 캐시 용량을 다루는 것을 제외하면 기본적인 풀이는 동일하다. 각 페이지의 캐시 공간은 배열에 저장하여 사용했다. 뒤로 가기 공간과 앞으로 가기 공간을 각각 덱으로 구현하고 B 또는 F를 수행할 때마다 저장된 페이지와 현재 페이지를 옮기면 된다. 이 두 경우에는 이미 캐시 공간에 저장된 .. 2023. 4. 19. [Kotlin] 백준 9519 : 졸려 문제 링크 9519번: 졸려 첫째 줄에 X(1 ≤ X ≤ 1,000,000,000) 가 주어지고, 둘째 줄에 X번 깜박인 후의 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 구간 [3,1000]에 포함된다. www.acmicpc.net 문제 해설 눈을 \(x\)번 깜박인 결과로부터 원래 단어를 찾아내야 한다. 처음에는 단순히 문제에서 주어진 연산을 \(x\)번 역수행해서 구해보려고 했는데 입력의 최대치가 10억인 것을 보고 시간 초과가 날게 뻔해서 다른 방법을 찾아보기로 했다. 예제로 주어진 테스트 케이스를 직접 돌려보면 일종의 규칙이 있다는 것을 볼 수 있다. 0은 최초 입력으로 주어진 단어이고, 각 회차는 이전 단어에서 문제에서 주어진 연산을 역수행한 결과이다. 첫번째 예제의 경우.. 2023. 4. 17. [Kotlin] 백준 2086 : 피보나치 수의 합 문제 링크 2086번: 피보나치 수의 합 제 1항과 제 2항을 1이라 하고, 제 3항부터는 앞의 두 항의 합을 취하는 수열을 피보나치(fibonacci) 수열이라고 한다. 예를 들어 제 3항은 2이며, 제 4항은 3이다. 피보나치 수열의 a번째 항부터 b번째 www.acmicpc.net 문제 해설 피보나치 수의 성질을 이용하면 쉽게 풀 수 있는 문제다. 기본적으로 \(n\)에 대한 피보나치 수의 점화식은 \(F_n=F_{n-1}+F_{n-2}\)가 되는데 여기서 \(n\)에 \(n+2\)을 대입하고 식을 조금 정리하면 \(F_n=F_{n+2}-F_{n+1}\)이 된다. 이렇게 되면 \(F_n\)까지의 모든 피보나치 수의 합은 다음과 같다고 볼 수 있다. $$\sum_{k=1}^n F_k=\sum_{k=1.. 2023. 4. 10. [Kotlin] 백준 1630 : 오민식 문제 링크 1630번: 오민식 첫째 줄에 자연수 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 1~N의 모든 자연수로 나누어 떨어지는 수를 구해야 한다. 다시 말해 N이하의 모든 자연수의 최소 공배수를 구해야 하는데, 이는 N 이하인 소수들의 거듭제곱으로만 이루어진 곱인 소인수분해의 형태로 나타낼 수 있다. 예를 들어, \(N=10\)일 때 오민식을 만족하는 가장 작은 수인 2520은 \(2520=2^3\times 3^2\times 5\times 7\)로 나타낼 수 있다. 우선 N 이하의 모든 소수는 에라토스테네스의 체를 이용하여 구한다. 그리고 각 소수에 대하여 N 이하인 가장 큰 거듭제곱을 구해서 곱하면서 각 연산마다 987654321로 나.. 2023. 4. 8. [Kotlin] 백준 11440 : 피보나치 수의 제곱의 합 문제 링크 11440번: 피보나치 수의 제곱의 합 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해설 입력의 최대치가 \(10^{18}\)이기 때문에 피보나치 수를 각각 구해서 제곱하여 더하는 방법으로 풀게 되면 어마어마한 시간이 걸리므로 다른 방법을 사용하여 풀어야 한다. 피보나치 수의 기본적인 점화식인 \(F_n=F_{n-1}+F_{n-2}\)를 살짝 변형하면 \(F_n=F_{n+1}-F_{n-1}\)이 되는데, 이 식을 사용하면 \(\sum_{k=1}^{n}{F_k}^2\)를 간단하게 만들 수 있다. \(\sum_{k=1}^{n}{F_k}^2\)에서 \({F_k}^2\)은 위의 식을 이용하여 \(F_k(F.. 2023. 4. 7. [Kotlin] 백준 2812 : 크게 만들기 문제 링크 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해설 N자리 수에서 K개의 숫자를 지워서 만든 가장 큰 수라는 것은 결국 앞자리 숫자가 뒷자리 숫자보다 커야한다는 것을 의미한다. 이를 처리하기 위해 스택을 사용할 수 있다. 입력으로 주어진 수를 각 자리수의 배열로 생각하여 진행한다. 앞에서부터 각 자리의 숫자를 스택에 삽입한다. 이 때, 스택에 숫자를 삽입하기 전에 이미 삽입된 숫자들을 순차적으로 확인하여 현재 삽입해야 할 숫자보다 작은 숫자를 모두 제거하고, 제거한 숫자의 개수를 기록한다. 제거한 숫자의 개수가 K개가 되었다면 남은 모든 숫자를 스택에 삽입한다. 모든 .. 2023. 4. 4. [Kotlin] 백준 16496 : 큰 수 만들기 문제 링크 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 문제 해설 기본적으로는 정렬을 활용한 문제지만 정렬 기준을 어떻게 할지가 관건인 문제라고 볼 수 있다. 수를 이어붙여서 더 큰수를 만들기 위해서는 수를 문자열로 다뤄야 한다. 정렬 기준자체는 굉장히 간단하다. s1과 s2가 있을 때, s1 + s2와 s2 + s1 중 더 큰것이 우선적으로 오도록 정렬하면 된다. 예를 들어 123과 45가 있을 때 12345보다 45123이 더 크기 때문에 [45, 123]으로 정렬할 수.. 2023. 4. 3. [Kotlin] 코틀린으로 정렬 관련 문제를 풀 때 사용하는 배열이나 리스트를 정렬하는 메소드의 종류 및 각 메소드의 차이 목차 개요 기본적으로 코틀린에서는 배열도 객체로 취급되어 sort()와 같은 메소드를 사용할 수 있다. 그런데 이들 메소드들은 종류에 따라 약간의 차이가 있고, 메소드를 호출한 객체의 타입과 메소드의 종류에 따라 성능도 차이난다. 백준 - 수 정렬하기 5 문제를 푸는데 그냥 단순한 정렬 문제라고 생각했다가 정렬 메소드의 종류에 따라 TLE가 나기도 했고 AC가 나오기도 했다. 이들 메소드들 사이에 무슨 차이가 있길래 무엇을 쓰느냐에 따라 결과가 다르게 나타나는지 궁금해서 내부 구조를 확인해봤는데 생각보다 많은 차이가 있었다. Kotlin 정렬 메소드의 종류 코틀린에서 배열이나 리스트를 정렬하는 메소드는 작동 방식과 결과 타입에 따른 3가지, 정렬 방법에 따른 3가지로 구분할 수 있다. 작동 방식과 결과 .. 2023. 3. 31. 이전 1 2 3 4 5 6 7 ··· 15 다음
