문제 - 더하거나 빼거나

 

 

# 문제 

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이 
매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.

 

해당 문제를 처음 밨을 때는 부호를 배치해야하고 -1 + 1 = 0 이므로 3을 만드려면 (+1, -1 ) 2개씩 짝지어

배치하면 되는 문제인 줄 알고 조합 문제로 받아드렸다. 따라서 3은 +1이 3개 나머지 2개는 더해서 0이여야하므로 

+는 4개 -1 은 1개 이므로 5C4 = 5 개 의 생각으로 전개를 했었다.  하지만 이 문제를 풀기 전에 팁으로 원소가 1이 아닌 [2, 3, 4]  일 경우 만들 수 있는 원소들을 찾는 알고리즘이 이 문제를 푸는 방법이라고 해서 조합으로는 풀지 못했다. 

물론 모든 경우의 수를 파악하면 되는데 이를 구현하는 방법이 아에 감이 안잡혀서 답안을 참고하였다. 

 

답안에서는 아주 간단해 보이지만 직접 작성할 려고하면 어려웠다. 

 

우선 경우의 수를 파악하는 방법으로는 앞에서부터 부호가 + 인지 - 인지 가지를 생성하면서 경우의 수를 만든다음 

마지막에 계산되는 숫자들을 모아 그 안에 지정된 숫자가 있는지 확인하는 방법이다. 즉 리스트으기 길이가 3개라면 2의 3승 (8) 개의  경우의 수가 생기는 것이다. 

 

def get_all_ways_to_by_doing_plus_or_minus(array, current_index, current_sum, all_ways):
    if current_index == len(array):  # 탈출조건!
        all_ways.append(current_sum)  # 마지막 인덱스에 다다랐을 때 합계를 추가해주면 됩니다.
        return
    get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum + array[current_index], all_ways)
    get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum - array[current_index], all_ways)

해당 함수가 경우의 수를 파악하기 위한 재귀함수로써 

Factorial 구현할 때는 매우 간단했지만 계속해서 초기 리스트를 기억해야하고 이전에 구했었던 값들을 기억해야하는 점에서 구현이 힘들었던것 같다. 

 

해당 함수는 인자가 4개나 들어가는데 [리스트] [현재 인덱스] [합계] [모든 방법 수] 이다 .

처음에는 저렇게나 필요할까? 라는 생각으로 단순히 [리스트] [모든 방법 수] 만 넘겨주고 return 하면 함수 끝나도록 만들어 봤었는데 재귀함수 작성시 실수한 것이 내부함수를 다시 호출 할 때 이전 에 부른 함수에서의 데이터는 접근할 수 없다는 것에 충격을 받아 실패를 했다. - 여기서 멘붕.. 

 

어찌어찌 정신차리고 다시 모범답안을 참고하여 문제를 피드백 해본 후 이해가 되어서 넘어갔지만 앞으로

재귀함수를 통해 함수를 짜는 방법은 꼭 익혀야 겠다는 생각을 했다. 

알고리즘의 장점이 연산이 빨라서 경우의 수를 파악할 수 있다는 점인데 효육적으로 짜려면 꼭 알아야겠다는 생각이 들었다. 

 

---