Classic Computer Science Problems in Python 그러나! 나는 Kotlin으로 작성할 예정!

최근에 아주 편안한 마음으로? 합격해도 가지 않겠어!라는 마음으로? 코빗 미들웨어 개발자 코딩 테스트와 면접을 봤는데..! 면접관들과 이야기를 나누고 보니... 가고 싶어졌다.. 으악!!! 이미 버스는 지나갔으니 어쩔 수 없고.. 면접 때 알고리즘에 대한 중요성을 강조하셔서.. 미루고 미룬 알고리즘에 대해서 열심히 공부하자는 마음을 먹음! 👊🏻

위에 말 그대로 고전 컴퓨터 알고리즘 인 파이썬 이라는 책을 과거에 사서 눈으로만 봤는데! 이번에는 보면서 직접 코딩도 하면서 열심히 습득하려고 한다! 책에서는 Python으로 예제가 되어 있는데! 나는 Kotlin으로 하려고 한다. 파이썬보다는 Kotlin 또는 JS를 마스터하고 싶어 그렇게 선택했다.

알고리즘이란?

알고리즘은 우리가 어떤 문제를 해결할 때 그 절차를 알기 쉽도록 기술하는 논리적인 절차과정을 의미한다. 라고 적혀 있는데..! 어떤 문제를 해결하는데 있어 적절한 자료구조를 이용해서 문제를 풀어가는 과정이라고 생각하자.

알고리즘의 특징

1. 입력(Input)
2. 출력(Output) : 하나 이상의 결과 값이 존재해야 한다.
3. 명확성 : 각 단계는 무엇을 하기 위한 것인지 명확하게 정의해야 한다.
4. 유한성 : 유효한 시간내에 종료되어야 한다.
5. 효과성 : 시간적 / 공간적 효율성이 필요하다.

Chapter1. 작은 문제

피보나치 수열

피보나치 수열은 첫 번째와 두 번째 숫자를 제외한 모든 숫자가 이전 숫자와 합한 숫자를 나열한 수열이다. 이것을 수학적 공식으로 표현 한다면 fib(n) = fib(n-1) + fib(n-2)이다. 이것을 계산하기 위해서 우리는 재귀 함수로 쉽게 구현할 수 있다.

재귀 함수

재귀함수는 자기 자신을 호출하는 함수이다. 재귀 함수에는 아주 중요한 기저 조건이 있다. 바로 탈출 조건이다. 이 탈출 조건을 설정하지 않는다면 무한 루프에 빠지게 된다.

재귀함수를 이용한 방법으로, 기조 조건(base case)에 해당하지 않는 함수가 2번 이상씩 호출되는 케이스를 제거 하기 위해서 메모이제이션을 이용해서 호출 횟수를 줄였다.

fun fibonacci(n: Int): Int {
    val memo = hashMapOf<Int, Int?>(0 to 0, 1 to 1)
    val checksum = memo.getOrPut(n) { null }
    return if (checksum == null) {
        fib3(n - 1) + fib3(n - 2)
    } else {
        memo[n]!!
    }
}

검색 알고리즘

데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해서 살펴보자.

검색과 키

검색은 특정 항목에 주목한다. 여기서는 그 주목하는 항목을 키(key)라고 한다. 검색 알고리즘은 키 값을 기준으로 원하는 값을 찾는다.