[Kotlin, 내일배움캠프] 공부일지(2024-06-27)

오늘 공부한 내용 정리(2024년 6월 27일)

 

 

코드카타 문제풀이

염색체(Silver 3, 9342번, 마라톤)

문제 내용

 

문제 풀이 방법

입력받은 문자열이 사진에 정의된 규칙을 만족하면 Infected! 를, 그렇지 않으면 Good를 출력.

 

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    for (i in 0 until case) {
        val string = readLine()
        val regex = Regex("[ABCDEF]?A+F+C+[ABCDEF]?$")

        if (regex.matches(string)) println("Infected!")
        else println("Good")
    }
}

 

풀이 과정

case만큼 반복한다.

문자열(string)을 입력받는다.

문자열이 정규 표현식을 만족하는지 체크해서 만족하면 Infected! 를, 그렇지 않다면 Good를 출력한다.

문제에 사용한 정규 표현식.

[ABCDEF]?: A부터 F가 0개 또는 1개 존재한다.
A+: A가 1개 이상 존재한다.
$: 문자열의 종료.

 

 

문제 해결 과정

정규 표현식을 사용해 쉽게 해결할 수 있는 문제이다.

어떤 표현식을 언제 써야 하는지 알 필요가 있다.

 

 

가장 긴 증가하는 부분 수열(Gold 2, 12015번)

문제 내용

 

문제 풀이 방법

가장 긴 증가하는 수열의 길이를 구하는 방법은 다이나믹 프로그래밍을 이용하거나, 이분 탐색을 이용할 수 있는데,

다이나믹 프로그래밍은 이 문제에서는 쓸 수가 없다(시간초과)

그래서 값을 하나하나 입력받으면서, 리스트에 들어있는 마지막 값보다 크다면 리스트에 집어넣고, 그렇지 않다면 이분 탐색을 이용해서 입력값보다 큰 값들 중 제일 작은 값을 찾아서 그 값을 교체하는 방식으로 풀어야 한다.

 

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

private var sequence = mutableListOf<Int>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    val input = StringTokenizer(readLine())

    sequence.add(input.nextToken().toInt())
    for (i in 1 until size) {
        val number = input.nextToken().toInt()
        if (number > sequence.last()) {
            sequence.add(number)
        } else {
            binarySearch(0, sequence.size -1, number)
        }
    }

    println(sequence.size)
}

private fun binarySearch(start: Int, end: Int, number: Int) {
    val mid = (start + end) / 2
    if (start > end) {
        sequence[start] = number
        return
    }

    // mid가 number보다 크다면?
    // mid 이후의 값들은 정답이 아님.
    if (sequence[mid] > number) {
        binarySearch(start, mid - 1, number)
    }
    // mid가 number보다 작거나 같으면?
    // mid포함 이전의 값들은 정답이 아님.
    else if (sequence[mid] < number) {
        binarySearch(mid+1, end, number)
    }
    else {
        sequence[mid] = number
        return
    }
}

 

풀이 과정

입력값의 개수(size)만큼 반복한다.

input의 nextToken() 값(number)을 하나하나 불러와서 현재 리스트(sequence)의 마지막 값과 비교한다.

sequence의 마지막 값보다 크다면 number를 리스트에 넣어준다. 이런 식으로 리스트에 넣어주면 리스트의 데이터는 자동으로 정렬된 데이터가 쌓이게 된다.

number가 list의 마지막 값보다 작다면 그때 이분 탐색을 써야 한다.

이미 리스트는 정렬되어 있으므로 문제없이 사용이 가능하다.

binarySearch()에 start(시작값), end(끝값), number(변경할 데이터)를 받아서 함수를 수행한다.

 

binarySearch에는 평범한 이분 탐색과 똑같다.

start와 end를 이용해 mid를 구해주고, sequence의 mid번째 값이 크냐 작냐에 따라 start, end값을 변경해 가면서 재귀 호출을 수행하면 된다.

재귀를 돌리다 보면 start가 end보다 커지는 때가 오는데, 그때 sequence의 start번째 index가 number보다 큰 값들 중 가장 작은 값이 될 것이다. 그 부분을 교체한다.

 

위 과정을 반복해 주면 가장 긴 증가하는 부분 수열의 길이를 구할 수 있다.

 

 

문제 해결 과정

가장 긴 증가하는 부분 수열 알고리즘에 대한 아이디어가 없으면 어려울 수 있는 문제이다.

