파이썬 알고리즘 179번 | [백준 14225번] 부분 수열의 합

Yunny.Log ·2022년 6월 20일

Algorithm

목록 보기

182/318

179. 부분 수열의 합

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

import sys
from itertools import combinations

n = int(sys.stdin.readline().rstrip())
s = list(map(int,sys.stdin.readline().rstrip().split()))

sums = []
for i in range(1,n+1) :
    combi=list(combinations(s,i)) #i는 1,2,3 으로 증가해나감
    # combi의 생김새
    # i가 1 : [(5,), (1,), (2,)]
    # i가 2 : [(5, 1), (5, 2), (1, 2)]
    # i가 3 : [(5, 1, 2)]
    for i in combi :
        sums.append(sum(i))

sums=sorted(set(sums)) 
# 부분수열 합의 모든 경우 (중복 없이, 오름차순 정렬)

start = 1 #자연수 중 sums에 없는 것

for i in sums : 
    print(i, start)
    if i!=start : # start는 1부터 하나씩 올라가는 아이
        # 부분 합에 속하는 i가 start와 다르다면 , 그 순간의
        # start가 부분합에 속하지 않는 최소의 아이 
        break
    else : start+=1 # 1부터 2,3,4, ... 올라감 

print(start)

이런걸 개선했더니 통과가 되드라

1) 기존

sums=sorted(sums)

start =0 

while True:
    start+=1
    if start not in sums :
        print(start)
        break

기존에는 매번 in구문으로 sums 안에 start 가 존재하는지 여부를 살펴줬었음
in의 시간 복잡도는 리스트의 수 (O(N)), 그리고 나는 while True로 찾을때까지 돌아서 for문의 시간복잡도임 (O(N)) 이 곱해져서 (O(N^2)) 임, 근데 최악의 경우는 2000000(200만), O(N^2) 는 만 의 입력부터 1초정도 소요된다고 하니 , 시간초과 걸릴 수 밖에!

2) 개선


sums=sorted(set(sums)) 
# 부분수열 합의 모든 경우 (중복 없이, 오름차순 정렬)

start = 1 #자연수 중 sums에 없는 것

for i in sums : 
    print(i, start)
    if i!=start : # start는 1부터 하나씩 올라가는 아이
        # 부분 합에 속하는 i가 start와 다르다면 , 그 순간의
        # start가 부분합에 속하지 않는 최소의 아이 
        break
    else : start+=1 # 1부터 2,3,4, ... 올라감 

print(start)

이 친구는 반대로 for 문하나만 가지고 진행하기 때문에 O(N)
O(N)은 입력이 1억 들어와야 겨우 1초 걸리기 때문에안정적 통과 가능

<내 틀렸던 풀이, 문제점>


from itertools import combinations

import sys

n = int(sys.stdin.readline().rstrip())
s = list(map(int,sys.stdin.readline().rstrip().split()))

sums = []

# 조합의 경우 다 구해서 리스트에 담아두기
for i in range(1,n+1) : #1개부터 n개까지 뽑기 가능
    combi=list(combinations(s,i))
    # combi의 생김새
    # i가 1 : [(5,), (1,), (2,)]
    # i가 2 : [(5, 1), (5, 2), (1, 2)]
    # i가 3 : [(5, 1, 2)]
    for i in combi :
        sums.append(sum(i))
    # sums 의 생김새
    # i가 1 : [(5,), (1,), (2,)]
    # i가 2 : [(5, 1), (5, 2), (1, 2)]
    # i가 3 : [(5, 1, 2)]

sums=list(set(sorted(sums)))

for i in range(1,len(sums)) :
    if sums[i]-sums[i-1] > 1 :
        print(sums[i-1]+1)
        break
else : print((sums[-1])+1)

아주 오랫동안 기다리는 중입니다 뜨더니 틀렸습니다로 바로 가버림

왜냐하면 말 그대로 틀렸기 때문,, sort 한 다음 set 을 한번 더 입혀줬었는데, 이때 순서가 오름차순이 아니고 이상한 순서로 되어있었음

from itertools import combinations

import sys

n = int(sys.stdin.readline().rstrip())
s = list(map(int,sys.stdin.readline().rstrip().split()))

sums = []

# 조합의 경우 다 구해서 리스트에 담아두기
for i in range(1,n+1) : #1개부터 n개까지 뽑기 가능
    combi=list(combinations(s,i))
    # combi의 생김새
    # i가 1 : [(5,), (1,), (2,)]
    # i가 2 : [(5, 1), (5, 2), (1, 2)]
    # i가 3 : [(5, 1, 2)]
    for i in combi :
        sums.append(sum(i))
    # sums 의 생김새
    # i가 1 : [(5,), (1,), (2,)]
    # i가 2 : [(5, 1), (5, 2), (1, 2)]
    # i가 3 : [(5, 1, 2)]

sums=sorted(sums)

for i in range(1,len(sums)) :
    #print(sums[i], sums[i-1])
    if sums[i]-sums[i-1] > 1 :
        print(sums[i-1]+1)
        break
else : print((sums[-1])+1)

아주 오랫동안 기다리는 중입니다 라고 뜨는 중, 왜지

=> 반례

2
1 1
3

import sys
from itertools import combinations

n = int(sys.stdin.readline().rstrip())
s = list(map(int,sys.stdin.readline().rstrip().split()))
# s에 1,1 이 들어온다면 1 하나로 생각헤줘야 함 
s = list(set(s)) # 중복제거 
sums = []

for i in range(1,n+1) :
    combi=list(combinations(s,i))

    for i in combi :
        sums.append(sum(i))

sums=sorted(sums)

for i in range(1,len(sums)) :

    if sums[i]-sums[i-1] > 1 :
        print(sums[i-1]+1)
        break
else : print((sums[-1])+1)

네~ 그냥 로직을 잘못 짠 거였어요

import sys
from itertools import combinations

n = int(sys.stdin.readline().rstrip())
s = list(map(int,sys.stdin.readline().rstrip().split()))
# s에 1,1 이 들어온다면 1 하나로 생각헤줘야 함 
# s = list(set(s)) # 중복제거 
sums = []

for i in range(1,n+1) :
    combi=list(combinations(s,i))

    for i in combi :
        sums.append(sum(i))

sums=sorted(sums)

start =0 

while True:
    start+=1
    if start not in sums :
        print(start)
        break

시간 초과 ..

import sys
from itertools import combinations

n = int(sys.stdin.readline().rstrip())
s = list(map(int,sys.stdin.readline().rstrip().split()))
# s에 1,1 이 들어온다면 1 하나로 생각헤줘야 함 
# s = list(set(s)) # 중복제거 
sums = []

for i in range(1,n+1) :
    combi=list(combinations(s,i))

    for i in combi :
        sums.append(sum(i))

sums=sorted(sums)

start =0 

while start < 2000000:
    start+=1
    if start not in sums :
        print(start)
        break

2프로에서 시간초과 발생 !
마지막에 search 하는 부분이 꽤나 시간이 걸려서 개선 필요

<반성 점>

<배운 점>

파이썬 Counter 모듈
set과 list의 차이 ( 출처 : https://www.acmicpc.net/board/view/85746)
- set는 for로 iteration을 돌리면 랜덤한 원소가 나오게 됩니다.(hash table의 특성 때문에 순서가 없어요)
그래서 1,2,3,4,5,6이 subsequences_s라 가정하면
num 이 1,2,3,4,5,6 순서로 뽑히는 것이 아닌 2,4,3,1,5,6등과 같이 의미없는 순서로 뽑히게 됩니다.
파이썬 set은 unordered collection,