엘리스 알고리즘 코드 챌린지, 예선 5일 차 문제

강의는 DFS이다.

강의와 문제는 작은 연관이 있다. 재귀를 쓰면 된다.

문제는 수열 복원(링크 없음, 골5?, 풀이 30분)이고 "길이 n 수열의 부분수열의 개수는 2^n인데 이러한 부분수열의 합이 2^n개 주어지는데 이로부터 길이 n의 원래의 수열을 복원하라"이다. a[i]>=1이라는 조건이 있는데 이게 없으면 어떻게 풀지 모르겠다.

풀이는 그리디 알고리즘에 재귀 혹은 반복문을 쓰면 된다.

000 # 0번째
001
010
011
100 # 1번째
101
110
111 # -1번째

길이 3의 수열의 부분수열은 0을 안 씀, 1을 씀으로 생각할 때 위의 8개와 같고 오름차순으로 정렬할 때 #에 적힌 내용은 자명하다. 그리디하게 처리하려고 고민했지만 이외의 경우의 수가 명확하지 않아서 포기하였다. 한편 미정렬의 0~3번, 4~7번은 서로 a[0]를 안 썼다는 것만 차이가 있다는 것을 관찰할 수 있고 이 a[0]은 100, 즉 정렬의 s[1]이라는 것을 이미 알고 있다. 따라서 두 배열을 분리할 수 있고 이렇게 분리된 배열에 다시 재귀적으로 수행을 하면 정답을 구할 수 있다.

def rec(arr):
    if arr == [0]:
        # "000"만 남은 경우.
        return
    a_0 = arr[1] # arr[0]은 언제나 사용. 000일 때의 원소.
    ans.append(a_1)
    left = []
    # right = [] # 해도 되는데 최적화
    left_unmatched = dict()
    for v in arr:
        if left_unmatched[v-a_0] >= 1:
            left_unmatched[v-a_0] -= 1
            # right.append(v) # 해도 되는데 최적화
        else:
            left_unmatched[v] += 1
            left.append(v)
    rec(left)
    # rec(right) # 절대 하면 안 됨
    return
n = int(input())
s_arr = sorted(map(int, input().split()))
ans = []
rec(s_arr)
print(*ans)

왼쪽 배열은 a[0]을 사용하지 않은 부분 순열이고 오른쪽 배열은 a[0]을 사용한 부분 순열이다. i=0부터 순회를 하며 그렇지 않다면 왼쪽 배열에 넣고, 이미 반대편 값(=자신-a[0])이 왼쪽 배열에 들어가있다면 오른쪽 배열에 넣는다. 이미 왼쪽 배열에 들어가있는지 여부는 딕셔너리로 개수를 세준다. 이렇게 만들어진 왼쪽 배열에서 다시 재귀 함수를 수행하다보면 정답을 찾을 수 있다.
처음에는 "여부"라는 것에 이끌려서 set로 셌는데 중복되는 경우를 제대로 처리하지 못해서 오류가 났고 다행히 중복 여부는 떠올리기 쉬워 금방 디버깅할 수 있었고 딕셔너리로 바꾸었다. 재귀를 한 층 깊이 들어갈 때마다 원본 수열의 원소를 하나 찾을 수 있고 arr의 길이가 절반이 되기 때문에 O(2*2^n, 단 n=원본수열의길이)이다.

# 생략

