[크래프톤 정글 ] 백준 1182 번

정글에 입소한지 0주차 가지나고 1주차에 접어들어 알고리즘 시험을 보게 되었다 .

시간은 1시간 30분 상,중,하 하나씩 총 3문제 가 출제 되었는데 , 결과는 처참했다. 하 문제 하나 겨우 풀었지만 그마저도 시간초과 ...ㅋㅋㅋ;;;;

그 비참한 결과를 다음주에는 반복하지 않고자 1주차 문제를 하나씩 풀어보려고 한다.

접근 방식

이 문제는 탐색을 사용하여 푸는 문제이기 때문에 접근 할수 있는 방법은 다양하다 대표적으로 다음과 같은 방법들을 이용하여 접근해 볼수 있을거같다

1. 재귀와 백트래킹 (Brute-force 방법)

이 방법은 모든 가능한 부분수열을 재귀적으로 탐색하여 부분수열의 합이 ( S )와 일치하는 경우의 수를 세는 방식이다.

• 설명: 모든 원소를 포함하거나 포함하지 않는 두 가지 선택을 재귀적으로 진행하여 모든 부분수열을 생성한다.
• 복잡도: 시간 복잡도는 ( O(2^N) )이다.
• 장점: 구현이 직관적이고 간단하다.
• 단점: 시간 복잡도가 크므로 N이 클 경우 비효율 적일 수 있다.

2. Meet in the Middle

수열을 두 개의 작은 부분으로 나누고, 각 부분에 대해 가능한 모든 부분수열의 합을 구한 후, 두 부분에서 합이 ( S )가 되는 조합을 찾는 방법이다.

• 설명:
  • 수열을 두 부분으로 [1, 2, 3, 4]는 [1, 2]와 [3, 4]와 같이 나눈다.
  • 각 부분에서 가능한 부분수열의 합을 모두 구한다.
  • 두 부분의 부분수열 합을 더해 ( S )가 되는 조합을 찾는다.
• 복잡도: 시간 복잡도는 ( O(2^{N/2}) ), 공간 복잡도도 비슷하다.
• 장점: 시간 복잡도를 크게 줄일 수 있는데, N이 약 40 정도일 때 유효하다.
• 단점: 구현이 비교적 복잡할 수 있으며, 추가 메모리가 필요할수 있다.

3. 메모이제이션 (Memoization)과 재귀

이미 계산된 결과를 저장하고 재사용하는 메모이제이션을 활용하는 방법이다.

• 설명:
  • 재귀적으로 부분수열을 탐색하면서 이미 계산된 결과를 저장하여 중복 계산을 방지 한다.
  • 특정 인덱스와 현재 합의 조합에 대해 결과를 저장하고 재사용 한다.
• 복잡도: 평균적으로 더 빠르지만, 최악의 경우 여전히 ( O(2^N) )이 될 수 있다.
• 장점: 중복 계산을 방지하여 효율을 높일 수 있다.
• 단점: 구현이 복잡할 수 있으며, 재귀 호출 스택이 커질 수 있다.

내풀이

나는 이번 풀이에서는 1번 방식을 이용하여 풀어 보았다.

나는 일단 먼저 부분수열에 대해 트리 를 그려 보았다.

1. 부분수열에 대한 트리 구조

주어진 수열 [1, 2, 3]에 대해 부분수열을 찾는 과정을 트리 구조로 나타내면 다음과 같다.

      0__________________________ ([], 0)   
                                /        \
      1__________________([1], 1)        ([], 0)
                        /      \         /      \
      2____________([1,2], 3)   ([1], 1) ([2], 2)  ([], 0)
               /       \      /    \   /    \    /    \
      3_([1,2,3], 6) ([1,2], 3) ([1,3], 4) ([1], 1) ([2,3], 5) ([2], 2) ([3], 3) ([], 0)

2. 재귀 호출을 통한 모든 경우의 탐색 과정

이 트리 구조에서 각 노드는 부분수열을 나타내며, 왼쪽 가지는 "현재 원소를 포함하는 경우", 오른쪽 가지는 "현재 원소를 포함하지 않는 경우"를 나타낸다.

단계 1: 첫 번째 원소(1)에 대한 재귀 호출

