전체 글222 [Kotlin] 백준 9935 : 문자열 폭발 문제 링크 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해설 스택을 사용하여 해결할 수 있다. 문제 해결 과정은 다음과 같다. 먼저 문자열을 앞에서부터 순회하면서 스택에 문자를 삽입한다. 스택에 문자를 삽입하는 도중에 폭발 문자열의 마지막 글자가 나타나면 폭발 문자열의 길이만큼 스택에서 문자를 제거하여 폭발 문자열인지 체크할 문자열을 만든다. 이 때 스택에서 현재 스택의 크기가 폭발 문자열의 길이보다 작을 수 있기 때문에 EmptyStackException을 방지하기 위한 체크 로직을 .. 2022. 12. 19. 투 포인터(Two Pointer) with Kotlin 투 포인터(Two Pointer) 투 포인터(Two Pointer) 알고리즘은 배열이나 리스트에서 두 개의 점을 이동시키면서 원하는 결과를 얻어내는 알고리즘이다. 예를 들어 부분합을 구하는 문제에서 배열과 부분합을 구할 특정 인덱스가 주어지는 것이 아니라 특정 값이 주어지고 부분합이 주어진 값과 일치하는 구간의 수 또는 구간의 최대/최소 길이를 구해야 하는 경우를 생각해볼 수 있다. 이 경우에 누적합이 계산된 배열이 있어도 단순히 이중 반복문으로 답을 찾게 되면 \(O(n^{2})\)의 시간 복잡도를 갖게 되어 배열의 크기가 10만 정도만 되더라도 100억회의 연산을 해야하기 때문에 굉장히 비효율적이다. 이럴 때 투 포인터를 사용하는 것이 대안이 될 수 있다. 투 포인터는 각각 구간의 시작과 끝을 가리키.. 2022. 12. 18. [Kotlin] 백준 1806 : 부분합 문제 링크 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 해설 부분합과 투 포인터가 결합된 문제다. 부분합에 대한 내용은 아래 포스트를 참고하면 좋다. 링크 : 누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin 누적합을 저장할 크기가 \(n+1\)인 배열을 선언하고 1번째 인덱스부터 누적합을 저장해나간다. 이후 투 포인터를 사용해서 배열 위를 이동하기 시작한다. start부터 end까지의 합이 \(S\) 이상이라면 기존 구간 길이의 최소값과 현재 구간 길이.. 2022. 12. 17. 누적합(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 기본 문법 9 : Kotlin의 다양한 클래스(Data Class, Enum Class, Sealed Class) 목차 개요 Kotlin에는 기본적인 클래스, 추상 클래스, 인터페이스 외에도 Data Class, Enum Class, Sealed Class가 존재한다. 물론 Enum Class는 Java에도 존재하는 개념이지만 Data Class와 Sealed Class는 Java에는 존재하지 않는 Kotlin만의 특별한 클래스이다. 이번 포스트에서는 이러한 Kotlin의 특별한 클래스에 대해 정리한다. Data Class Data Class는 주로 DB를 다루는 앱을 개발할 때 각 DTO(Data Transfer Object)나 VO(Value Object)를 작성할 때 사용할 수 있는 특수한 클래스이다. Java에서 DTO나 VO를 작성할 때 getter, setter를 비롯하여 equals(), hashCode.. 2022. 12. 16. [Kotlin] 백준 25916 : 싫은데요 문제 링크 25916번: 싫은데요 $6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다 www.acmicpc.net 문제 해설 부분합의 최대치 중 M 이하인 값을 구하는 문제다. 문제에 햄스터가 막을 구멍은 반드시 연속되어야 한다는 제한이 있기 때문에 투 포인터를 이용하여 풀 수 있다. 투 포인터는 이름 그대로 두 개의 점이 배열 위를 이동하면서 주어진 조건에 맞는 답을 찾아가는 방법이다. 본 문제에서는 독의 첫 번째 구멍부터 마지막 구멍까지 햄스터가 계속 몸을 늘리거나 줄여가면서 답을 찾을 수 있다. 주어진 예제를 그림으로 표현해보자. 그림을 보면 현재 햄스터가 막은 구멍 크기의 합계가 조건보다 작은 경우엔 햄스터가 오른쪽으로 늘어나고, 햄스터가 막은 .. 2022. 12. 16. [Kotlin] 백준 11387 : 님 무기가 좀 나쁘시네여 문제 링크 11387번: 님 무기가 좀 나쁘시네여 각 줄마다 "공격력", "힘", "치명타 확률", "치명타 피해비율", "공격속도 증가"의 수치를 나타내는 다섯 개의 정수가 공백을 사이에 두고 순서대로 주어진다. 첫 번째 줄은 무기를 장착한 크리의 www.acmicpc.net 문제 해설 문제 자체는 단순한 구현 문제지만 주의할 점이 있다. 전투력을 계산할 때 실수 계산을 많이 하게 되는데 컴퓨터는 내부적으로 모든 수를 2진법으로 저장하기 때문에 소수점 이하 부분은 정확하게 저장할 수 없고 근사치를 저장하게 된다. 이 과정에서 여러번의 연산을 하다보니 오차가 발생하여 식은 맞지만 답은 틀리는 경우가 발생할 수 있다. 따라서 BigDecimal을 사용하여 오차 없이 계산해야 한다. 이점만 주의하면 크리와 .. 2022. 12. 15. Kotlin 기본 문법 8 : 정적 변수와 정적 메소드(feat. companion object) 목차 개요 정적 변수와 정적 메소드는 클래스에 고정된 채로 프로그램이 실행될 때 클래스와 함께 메모리에 적재되어 객체를 생성하지 않고 호출할 수 있는 변수와 메소드를 의미한다. 이러한 정적 변수와 정적 메소드는 해당 클래스의 모든 객체가 공유하여 어디서든 참조가 가능하다. 이 포스트에서는 Kotlin에서 정적 변수와 정적 메소드를 선언하고 다루는 방법에 대해 정리한다. Kotlin에는 static 키워드가 없다 Java에서는 클래스 내부의 변수나 메소드 앞에 static을 붙이기만 하면 정적 변수나 정적 메소드로 선언할 수 있다. 하지만 Kotlin에서는 static이 존재하지 않고 다른 두 가지 방법으로 정적 변수와 정적 메소드를 작성할 수 있다. companion object Kotlin에서 정적 변.. 2022. 12. 14. 이전 1 ··· 18 19 20 21 22 23 24 ··· 28 다음
