수리링의 데이터교실

https://school.programmers.co.kr/learn/courses/30/lessons/12945

오랜만에 피보나치 수열 문제 풀이를 했습니다. 처음에 간단한 재귀함수를 적용해서 풀이를 했더니 테스트는 모두 통과하는데 효율성 테스트에서 시간 초과로 계속 실패를 하는 문제가 발생했습니다. 그래서 효율성을 올리기 위해 메모화를 적용해서 풀이를 했더니 효율성 테스트도 모두 통과할 수가 있었습니다 :-)

간단하게 풀이방법을 설명해 보겠습니다!

1. 메모화 없이 기본 피보나치 수열 함수 작성하기

def basic_fibonacci(n):
    if n in [1, 2]:
        return 1
    if n == 3:
        return 2

    return basic_fibonacci(n-2) + basic_fibonacci(n-1)

만약 주어진 정수가 1 또는 2라면 바로 1을 리턴,

주어진 정수가 3이라면 바로 2를 리턴하도록 초기 설정을 해 줍니다.

4 이상의 정수 n이 주어졌을 때 재귀함수 형식으로 n-2와 n-1에 basic_fibonacci 함수를 적용한 값을 구해 더한 값을 리턴합니다.

basic_fibonacci(8), basic_fibonacci(9), basic_fibonacci(10), basic_fibonacci(11)
# (21, 34, 55, 89)

위 함수는 제대로 작동하지만, n의 값이 커질수록 효율성이 급격하게 떨어진다는 단점이 있어요. 메모화를 이용해서 함수의 효율을 높여보겠습니다.

2. 메모화를 적용한 피보나치 수열 함수 작성하기

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    if n > 6:
        for i in range(7, n+1):
            if i in memo: pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

하나씩 뜯어보겠습니다 :)

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):

가장 먼저 함수를 선언할 때 파라미터 값으로 memo라는 이름으로 딕셔너리를 포함해 주었습니다. 저는 간단하게 n이 1부터 6번째일때 피보나치 수열 값을 딕셔너리에 초기값으로 미리 메모를 해 두었습니다.

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]

내가 구하고자 하는 것은 피보나치 수열의 n번째 값입니다. 만약 n이 2, 3, 4, 5, 6인 경우 (문제 조건에서 n은 2 이상의 정수라고 했으므로 1은 제외합니다) memo 딕셔너리의 해당하는 value 값을 바로 리턴하고 함수를 종료하게 됩니다.

    if n > 6:
        for i in range(7, n+1):
            if i in memo: pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

만약 n이 6보다 크면 어떻게 해야 할까요?

주어진 n의 값이 50일 때를 예시로 생각해 봅시다. 우리는 50번째 값을 구하기 위해 48, 49번째 값이 필요합니다.

49번째 값을 구하기 위해서는 47, 48번째가 필요하고

48번째 값을 구하기 위해서는 46, 47번째가 필요합니다.

결국 50번째 값을 구하기 위해서는 1부터 49번째까지 피보나치 수열 값을 모두 알아야 합니다.

그럼 메모화는 어떻게 작동할까요?

제가 만약 50번째 피보나치 수열 값을 구하기 전에,

40번째 피보나치 수열 값을 먼저 구했다고 생각해 보겠습니다.

fibonacci(40)
# 102334155

우리는 40번째 피보나치 수열 값을 구하기 위해 지금 1번째~39번째 피보나치 수열의 값을 열심히 구했습니다.

이제 다음으로 50번째 피보나치 수열 값을 구하려고 합니다.

먼저 메모화를 해놓지 않은 경우를 생각해 봅시다.

우리는 이미 1번부터 40번째까지의 값을 이전에 미리 구한 전적이 있지만

따로 기록을 해 두지 않았기 때문에 같은 계산을 또 반복해야 합니다.

1번째~49번째 피보나치 수열 값을 열심히 또 구하는 거죠.

하지만 제가 기록을(메모화를) 해 두었다면 얘기가 달라집니다.

즉 처음에 fibonacci(40)을 계산했을 때

memo 딕셔너리에 1번부터 40번까지 피보나치 수열 값을

key(n) : value(값) 형식으로 미리 저장을 해 두었다면,

우리는 fibonacci(50)을 구할 때 

1. 1번부터 40번까지는 간단히 딕셔너리에서 값을 찾아 가져올 수 있습니다.

2. 41번부터 49번째 값은 새로 구하고 딕셔너리에 값을 추가해주는 방식으로 계속해서 메모를 해나갈 수 있습니다.

+ 참고로 함수를 여러번 작동하면서 메모장에 추가하는 key와 value 값은 매번 초기화되지 않고 계속해서 누적 기록을 보관합니다.

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    # 주어진 정수가 2-6중 하나일 경우 바로 메모장에서 수열값을 찾아 리턴, 함수종료
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    # 주어진 정수가 6보다 큰 경우(7 이상)
    if n > 6:
    	# 7부터 n까지의 정수 i에 대해서
        for i in range(7, n+1):
            # 만약 메모장에 i값이 이미 메모되어 있다면 그냥 넘어가고
            if i in memo: 
                pass
            # 만약 메모장에 i값이 없다면 피보나치 수를 구해서 추가해주세요
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    # 메모장에서 n번째 피보나치 수열 값을 찾아 리턴해주세요
    return memo[n]