계수 배열을 구한 뒤에 유사하게 풀어도 된다. 재귀를 하지 않고 배열 자체를 바꾸고(cnt를 기록하는 배열이기 때문에 0으로 수정할 때 시간복잡도가 O(1)이다.) 반복문을 n회 돌리며 반복문마다 a[0]을 찾으면 된다. 시간복잡도는 O(n*num_range, 단 num_range=부분수열의합의최댓값). cnt가 기록된 계수배열 내에서 a[0]을 찾은 뒤 i=0부터 순회하며 s[i]의 cnt>0이라면 s[i]+a[0]의 cnt를 s[i]의 cnt만큼 빼준다. 왜냐하면 그만큼이 left(=s[i])와 매칭되는 right(=s[i]+a[0])의 개수이기 때문이다. 이 풀이는 매칭되는 left과 right의 위치를 인덱싱을 통해 빠르게 접근할 수 있고 개수 역시 빠르게 제거할 수 있다. 나의 풀이는 매칭되는 right가 존재함은 알고있지만 list.find를 쓰지 않고 순회를 기다렸고 제거하는 것도 list.remove를 쓰지 않고 순회를 기다렸다.
n=50으로 크단 것만 빼면 이 문제는 정확히 Subsequence Sums(https://www.acmicpc.net/problem/19073, 맞힌 사람 18명, 플3)이고 풀이 역시 지금의 풀이가 강제된다. 발상 자체가 다소 어렵고 n이 큰 것을 감안해도, 애초에 입력의 한계상 입력이 계수 배열 형태로 들어오기 때문에 발상을 떠올리기 쉬워서 그 정도는 아닌 것 같다.

import sys
from itertools import combinations
def dfs(res, x, sum_, now, m):
    if x == len(res):
        now.append(sum_ + m)
        return
    dfs(res, x + 1, sum_, now, m)
    dfs(res, x + 1, sum_ + res[x], now, m)
def solve():
    n = int(input())
    v = list(map(int, input().split()))
    v.sort()
    res = []
    now = []
    for i in range(1, len(v)):
        if v[i] not in now:
            m = v[i]
            dfs(res, 0, 0, now, m)
            res.append(v[i])
        now.remove(v[i])
    print(' '.join(map(str, res)))
if __name__ == "__main__":
    solve()

위는 솔루션인데 사용하지도 않는 sys, itertools는 왜 있는지 모르겠고 코드가 매우 나쁘다고 생각한다. 시간복잡도는 O(2^n + 2^(n+1) + 2^(n+1)^2)인 듯하다. 여기서 2^n은 바깥 반복문이고, 2^(n+1)은 summation 1 to n(2^i)이고 여기서 2^i는 i 길이의 res로부터 모든 부분 순열을 구하는 경우의 수이고, 2^(n+1)^2는 이러한 부분 순열 내에서 list.remove 연산을 할 때 소요되는 시간이다. n =[12, 13, 14, 15]에 솔루션은 [78, 130, 334, 1126(ms)]가 걸렸고 n=[15, 20, 21, 22]에 대해 내 풀이는 [71, 382, 706, 1370(ms)]가 걸렸다. 나의 풀이는 left, right 모두 arr 내에 존재하는 것이 확실하기 때문에 순회를 기다리며 right를 찾았고 지우는 것은 순회를 기다린 뒤 딕셔너리와 right.append로 O(1)로 지웠는데 솔루션은 O(2^n)으로 새로 생성하고 O(n)으로 새로 지웠기 때문에 훨씬 오래 걸린다. now는 나의 코드의 left, 즉 a[0]을 사용하지 않은 부분 수열에 대응되는 right가 될 예정인 원소들의 모임이다. v[i] not in now라면 right가 아니기 때문에 조금 이따가 res에 추가를 하고, 이미 확정된 정답들(res)로부터 만들어지는(dfs를 이용해) 모든 부분 순열의 합 + v[i]을 해줌으로써 right들을 만들어주고, 모두사용안함+v[i]은 v[i] 자기 자신이 이미 처리를 했기 때문에 now에서 리무브해준다. v[i] in now라면 방금 위에서 설명한 v[i] not in now에서 만들어진 now에 들어가있다는 뜻이기 때문에 정답이 될 수 없고 left에 대응되는 값을 1개만 제거해준다는 의미로 리무브해준다. 참고로 파이썬의 리무브는 첫 원소만 제거한다.