[백준] 1182번 부분수열의 합 파이썬 해설

출처 : https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

브루트 포스 알고리즘으로 분류된 문제이다.

완전 탐색 알고리즘이라고도 불리는데, 가능한 모든 경우의 수를 다 따진다는 뜻이다.

 

문제를 두 가지 방법으로 풀어봤다.

첫 번째는 파이썬 모듈을 사용하여 풀었고, 두 번째는 직접 조합을 만들어서 풀었다.

 

1. 파이썬 itertools를 사용한 풀이

---

from itertools import combinations as cb
import sys
input=sys.stdin.readline


if __name__ == "__main__":
    cnt = 0
    n, s = map(int, input().split())
    arr = [*map(int, input().split())]
    
    for i in range(1, n + 1):
        for combination in cb(arr,i):
            if sum(combination) == s:
                cnt += 1

    print(cnt)

combination 함수에 문제에서 주어진 배열을 입력하여 모든 조합을 구한 뒤 조건에 맞는 경우의 개수를 세는 아주 간단한 방법으로 풀 수 있다.

하지만, 파이썬에서 있는 모듈으로 푸는 방법에 만족한다면, 혹시나 다른 언어로 문제를 풀어야 할 때 뇌 정지가 올 수도 있다.
모듈을 사용하지 않는 방법을 사용하여 풀어보는것도 실력 향상에 도움이 된다고 생각한다.

 

 

2. 모듈을 사용하지 않는 풀이

---

import sys
input=sys.stdin.readline

def make_comb(arr, comb, s):
    cnt = 0
    for front in arr:
        for end in list(comb):
            comb.append(front + end)
            if comb[-1] == s:
                cnt += 1
    return cnt

if __name__ == "__main__":
    n, s = map(int, input().split())
    comb = [0]
    cnt = make_comb([*map(int, input().split())], comb, s)
    print(cnt)

combination 모듈을 직접 구현한 풀이이다.

0을 원소로 가지는 리스트 comb를 선언해주고 comb리스트과 입력받은 리스트를 이용해서 조합을 찾는다.

front + end 부분이 이해가 안 될 수도 있다.

천천히 어떻게 동작하는지 분석해보면 어려운 알고리즘이 아니란 것을 알 수 있다.

1. 입력받은 배열의 원소를 for문의 조건으로 반복문을 만든다.
2. comb 리스트의 원소를 for문의 조건으로 반복문을 만든다.
3. 2중 for문 안에서 front (입력받은 리스트의 원소) + end (comb 리스트의 원소)를 계산한다.
4. 처음 원소 0 때문에 입력받은 배열의 원소가 혼자 선택 될 경우를 계산할 수 있게 된다.
5. 2중 for문을 진행하면서 모든 조합을 계산할 수 있게 된다. (print 함수를 이용해서 comb를 출력하는 것도 좋은 방법이다.)

두 번째 for문의 조건에서 "list(comb)"라는 문법을 사용한 이유는 그냥 comb를 조건으로 사용할 경우 바로 아랫줄의 comb.append 구문에 의해 반복문의 횟수가 무한대로 증가하기 때문이다.
(깊은 복사의 개념으로 조건을 넘긴다고 생각하면 될 것 같다.)

 

결과

---

빨간 줄 아래가 모듈을 사용한 풀이이고, 빨간 줄 위에 모듈을 사용하지 않은 풀이이다.

시간을 조금이라도 줄이고 싶어서 여러 가지 방법을 시도해봤다.

메모리는 늘어났지만 시간을 줄이는 데 성공했다! 기분이 좋다!

이번 문제도 한 번에 맞혀서 여러 가지로 기분 좋게 푼 문제였다.