문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이 문제를 풀이하기 위해 이분 탐색(Binary Search) 알고리즘이 필요하다. 이분 탐색이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간값을 선택하고, 찾고자하는 값과 비교해서 중간값이 더 크다면 그 중간값이 새로운 최댓값이 되고, 더 작다면 최솟값이 된다. 그리고 다시 새로운 중간값을 찾고, 찾고자하는 값과 비교해나가는 것이다. 풀이한 코드에서는 binarySe..

문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 문제를 보고 일단 타일의 모습을 그려보기로 했다. n의 타일은 n - 1 의 타일에 세로 타일이 하나씩 추가된 모습과, n - 2의 타일에 가로 타일 두개씩 추가된 모습이다, 이를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2] 이다. 이 점화식을 이용해 문제를 해결하면 된다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val mo..

문제 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 먼저 코틀린의 HashSet을 이용하여 중복된 단어의 입력을 방지한다. 이 set을 정렬하기 위해 MutableList로 형변환 시켜준다. 이 리스트를 Comparator를 이용하여 정렬시켜주기 위해 sortWith() 함수를 사용한다. 두 단어의 길이가 같은 경우에는 알파벳 순서에 따라 정렬하고, 아닌 경우에는 길이에 따라 정렬해준다. 이 후, 정렬된 리스트를 출력하면 된다. 코드 fun main() { val br = System.`in..

문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 문제에서 주어진 코드대로 피보나치 수열을 재귀함수로 구현하고, 0과 1을 세는 방법으로 문제를 풀면 시간초과가 발생한다. 대신 DP를 이용해 피보나치 수열을 풀면 된다. 피보나치 수란 한 단계 전의 숫자와 두 단계 전의 숫자를 합한 수의 수열이다. 예를 들어 1, 1, 2, 3, 5, 8 ... 등이 피보나치 수이다. 피보나치 수를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2]이다. 이 점화식에서 dp[n - 1] = dp[n - 2] + dp[n - 3] 이고 dp[n - 2] = dp[n - 3] + dp[n - 4]..

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 어떤 수가 소수인지 알기 위해서 아래 코드로 판별할 수 있지만, 범위 내에 모든 수를 아래와 같은 방법으로 판별한다면 비효율적이고 이 문제에서 시간초과가 발생한다. for(i in start .. end) { var cnt = 0 for(j in 1..i) { if(i%j==0) { cnt++ } } if(cnt==2) { println(i) } } 대신 에라토스테네스의 체를 이용하여 해결할 수 있다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가는 방식이다. 2의 배..