240501 프로그래밍 심화 - 특강 많이 듣고 숫자 야구 발전시키기

노재원·2024년 5월 1일

TIL kotlin 내일배움캠프

내일배움캠프

목록 보기

30/90

튜터님의 특강 듣기

오늘 가장 많이 한 일을 꼽으라면 특강을 듣는 거였다. 인터넷 강의로 주어지는 방식이 아니라 대면으로 줌이나 잽을 통해서 실시간으로 들은 시간만 3시간이었다.

피곤하기도 피곤했지만 아무래도 실시간의 장점이 굉장히 돋보이고 다른 분들의 질문으로 이해도를 끌어올릴 수도 있어서

클래스 미니 특강

오전에는 같은 팀분들과 튜터님께 클래스 기초 강의를 들으러 갔다. 튜터님이 클래스에 관련해서 아주 기초적인 강의를 알려주신다고 피드백 중에 얘기가 나와서 다들 클래스 작성에 어려움을 겪으셔서 다 같이 들으러 갔다.

나는 안들어도 되니깐 안들을까 하다가 같이 들으면 코드리뷰 할 때 팀원분들에게 설명하기 정말 수월해지고 설명에 쓰이는 키워드를 통일하고 내가 새로 배울 수도 있으니 같이 들었다.

역시 튜터님이라 설명 방법이 차분하고 정돈되어 있어서 내가 2주차에 했던 설명보다 훨씬 듣기 좋았고 팀원 분들도 작성하기 어려웠던 Class 의 개념 이해에 훨씬 도움이 되신 것 같다. 나는 설명이 빨랐구나 느껴졌다.

알려주신 내용을 토대로 상태와 행위를 가진 클래스를 만들어서 튜터님과 함께 다시 리뷰하기로 했다.

Stack, Memory로 개념적 이론과 함께 듣는 계산기 과제 해설

계산기 과제를 같이 라이브 코딩으로 진행한 것에 이어서 원초적인 해설을 붙인 세션이 진행됐다. 간단한 계산기지만 개념적인 부분에서 쓰일 수 있는 키워드가 많아 기록하기로 했다.

분명 언제 어디선가 개념적으로 들어봤었을 내용들이지만 그 때는 이해 못했고 지금은 이해할 자신이 조금 생긴 것 같다.

객체지향의 진행 방식을 나는 스택과 힙 메모리를 키워드로 써서 설명할 정도의 지식은 없는데 오늘 개념적 해설로 천천히 진행하며 많이 참고하게 됐다.

인스턴스를 생성하면 힙 메모리 위에 올라가고 변수는 대입받을 때 힙 메모리의 주소를 대입받는다. 이후 인스턴스 주소가 저장된 변수를 쓸 때마다 해당 주소값을 찾아가서 인스턴스의 행위를 실행한다. 이 구조는 Call by reference 다.

Kotlin 에서 매개변수는 기본적으로 불변이기도 하고 기본 자료형이 따로 존재하지 않고 모두 클래스라 Call by reference로만 작동한다. (알고는 있었지만 상세 이유는 몰랐다.)

그 근본적인 구조로 사용중인 inline, wrapper class는 이해가 추가로 필요할 것 같다.

inline class와 typealias는 유사해보이지만 typealias는 별칭일 뿐이고 inline class는 사용한 기존 타입과 완전히 별개의 class로 취급받는다.

wrapper class는 primitive type을 객체로 변환해둔 것이다. inline class로 설계한 것과 자바 바이트 코드에서도 다르게 설계된다.

클래스, 객체, 인스턴스를 각각 용어정리하면 이런 느낌이다:

객체: 범용적인 개념을 가지고 있는 클래스 구현체

인스턴스: 힙 메모리에 올라가 있는 진짜 객체

클래스: 객체를 구현하기 위한 설계도

생성자를 객체 생성시 최초 1회 호출 가능한 주소를 반환하는 특별한 메소드라고 볼 수 있다.

의존성은 다른 인스턴스의 주소를 얼만큼 알고 있는지를 의미한다고도 할 수 있다.

Exception은 예외객체라 부를 수 있다. 예외가 발생했다면 어딘가에선 반드시 throw로 예외객체를 던져준 것이다.

try-catch는 예외 처리이기도 하지만 예외 회복 이라는 키워드로도 표현 가능하다.

Exception을 직접 만들어서 쓸 때 던져주는 시점을 일일이 던져주는 게 아니라 catch 안에서 새로 묶어 보내주면 에러 리포팅 관리가 더 쉬워질 것이다.