최종 피보나치 함수입니다 :)

내가 구하고자 하는 n의 피보나치 값을 찾기 위해 7부터 n-1번째의 수열값을 계속해서 차례대로 메모장에 누적 메모해나가는 방식입니다. 재귀함수랑 약간 비슷한듯 다른 느낌이네요!

3. 최종 문제풀이

마지막으로 문제 해결을 위해 피보나치 수열을 활용해서 soluton()함수를 작성했습니다. 저는 코딩테스트 문제를 풀 때 이렇게 함수를 나누어 작성하는것을 좋아합니다. 함수 안에 함수 작성하는거 시러요.....(개취)

def fibonacci(n, memo = {1:1, 2:1, 3:2, 4:3, 5:5, 6:8}):
    if n in [2, 3, 4, 5, 6]:
        return memo[n]
    
    if n > 6:
        for i in range(7, n+1):
            if i in memo: 
                pass
            else:
                memo[i] = memo[i-2] + memo[i-1]
    
    return memo[n]

def solution(n):
    fibo_num = fibonacci(n)
    
    # fibonacci(30)< 1234567 < fibonacci(31)
    # 만약 n이 30 이하라면 바로 fibo_num을 리턴하고(몫이 0이므로 나머지와 동일)
    if n <= 30 : 
        return fibo_num
    # 만약 n이 30보다 크다면 fibo_num을 1234567으로 나눈 나머지를 리턴
    else :
        return fibo_num % 1234567

풀이나 설명에 오류가 있다면 댓글로 알려주세요!

감사합니다! :-)

가끔 코딩 테스트에서 이거.. 리스트를 평탄화해주면 쉽게 풀 수 있겠는데? 라는 생각이 들 때가 있습니다. 프로그래머스 0단계에서는 이 평탄화 함수를 작성하는 것 자체가 문제로 출제되기도 했었던거 같기도 하구요. 어쨌든 알고 있으면(또는 외워 두면) 정말 너무나!!!! 큰 도움이 되는!!!!! 평탄화 함수 작성하는 방법!!! 정리해 봅시다.

* 설명 없이 함수만 빠르게 확인하고 싶으시다면 글 맨 아래로 가세요! *

먼저, 중첩 리스트란 무엇일까요?

normal_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
weird_list = [1, 2, [3], 4, 5, [6], 7, [8, 9, 10]]
crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]

위 세 가지 리스트를 살펴 봅시다.

먼저 멀쩡한 리스트 normal_list는 참 보기 좋습니다.

그런데 weird_list는 리스트 안에 리스트를 원소로 가지고 있네요. [3], [6], [8, 9, 10]과 같이 말이죠. 이런 놈들을 중첩 리스트라고 부르겠습니다. 그래도 여기까진 어찌저찌 해체해볼 수 있을 것 같습니다.

그런데 crazy_list.. 이 미친놈을 보니까 리스트 안에 리스트가 또 리스트를 가지고 있어요. 중첩에 중첩에 중첩에 중첩에 중...!!!

평탄화란? (Flatten)

weird_list, crazy_list, crazy_list_and_tuple처럼 중첩된 리스트를

normal_list처럼 1차원의 리스트로 평평(Flat)하게 평탄화(Flatten)해주는 작업을 의미합니다.

만약 우리가 리스트 안에 있는 모든 값들 중에서 가장 큰 값을 구해야 된다면 어떻게 할까요?

normal_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
max(normal_list)
# 10

crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]
max(crazy_list)
# ????????

1차원 리스트인 normal_list의 경우 내장함수 max()를 사용하면 아주 쉽게 최댓값을 구해낼 수 있지만, 우리의 미친놈 crazy_list는 그렇게 호락호락하지가 않습니다. 

평탄화 함수 작업하기

weird_list = [1, 2, [3], 4, 5, [6], 7, [8, 9, 10]]

def easy_flatten(nested_list):
    result = []

    for element in nested_list:
        if isinstance(element, list):
            result.extend(element)
        else:
            result.append(element)

    return result
    
easy_flatten(weird_list)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]
easy_flatten(crazy_list)
# [1, 2, [3], 4, 5, [6], 7, [8, [9, [10]]]]

def hard_flatten(nested_list):
    result = []

    for element in nested_list:
        if isinstance(element, list):
            # 유일하게 달라진 부분 - element 대신 hard_flatten(element)❤️
            result.extend(hard_flatten(element))
        else:
            result.append(element)

    return result

crazy_list = [1, 2, [[3], 4, 5], [[6], 7, [8, [9, [10]]]]]
hard_flatten(crazy_list)
#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

(적용 예시)

# 리스트 k에서 하트를 모두 제거한 1차원 리스트를 출력하세요
k = [['a', 'b', ['🩶', 'd']], 'e', 'f', '🩶', [['🩶'], 'i']]

[element for element in hard_flatten(k) if element != '🩶']
# ['a', 'b', 'd', 'e', 'f', 'i']

감사합니당!