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

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

 

 

1. 코드카타 문제풀이

A. 1로 만들기(백준, S3, 1463번)

문제 내용

 

문제 풀이 방법

• 숫자가 주어질 때, 3가지의 연산을 수행해 1로 만들 수 있는 최솟값을 출력.

 

해결 코드(스포 주의)

import java.util.Scanner
import kotlin.math.min

fun main() = with(Scanner(System.`in`)) {
    val num = nextInt()
    val cntList = MutableList(num+1) { 0 }

    // 1을 제외한 num까지 반복.
    for (i in 2 .. num) {
        // 일단 이전의 값에서 1을 더하면 해당 값을 만들 수 있는 개수가 나옴.
        cntList[i] = cntList[i-1] + 1
        // 2, 3으로 나누어 떨어지면 i를 2 또는 3으로 나눈 index에 1을 더하면 만들 수 있는 개수가 나옴.
        // 위에 만든 개수와 2, 3을 나눠 만든 개수 중 더 작은 것을 고르기.
        if (i % 2 == 0) cntList[i] = min(cntList[i], cntList[i/2] + 1)
        if (i % 3 == 0) cntList[i] = min(cntList[i], cntList[i/3] + 1)
    }
    
    println(cntList[num])
}

 

풀이 과정

• 입력받은 num의 +1만큼의 크기를 가지는 mutableList를 생성한다.
• 2부터 num까지 반복한다.
  배열의 초기값은 0이 입력받을 일은 없고, 1은 무조건 0이기 때문에 2부터 시작한다.
• 반복을 돌면서 이전의 값에 1을 더하면 해당 값을 만들 수 있는 개수가 나온다.
  예를 들어, i가 6이면 이전의 값인 5를 만들 수 있는 경우의 수의 최솟값은 3인데, 여기에 1을 더함으로써 연산 횟수를 1 늘렸으므로 6을 만들 수 있는 연산의 횟수는 4가 된다.
• i가 2 또는 3으로 나누어 떨어지는 경우 바로 2, 3으로 나눈 index의 최솟값에 1을 더해서 연산 횟수를 구한다.
  예를 들어 i가 6이면 2와 3으로 둘 다 나누어 떨어지기 때문에 2가지의 경우를 모두 봐보면,
  2로 나누어 떨어지는 조건을 보면, 6 / 2 = 3번째 index 값은 1이다. 3에다 2를 곱하는 연산을 써서 6을 만들 수 있으므로 연산 횟수는 2가 된다.
  3으로 나누어 떨어지는 조건을 보면, 6 / 3 = 2번째 index의 값은 1이다. 2에다가 3을 곱하는 연산을 써서 6을 만들 수 있으므로 연산 횟수는 2가 된다.
• 그냥 1을 더한 연산의 연산 횟수와 2 또는 3으로 나누어 떨어질 때, 그 값들의 최솟값에 1을 더한 값 중 더 작은 값이 최솟값이 될 것이다.
• 반복 종료 후 List의 num번째 index를 구한다. List의 크기를 num+1로 정해놓아서 오류가 나지 않는다.

 

문제 해결 과정

• 다이나믹 프로그래밍으로 문제를 해결했다.
• DP의 점화식을 찾을 수 없어서 헤매고 있다가 결국은 문제를 푸는 방법을 찾아보았다(정답 코드도 같이 봤다(다른 언어긴 했지만.)).
• 풀이 방법을 알게 되니 제한시간이 0.15초인 것이 무색하게 쉽게 해결했다.
• 아직은 DP의 점화식을 생각하는 것이 많이 힘들다. DP문제를 많이 풀어보는 방법밖에 없는 것 같다.
  그때까지는 다른 사람들의 풀이를 참고하면서 해결해야 할 듯하다.

 

B. 킬로미터를 마일로(백준, S5, 6504번)

문제 내용

 

문제 풀이 방법

• km가 입력으로 주어졌을 때, 이 킬로미터를 피보나치 수열의 데이터들을 이용해 마일로 변환해 출력.
• 42km가 주어지면, 피보나치 수열은 [1, 2, 3, 5, 8, 13, 21, 34]까지 나타나고, 이 수열을 이용해 마일로 변환한다.
  34 + 8을 하면 42가 되기 때문에 피보나치 진법으로 변환하면 [0, 0, 0, 0, 1, 0, 0, 1] 이 된다.
  여기서 맨 앞의 데이터를 제외하고 보면 [0, 0, 0, 1, 0, 0, 1] 이 되는데 이를 다시 정수로 변환하면 21 + 5 = 26이므로
  정답은 26이 될 것이다.

 

