Algorithm/관련내용5 [Kotlin] 코틀린으로 정렬 관련 문제를 풀 때 사용하는 배열이나 리스트를 정렬하는 메소드의 종류 및 각 메소드의 차이 목차 개요 기본적으로 코틀린에서는 배열도 객체로 취급되어 sort()와 같은 메소드를 사용할 수 있다. 그런데 이들 메소드들은 종류에 따라 약간의 차이가 있고, 메소드를 호출한 객체의 타입과 메소드의 종류에 따라 성능도 차이난다. 백준 - 수 정렬하기 5 문제를 푸는데 그냥 단순한 정렬 문제라고 생각했다가 정렬 메소드의 종류에 따라 TLE가 나기도 했고 AC가 나오기도 했다. 이들 메소드들 사이에 무슨 차이가 있길래 무엇을 쓰느냐에 따라 결과가 다르게 나타나는지 궁금해서 내부 구조를 확인해봤는데 생각보다 많은 차이가 있었다. Kotlin 정렬 메소드의 종류 코틀린에서 배열이나 리스트를 정렬하는 메소드는 작동 방식과 결과 타입에 따른 3가지, 정렬 방법에 따른 3가지로 구분할 수 있다. 작동 방식과 결과 .. 2023. 3. 31. [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. 투 포인터(Two Pointer) with Kotlin 투 포인터(Two Pointer) 투 포인터(Two Pointer) 알고리즘은 배열이나 리스트에서 두 개의 점을 이동시키면서 원하는 결과를 얻어내는 알고리즘이다. 예를 들어 부분합을 구하는 문제에서 배열과 부분합을 구할 특정 인덱스가 주어지는 것이 아니라 특정 값이 주어지고 부분합이 주어진 값과 일치하는 구간의 수 또는 구간의 최대/최소 길이를 구해야 하는 경우를 생각해볼 수 있다. 이 경우에 누적합이 계산된 배열이 있어도 단순히 이중 반복문으로 답을 찾게 되면 \(O(n^{2})\)의 시간 복잡도를 갖게 되어 배열의 크기가 10만 정도만 되더라도 100억회의 연산을 해야하기 때문에 굉장히 비효율적이다. 이럴 때 투 포인터를 사용하는 것이 대안이 될 수 있다. 투 포인터는 각각 구간의 시작과 끝을 가리키.. 2022. 12. 18. 누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin 누적합(Prefix Sum) 일반적으로 배열의 \(n\)번째 인덱스까지의 합을 구할 땐 아래와 같이 반복문을 사용하여 계산하게 된다. fun sumOfArray(arr: IntArray, n: Int): Int { var sum = 0 for (i in 0..n) { sum += arr[i] } return sum } 이 경우는 합을 한 번만 구할 때는 문제없이 사용할 수 있으나, \(N=[n_{1}, n_{2}, n_{3}, \cdots, n_m]\)와 같은 \(m\) 개의 경우에 대해 각 \(n\)번째 인덱스까지의 합을 구하는 경우엔 \(n\)만큼의 연산을 \(m\) 번 반복하게 된다. 즉, 총 시간 복잡도는 \(O(nm)\)이 된다. 누적합은 배열의 요소가 변하지 않는다는 점을 이용한다. 원본 배열.. 2022. 12. 17. [Kotlin/Java] 소수 찾기와 에라토스테네스의 체 소수를 판별하는 기본적인 방법 소수(prime number, 素數)는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수를 의미한다. 예를 들면 2, 3, 5, 7 ... 등이 있다. 어떤 수 \(x\)가 주어졌을 때 \(x\)가 소수인지 판별하는 가장 간단한 방법은 2부터 \(x-1\)까지 모든 수로 \(x\)를 나누었을 때 나누어 떨어지는 수가 있는지 확인하는 것이다. // Kotlin fun isPrime(x: Int): Boolean { for (i in 2 until x) {// 2부터 x-1까지 반복 if (x % i == 0) return false// x가 한 번이라도 나누어 떨어지면 소수가 아님 } return true// 모두 반복해도 나누어 떨어지지 않으면 소수 } // Java .. 2022. 11. 29. 이전 1 다음
