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

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

 

 

1. 코드카타 문제풀이

A. 알고리즘 수업 - 피보나치 수 1(백준, B1, 24416번)

문제 내용

 

문제 풀이 방법

• 재귀 호출과 반복문으로 n번째 피보나치 수열을 구할 때, 각 구문이 호출되는 횟수를 출력.
• 사진의 코드의 주석이 쳐져 있는 부분이 몇 번 호출되는지 확인한다.

 

해결 코드(스포 주의)

import java.util.Scanner

private var resursive = 0   // 재귀 함수 카운트
private var loop = 0        // 반복문 카운트
fun main() = with(Scanner(System.`in`)) {
    val number = nextInt()

    fibonacci(number)   // 재귀 호출

    // 반복문
    val fibonacciList = mutableListOf(1, 1)
    for (i in 3 .. number) {
        fibonacciList.add(fibonacciList[i-2] + fibonacciList[i-3])
        loop++
    }

    println("$resursive $loop")
}

private fun fibonacci(num: Int): Int {
    if (num == 2 || num == 1) {
        resursive++
        return 1
    } else return fibonacci(num - 1) + fibonacci(num - 2)
}

 

풀이 과정

• 재귀 함수 호출 카운트(resursive)와 반복문 호출 카운트(loop)를 전역 변수로 생성한다.
• 각각 재귀 함수, 반복문을 구현해 문제 사진에 해당되는 부분에 각각의 전역 변수를 카운팅 한다.

 

문제 해결 과정

• 사진의 주석이 달린 부분에 정확하게 카운팅 로직을 넣어야 한다(특히 재귀 호출 부분). 그렇지 않으면 fibonacci()가 호출된 횟수를 구하게 된다(num이 2 또는 1일 때 카운팅을 해야 구현이 정확하다).
• 다이나믹 프로그래밍 공부 후 풀어보는 연습용 문제이다. 실제로 활용하기까지는 오랜 시간이 걸릴 듯하다.

 

B. 다리 놓기(백준, S5, 1010번)

문제 내용

 

문제 풀이 방법

• 강을 기준으로 서쪽 사이트와 동쪽 사이트가 있을 때, 서쪽 사이트와 동쪽 사이트를 서로 연결하는 경우의 수 출력.
• 다리가 서로 겹쳐질 수 없다.
• 다이나믹 프로그래밍과 단순 반복문으로 해결할 수 있다(해결 코드 참고).

 

해결 코드(스포 주의)

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 input = readLine().split(" ").map { it.toInt() }
        val westSite = input.first()
        val eastSite = input.last()

        // DP를 사용하지 않은 단순 반복문
//        var numerator = 1.toBigInteger()       // 조합의 분자(팩토리얼)
//        var denominator = 1.toBigInteger()     // 조합의 분모(팩토리얼)
//        for (j in eastSite-westSite+1 .. eastSite) {
//            numerator *= j.toBigInteger()
//        }
//
//        for (j in 1 .. westSite) {
//            denominator *= j.toBigInteger()
//        }
//
//        println(numerator / denominator)

        // DP를 이용한 풀이.
        val combination = MutableList(westSite) {MutableList(eastSite) { 0 } }
        for (j in 0 until westSite) {
            for (k in 0 until eastSite) {
                if (j == k) combination[j][k] = 1
                else if (j == 0) combination[j][k] = k+1
                else if (k != 0) combination[j][k] = combination[j - 1][k - 1] + combination[j][k-1]
            }
        }

        println(combination[westSite-1][eastSite-1])
    }
}

 

풀이 과정

• 나는 총 2가지의 문제 풀이법이 있다(반복분, 다이나믹 프로그래밍)
• 단순 반복문으로 해결하는 방법은 westSite와 eastSite 간의 조합을 구하면 해결할 수 있다(편의상 westSite를 w, eastSite를 e로 부르겠다).
  조합의 공식은 e! / r! * (e-r)!이다. 이를 이용해 반복문을 돌려서 팩토리얼 값(분자, 분모)을 구해준 다음에 둘이 나눈다.

 

문제 해결 과정

• 풀이 과정에서 단순 반복문에 대한 풀이를 했으므로 이번에는 다이나믹 프로그래밍을 활용한 풀이를 설명하겠다.
• 이 문제를 다이나믹 프로그래밍으로 해결할 수 있는 이유가 DP는 기존의 데이터를 재활용해 새로운 데이터를 만드는 것이 기본적인 원칙인데 이를 활용할 수 있는 방법이 있다.

가로: east, 세로: west