예외를 처리하지 않고 상위 메소드로 전파하는 회피 키워드가 있다.

알고리즘 특강 2회차 - 시간 복잡도

순회가 늘었다, 줄었다라고만 하는 나는 사실 시간 복잡도를 정확히 표현할 줄은 모른다. 그래프로 그려지는 O(1), O(n) 정도는 대충 아는데 내가 짠 코드가 정확히 얼만큼의 시간 복잡도를 가지는지 항상 헷갈려서 확신을 가지고 말을 하지 않기 때문에 그냥 순회의 증감으로만 퍼포먼스를 구분하고 있다.

이번 시간은 시간 복잡도를 구체적으로 알려주셨고 좀 쉽게 알아볼 수 있는 것들 위주로 정리했다. 시간 복잡도는 봐도봐도 까먹는다.

공간 복잡도는 써본 경험도 적고 고민해본 경험도 적어서 이번에 많이 배웠다.

시간 복잡도는 Big-O(최악), Big-Ω(오메가, 최고), Big-θ(세타, 평균) 으로 나눌 수 있는데 보통 빅-오 표기법을 사용한다. (상한 점근법이라고도 한다.)

최악의 상황을 가정할 때가 많다보니 Big-O를 쓴다.

O(n) 에서 한 번만에 찾아도 점근 표기법상 O(1)이라고 표기하는 게 아니다.

O(n) = n번 만큼, O(n^2) = 이중포문 순회

표기할 때 큰 값을 따라가되 곱연산은 반영된다

O(n^2) + O(n) = O(n^2)

O(n) + O(n) * O(logn) = O(nlogn)

.sum() 과 같은 메소드 코드는 구현된 코드를 살펴보고 시간 복잡도를 알아내야 한다.

수학 공식을 써서 순회 없이 풀었다면 O(1)이다.

수학 수식을 작성하라는 식의 요구문제는 거의 출제 되지 않는다. 시간 복잡도의 차이를 주로 알면 된다.

프로그래밍상 이진법을 쓰기 때문에 O(logN)은 O(log2N)과 같다.

Big-O Complexity Chart로 그래프을 눈에 익히는 것도 좋을 것 같다.

List, Map, Set등 콜렉션 내장 함수도 시간 복잡도를 알고 쓰면 더 좋다.

공간 복잡도는 프로그램을 실행하고 완료까지 사용한 공간의 양을 뜻한다.

함수의 호출은 Stack 을 차지하고 따라서 팩토리얼 재귀함수같은 재귀함수의 공간복잡도는 O(n)이다.

재귀함수 말고 for문으로 재귀함수를 구하면 같은 시간복잡도에 공간복잡도는 O(1)로 줄어든다.

비용적으로 메모리 늘리기 < CPU 변경하기라서 시간 복잡도를 우선시 하는 경우가 많다.

숫자야구 발전시키기

숫자 야구 정답 랜덤 알고리즘 바꾸기

최근 코드카타 문제를 보다보면 Map을 이용해서 처리하면 쉽겠구나 하는 것들을 떠올리곤 하는데 갑자기 문득 숫자 야구 생각이 나서 숫자 야구 정답 알고리즘도 바꿀만한 여지가 있지 않을까? 생각이 들어서 찾다보니 Map 활용은 아니지만 간단하게 줄일 수 있어서 수정을 했다.

do {
    this.answer = (0..9).toList().shuffled().slice(0 until this.difficulty.length).joinToString("")
} while (this.answer.first() == '0')

0부터 9까지 정해진 범위 내에서만 값이 정해지기 때문에 랜덤한 0..9 범위가 있다면 그 중 난이도만큼만 잘라서 쓰면 아주 쉽게 랜덤값을 뽑아올 수 있었다.

이전 알고리즘은 정해진 범위가 아니라도 대응할 여지가 있긴 하겠지만 새로운 방식보다 퍼포먼스는 떨어질테니 숫자야구에 맞는 알고리즘은 새로운 방법이 맞는 것 같다.

첫 자리 숫자 0을 방지하기 위해서라면 shuffle 까지만 반복하며 예외처리 하다가 slice하는 게 더 성능 최적화가 될 것 같은데 짧게 쓰고 싶어서 그냥 두기로 했다.

파일 입출력으로 시행횟수 관리하기

class NumberBaseballIOUtils private constructor() {
    private val file = File(Constants.RECORD_FILE_PATH)

