재귀 함수 응용

따로 튜터팀께서 직접 라이브 시연으로 재귀 함수를 응용하는걸 보여주셨다.

정수로 이루어진 배열의 요소들을 더하거나 빼서 특정한 숫자를 만드는 문제에 대한 풀이었는데

듣기는 했으나 이해가 어려워 일단 강의 자료를 기록해둔다..

 

# Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 '더하거나 빼서' 특정한 숫자를 만들려고 한다.
# 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
# -1+1+1+1+1 = 3
# +1-1+1+1+1 = 3
# +1+1-1+1+1 = 3
# +1+1+1-1+1 = 3
# +1+1+1+1-1 = 3

# 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘거 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

numbers = [1, 1, 1, 1, 1]
target_number = 3
sums = []

def get_all_combinations(numbers, curr_idx, curr_sum):
    # 1 (+-) 1 (+-) 1 (+-) 1 (+-) 1
    # 경우의 수 : 32개

    if curr_idx == len(numbers):
        return sums.append(curr_sum)

    get_all_combinations(numbers, curr_idx + 1, curr_sum + numbers[curr_idx])
    get_all_combinations(numbers, curr_idx + 1, curr_sum - numbers[curr_idx])

get_all_combinations(numbers, 0, 0)
print('sum: ', sums)

 

재귀 함수 말고도 반복문을 통해 이 문제를 해결할 수 있다고 한다.

+1과 -1로 이루어진 배열이기에 binary 즉, 2진법을 쓰면 된다는건데 풀이 방법은 아래와 같다.

# Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 '더하거나 빼서' 특정한 숫자를 만들려고 한다.
# 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
# -1+1+1+1+1 = 3
# +1-1+1+1+1 = 3
# +1+1-1+1+1 = 3
# +1+1+1-1+1 = 3
# +1+1+1+1-1 = 3

# 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘거 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

numbers = [1, 1, 1, 1, 1]
target_number = 3
sums = []

# 반복문으로 해보자
def get_all_combinations(numbers):
    # 1 (+-) 1 (+-) 1 (+-) 1 (+-) 1
    # 경우의 수 : 32개

    # binary => +, - => 1, 0으로 나타낼 수 있을거 같음
    # 32개의 경우의 수 => -----(0) ~ +++++(31) => 00000(2) ~ 11111(2)

    number_of_operator = 2 # +, -만 지원
    for i in range(number_of_operator ** len(numbers)):
        # [0, 0, 0, 0, 0] ~ [1, 1, 1, 1, 1]
        binary_value = '{:05b}'.format(i) # 0 ~ 31 => 00000 ~ 11111
        # print('binary_value: ', binary_value)

        # list comprehension
        operators = [int(el) for el in list(binary_value)]
        print('operators:', operators) # -> sum을 계산하기 위해 이렇게 만듦

        # operator에 따라서 더하거나 빼거나
        curr_sum = numbers[0] if operators[0] == 1 else -numbers[0]
        for j in range(1, len(numbers)):
            if operators[j] == 1:
                curr_sum += numbers[j]
            else:
                curr_sum -= numbers[j]
        sums.append(curr_sum)


get_all_combinations(numbers)
print('sum: ', sums)
print(len(sums))

포맷 변환이라던지 리스트 컴프리헨션이라던지 익숙하지 않은 파이썬 문법들이 나와 어지럽지만

코딩을 잘하려면 이정도의 유연한 사고력이 있어야 되는구나라고 새삼 느끼게 되는 강의였다.