• 위의 사진을 보면 가로와 세로의 값이 변함에 따라 값이 변하고 있다. 표의 가로, 세로의 데이터에 해당하는 수가 경우의 수이다(가로: 2, 세로: 2일 때 경우의 수 = 1)

위의 설명을 적용 빈칸은 0

• 가로와 세로가 같으면 1이고 세로가 1일 때는 가로의 값을 그대로 가져가는 것을 보아 특정한 규칙을 찾을 수 있다.
  1,1의 데이터인 1과 1,2의 데이터인 0(빈칸)의 합이 2,2의 데이터인 1과 같다(1+0=1)
  이 사실을 이용해 3, 2의 데이터를 유추할 수 있다(2,1 데이터: 2, 2,2 데이터: 1 => 2+1=3)
  위의 방법을 반복하면 1 위의 데이터를 모두 채울 수 있다.
  작은 값을 재활용해 큰 값을 구하는 다이나믹 프로그래밍의 규칙을 완전히 따르고 있다.
  이를 이용해 코드를 구현해 보면,
• 입력받은 westSite, eastSite의 크기를 가지는 2중 리스트를 생성한다.(combination)
  0부터 westSite까지를 외부 반복으로, 0부터 eastSite까지를 내부 반복으로 잡고
  초기 데이터를 설정해 준다(j와 k가 같으면 eastSite와 westSite가 같은 경우이므로 무조건 1, j가 0인 경우는 eastSite의 index값을 따라가므로 k+1로 설정).
  초기 데이터를 설정하고 나면 위 사진과 같은 상태가 될 것이다.
  이제 k가 0이 아닌 경우에만 combination[j][k]를 넣어준다.
• 출력 결과

정상적으로 사진처럼 출력되었다

• 위의 데이터를 바탕으로 가장 마지막 열, 마지막 행의 데이터가 원하는 값이기 때문에 그것을 출력한다.

 

 

2. 개인 과제

A. 콘솔 키오스크 만들기(Lv.2)

과제 내용 간단 정리

• 현재 Lv.2까지 구현했다.
• Lv.1 요구사항: 조건문과 반복문을 이용해 키오스크 메인 메뉴 화면과 상세 메뉴 화면을 출력하기.
• Lv.2 요구사항: 상세 메뉴에 전시할 메뉴들의 클래스를 만들고 그 안에 displayInfo() 함수를 만들어 메뉴 정보 출력하기.

 

Lv.2 구현 과정

• Lv.2까지 구현하기도 했고, Lv.2가 Lv.1의 진보된 단계이기 때문에 Lv.2 구현 과정만 설명하겠다.
• 먼저 메뉴 정보를 출력할 클래스를 만들어 주었다.
  클래스에는 name, price 프로퍼티를 만들고, displayInfo() 함수로 name, price를 이용해 메뉴 정보를 출력한다.

Burger1.kt

class Burger1() {
    var name = "햄버거 1"
    var price = "3,500"

    fun displayInfo() {
        println("1. $name                  | W$price | 그냥 햄버거 1")
    }
}

• 생성한 클래스들을 이용해 기존의 메뉴 출력을 삭제하고, 클래스명.displayInfo()로 교체한다.

kiosk.kt의 일부 코드

"햄버거" -> {
    val burger1 = Burger1()
    val burger2 = Burger2()
    val burger3 = Burger3()

    println("[ 햄버거 ]")
    burger1.displayInfo()
    burger2.displayInfo()
    burger3.displayInfo()
}

 

 

 

3. 개인 공부

A. 알고리즘 개념 - 다이나믹 프로그래밍

공부 내용 간단 정리

• 따로 포스팅을 올렸다.
• 포스팅 링크: https://rkdrkd-history.tistory.com/118

[알고리즘] 다이나믹 프로그래밍(Dynamic Programming)

 

 

---

 

오늘 공부 내용 정리 및 회고

• 백준 B1문제는 다이나믹 프로그래밍을 공부하면서 풀어본 문제이고, S5문제는 다이나믹 프로그래밍을 공부하고 나서 풀어본 문제이다. 처음에는 단순 반복으로 풀었다가 질문 게시판에서 힌트를 얻고 다시 DP로 풀었다.
• DP 문제들은 변수를 잘 파악하고 관계식을 잘 만들어야 쉽게 해결할 수 있는 문제들인 것 같다. 많이 풀고 머리를 박다 보면 나중에 잘 파악하는 능력이 생기지 않을까 기대 중이다.
• 현재 콘솔 키오스크를 Lv.2까지 구현했다. 아직까지는 어려움은 없는데, Lv.3부터 본격적인 기능 추가니까 사용되는 개념을 잘 공부해 둬야겠다.