    /**
     * 게임 기록을 파일에서 읽어 줄마다 구분해 반환합니다.
     *
     * @return 게임 기록이 담긴 List<String>
     */
    fun getGameRecords(): List<String> {
        if (this.file.readLines().isEmpty()) throw Exception("게임 기록이 없습니다.")

        return this.file.readLines()
    }

    /**
     * NumberBaseballGameRecord에서 난이도와 입력 횟수를 얻어 파일에 기록합니다.
     *
     * @param 한 게임이 끝난 기록이 담긴 NumberBaseballGameRecord
     */
    fun addGameRecord(gameRecord: NumberBaseballGameRecord) {
        this.file.appendText("${gameRecord.difficulty.name} : ${gameRecord.inputCount}\n")
    }

    companion object {
        private var instance: NumberBaseballIOUtils? = null

        /**
         * 유틸리티는 Singleton instance로 관리
         *
         */
        fun getInstance(): NumberBaseballIOUtils = this.instance ?: NumberBaseballIOUtils()
    }
}

한 번의 실행에서 풀이를 기록하는 건 재미가 없으므로 파일 입출력을 통해 records.txt 에 저장해서 불러오기로 했다. 원래 SQLite 처럼 로컬DB 같은 걸 찾아봤는데 이건 Android storage를 쓰는 거다 보니 JVM 위에서 돌아가는 단일 프로젝트 구조에선 쓸 수는 있는데 안드로이드처럼 써지는지 불확실해서 그냥 파일입출력으로 하기로 했다.

유틸리티는 앱에서 쓸 때 어지간해선 Singleton 패턴으로 관리를 해서 이번에도 그렇게 했고 관습적으로 하는 거긴 하지만 유틸리티에서 같은 데이터를 지속적으로 참조한다면 Singleton instance가 적절한 패턴이 맞다고 생각한다.

텍스트로 저장하는 데이터 양식이 좀 구리긴 한데 지금은 기능 구현을 우선으로 하고 있고 디테일은 나중에나 생각해야겠다.

아래 코드는 유틸리티성 파일로 Data class와 Constants도 새로 만들었다.

// 게임 기록용
data class NumberBaseballGameRecord(var difficulty: NumberBaseballDifficulty, var inputCount: Int)

// 상수 기록용
object Constants {
    const val RECORD_FILE_PATH = "src/main/resources/record.txt"
}

코드카타 - 프로그래머스 가장 가까운 같은 글자

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

문제 링크

fun solution(s: String): IntArray {
    val answer = mutableListOf<Int>()
    val charMap = mutableMapOf<Char, Int>()
    
    s.forEachIndexed { index, char ->
        if (charMap.contains(char)) answer.add(index - charMap[char]!!)
        else { answer.add(-1) }
        
        charMap[char] = index
    }
    
    return answer.toIntArray()
}

보자마자 Map 으로 풀면 될 것 같아서 뚝딱 해치웠다. Map의 특성상 Index 정보만 갖고 있어도 가장 가까운 값이라는 명제를 돌파하기엔 충분했다.

제출 전에 다른 방법으로 해볼 수 있는 방법을 고민해봤는데 순회 횟수를 늘리지 않고서야 불가능하지 않나? 생각이 들었고 나쁘지 않은 결과물로 제출했다.

다른 풀이중에서도 비슷하거나 순회 횟수가 늘어난 방식이 많아서 괜찮게 푼 건 맞는데 Kotlin 스럽게 해결한 풀이 하나가 있어서 가져왔다.

fun solution2(s: String): List<Int> {
    return s.withIndex().map { (i, c) -> s.slice(0 until i).lastIndexOf(c).let { if (it >= 0) i - it else -1 } }
}

index 크기에 맞춰 자른 문자열에서 lastIndex로 계속 현재 Char Index를 가져오고 lastIndex와 index를 비교해서 반환하는 깔끔한 함수였다.

Kotlin style로 깔끔하게 작성된 건 마음에 드는데 다만 순회 자체는 꽤 늘어서 퍼포먼스 차이가 나는 건 어쩔 수 없지만 아쉬웠다.

노재원

mobz

이전 포스트

240430 프로그래밍 심화 - 숫자 야구 만들기

다음 포스트

240502 프로그래밍 심화 - 숫자 야구 마무리하고 리뷰하기

1개의 댓글

류원형

2024년 5월 1일

오호... 잘 배우고 갑니다. 감사합니다.

답글 달기