• 현재 상태: ([], 0) (현재 부분수열은 빈 집합, 합은 0)
• 두 가지 선택:
  • 포함하는 경우: [1]을 포함하여 재귀 호출한다. (([1], 1))
  • 포함하지 않는 경우: [1]을 포함하지 않고 재귀 호출한다. (([], 0))

단계 2: 두 번째 원소(2)에 대한 재귀 호출

1. 포함하는 경우에서:
   • 현재 상태: ([1], 1) (현재 부분수열은 [1], 합은 1)
   • 두 가지 선택:
     • 포함하는 경우: [2]를 포함하여 재귀 호출한다. (([1, 2], 3))
     • 포함하지 않는 경우: [2]를 포함하지 않고 재귀 호출한다. (([1], 1))
2. 포함하지 않는 경우에서:
   • 현재 상태: ([], 0) (현재 부분수열은 빈 집합, 합은 0)
   • 두 가지 선택:
     • 포함하는 경우: [2]를 포함하여 재귀 호출한다. (([2], 2))
     • 포함하지 않는 경우: [2]를 포함하지 않고 재귀 호출한다. (([], 0))

단계 3: 세 번째 원소(3)에 대한 재귀 호출

1. [1, 2]에서:
   • 현재 상태: ([1, 2], 3) (현재 부분수열은 [1, 2], 합은 3)
   • 두 가지 선택:
     • 포함하는 경우: [3]을 포함하여 재귀 호출한다. (([1, 2, 3], 6))
     • 포함하지 않는 경우: [3]을 포함하지 않고 재귀 호출한다. (([1, 2], 3))
2. [1]에서:
   • 현재 상태: ([1], 1) (현재 부분수열은 [1], 합은 1)
   • 두 가지 선택:
     • 포함하는 경우: [3]을 포함하여 재귀 호출한다. (([1, 3], 4))
     • 포함하지 않는 경우: [3]을 포함하지 않고 재귀 호출한다. (([1], 1))
3. [2]에서:
   • 현재 상태: ([2], 2) (현재 부분수열은 [2], 합은 2)
   • 두 가지 선택:
     • 포함하는 경우: [3]을 포함하여 재귀 호출한다. (([2, 3], 5))
     • 포함하지 않는 경우: [3]을 포함하지 않고 재귀 호출한다. (([2], 2))
4. []에서:
   • 현재 상태: ([], 0) (현재 부분수열은 빈 집합, 합은 0)
   • 두 가지 선택:
     • 포함하는 경우: [3]을 포함하여 재귀 호출한다. (([3], 3))
     • 포함하지 않는 경우: [3]을 포함하지 않고 재귀 호출한다. (([], 0))

3. 재귀 호출을 통한 모든 경우의 탐색

따라서 3번 인덱스 일때 해당 부분수열 에서 조합 가능한 모든 경우(2^N)의 경우가 나온다.

문제에서는 S 가 될수 있는 경우의 수 를 묻고 있기에

구현

위의 원리를 이해 했다면 구현은 많이 어렵지는 않다.

original = 0 # 부분수열의 합이 S가 되는 경우의 수를 저장할 변수  
arr = \[\] # 입력받은 수열을 저장할 리스트

def find\_subsequence(index, current\_sum):  
    global original # 함수 외부의 'original' 변수를 사용하기 위해 global로 선언

    # 수열의 끝에 도달한 경우
    if index == len(arr):
        # 현재 부분수열의 합이 S와 같으면 경우의 수 증가
        if current_sum == S:
            original += 1
            return

  # 현재 원소를 포함하는 경우
  find_subsequence(index + 1, current_sum + arr[index])

  # 현재 원소를 포함하지 않는 경우
  find_subsequence(index + 1, current_sum)

# 입력 처리

num = list(map(int, input().split()))

N = num\[0\]  
S = num\[1\]

# N개의 정수를 공백으로 구분하여 입력받기

arr = list(map(int, input().split()))  

if len(arr) != N:  
    print()  
else:  
    # 재귀 호출을 시작  
    find_subsequence(0, 0)

# S가 0일 때 공집합인 경우는 제외
if S == 0:
    original -= 1

print(original)