해결 코드(스포 주의)

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()
    var fibonacciList: List<Int>

    for (i in 0 until case) {
        var num = readLine().toInt()
        var mile = 0

        fibonacciList = fibonacciDP(num)

        // 피보나치 진법으로 표시한 데이터.
        val fibonacciNotation = Array(fibonacciList.size) { 0 }
        for (j in fibonacciNotation.size-1 downTo 0) {
            if (num == 0) break
            if (j == fibonacciNotation.size-1) {
                fibonacciNotation[j] = 1
                num -= fibonacciList.last()
            } else {
                if (fibonacciList[j] <= num) {
                    fibonacciNotation[j] = 1
                    num -= fibonacciList[j]
                } else continue
            }
        }

        // 가장 끝의 데이터 제외하고 보기.
        for (j in 1 until fibonacciNotation.size)
            if (fibonacciNotation[j] == 1) mile += fibonacciList[j-1]

        println(mile)
    }
}

// DP를 이용한 피보나치 수열 구하기.
private fun fibonacciDP(num: Int): List<Int> {
    val fibonacci = mutableListOf(1, 2)
    var index = 2

    while (true) {
        val fibonacciNum = fibonacci[index-1] + fibonacci[index-2]
        if (fibonacciNum > num) break

        fibonacci.add(fibonacciNum)
        index++
    }

    return fibonacci
}

 

풀이 과정

• case만큼 반복하고, num을 입력받고 mile 변수를 초기화한다.
• fibonacciList를 만들어 fibonacciDP() 함수의 값을 넣는다.
  fibonacciDP()는 피보나치 수열을 DP 방식으로 계산한 함수이다.
• fibonacciNotation을 만들어 피보나치 진법으로 표시할 Array를 만들어 준다. 전부 0으로 초기화한다.
  fibonacciNotation의 크기의 -1부터 0까지 뒤로 반복해 준다.
  num까지의 피보나치 수열을 생성했기 때문에 fibonacciList의 마지막 데이터는 반드시 들어간다(첫 반복일 때).
  반복하다가 fibonacciList[j]가 num보다 작거나 같은 조건을 만족하면 fibonacciNotation의 j번째 index를  1로 변경한다. 또한 1로 데이터를 변경할 때마다 num을 fibonacciList[j]만큼 빼준다.
  반복을 다 돌기 전에 num이 0이 되면 더 돌 필요가 없기 때문에 break.
• 데이터를 변경한 fibonacciNotation을 1부터 돈다(첫 번째 index의 데이터를 제외해야 하기 때문).
  fibonacciNotation[j]가 1이면 fibonacciList[j-1]의 값을 mile에 더해준다(첫 번째 index를 제외했기 때문에 fibonacciList 데이터도 1씩 밀려나야 한다).
• mile을 출력한다.

 

문제 해결 과정

• 피보나치 수열을 빠르게 구하지 못하면 시간 초과가 날 듯한 문제이다.
• 나의 경우는 DP를 이용해 빠르게 구해주었다.
• 위의 코드는 입력받은 num의 크기가 이전 num보다 크면 이전 num 때 구했던 피보나치 수열을 재활용해 더 빠르게 num까지의 피보나치를 구할 수 있을 듯하다.

 

2. 개인 공부

A. 개인 과제(Lv.3 진행 중)

공부 내용 간단 정리

• Lv.3는 클래스 간 상속 관계를 가지도록 구현하는 것이다.
• Burger1(), Burger2() 클래스가 있을 때, 이들을 묶는 Burger()를 만들고, Burger(), Drink() 클래스를 묶는 Food()라는 최상위 클래스를 구현하는 것이다.
  Food -> Burger -> Burger1 순서
• Food()에는 어떤 기능을 넣어야 하고, Burger()에는 어떤 기능을 넣어야 할지 헷갈려 헤매고 있다.

 

 

---

 

오늘 공부 내용 정리 및 회고

• DP 문제를 계속 1문제 이상 풀어볼 생각이다.
• 개인과제 상속에 대해 내일 더 공부해 보고 Lv.3에 적용시켜 볼 생각이다.