처음에는 몰라서 알고리즘을 살짝 겉핥기식 공부를 해서 적용을 해봤지만 아직은 이분 탐색 쪽이 완전 숙련이 되지 않아서인가?

이분 탐색 쪽의 index에서 계속 문제가 발생했다.

이 문제를 풀면서 이분 탐색을 더 잘 활용할 수 있었다.

 

 

개인 공부

Z(Silver 1, 1074번)

문제 내용

 

 

문제 풀이 방법

2 * 2의 리스트를 Z순서로 하나하나 방문할 때, r행 c열을 몇 번째로 방문하는지 출력.

2^N * 2^N의 리스트를 중앙을 기준으로 4개로 쪼개가면서 r과 c가 어떤 사분면에 들어가는지 확인해야 한다.

배열의 크기를 줄여가면서 사분면 확인 후 어떤 사분면인지 체크해서 그 사분면의 0, 0의 데이터를 결과에 더해 주어야 한다.

쭉 반복하다가 배열의 크기가 2 * 2가 되면 그 사분면에 몇 번째 데이터인지 확인에 값을 더해주면 결과를 얻을 수 있다.

 

 

해결 코드(스포 주의)

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

private var visitNumber = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (size, x, y) = readLine().split(" ").map { it.toInt() }
    val mapSize = 2.0.pow(size).toInt()

    comparison(x, y, mapSize / 2)
    println(visitNumber)
}

private fun comparison(x: Int, y: Int, mapSize: Int) {
    if (mapSize == 1) {
        // 남은 x, y만큼 더하기
        // 사분면 순서는 z임.
        // 0, 0 => 1사분면
        // 0, 1 => 2사분면
        // 1, 0 => 3사분면
        // 1, 1 => 4사분면
        visitNumber += if (x == 0) {
            if (y == 0) 0 else 1
        } else {
            if (y == 0) 2 else 3
        }

        return
    }

    if (x < mapSize && y < mapSize) {
        comparison(x, y, mapSize / 2)
    } else if (x < mapSize && y >= mapSize) {
        visitNumber += (mapSize * 2).toDouble().pow(2).toInt() / 4
        comparison(x, y - mapSize, mapSize / 2)
    } else if (x >= mapSize && y < mapSize) {
        visitNumber += (mapSize * 2).toDouble().pow(2).toInt() / 4 * 2
        comparison(x - mapSize, y, mapSize / 2)
    } else {
        visitNumber += (mapSize * 2).toDouble().pow(2).toInt() / 4 * 3
        comparison(x - mapSize, y - mapSize, mapSize / 2)
    }
}

 

풀이 과정

배열의 길이(size) x축, y축을 입력받는다.

실질적인 배열의 크기는 2^size로 설정한다(mapSize)

그다음 comparison을 호출한다. x, y와 mapSize를 2로 나눈 값을 파라미터로 넣는다.

 

comparison 함수에서는 x와 y가 mapSize(현재 배열의 중앙) 보다 크냐 작냐에 따라 들어가 있는 사분면을 결정하고,

방문 번호(visitNumber)를 사분면에 맞게 변환해서 더해주고,

그 사분면에 값이 해당되도록 x, y 값을 변경 후 mapSize / 2를 다시 해준다.

이를 재귀 호출로 반복하다 보면 mapSize가 1이 되는데, 이때 x, y 값에 따라 마지막으로 들어갈 사분면을 판단하고 0, 1, 2, 3 중 값을 visitNumber에 더해 주면 최종 답안을 구할 수 있다.

 

 

문제 해결 과정

재귀를 이용하는 문제.

재귀 없이 무지성으로 처음부터 탐색을 하게 되면 시간 초과가 난다.

사분면으로 나눈 후, 값을 변경해 가면서 재귀 호출을 할 줄 알아야 한다.

재귀에서 사분면에 대한 조건을 찾고, 다시 함수를 호출할 때, x, y값을 상황에 맞게 잘 변경해주지 않으면 값이 달라지므로 주의해야 한다.

 

---

 

 

오늘 공부 내용 정리 및 회고

하루종일 알고리즘 문제 풀이만 했다.

오늘 푼 알고리즘 문제들이 거의 다 재귀를 사용한 문제이다. 재귀 쓰는 솜씨가 좋아진 것 같다.

이분 탐색에 대한 깨달음도 얻어가는 중이다. 조금 더 풀다 보면 깨달을 수 있을 것 같다.

 

내일은 기하 알고리즘을 맛보기로 공부해 볼까?

내일부터 수준별 학습반의 과제를 시작해야겠다.