시간복잡도 문제

1. 연속 부분 최대합

import sys
import math

def getSubsum(data) :
    '''
    n개의 숫자가 list로 주어질 때, 그 연속 부분 최대합을 반환하는 함수를 작성하세요.
    '''
    '''
    모든 경우를 구하고, 가장 큰 것을 출력
    '''
    result = -math.inf
    temp = 0

    for start in range(0, len(data)):
        for end in range(start, len(data)):
            temp = 0
            for i in range(start, end+1):
                temp += data[i]
            result = max(result, temp)

    return result

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]

    print(getSubsum(data))

if __name__ == "__main__":
    main()

2. 멱집합 구하기

import sys

def getPowerSet(n, k):
    '''
    1부터 n가지의 자연수의 원소가 있을 때 k를 가장 처음으로 선택하는 경우 반환
    3,2
    [[2],[2,3]]

    3,3
    [[3]]
    '''

    if n == k:
        return [[k]]

    '''
    기저조건이 아닌 경우
    getPowerSet(3,1)
    [[1]     [1,2][1,2,3]     [1,3]]

    temp : [[2.][2,3]]

    getPowerSet(3,2)
    [[2],[2,3]]

    temp : [[3]]
    '''

    result = [[k]]

    #뒤에(k뒤에 올 수==i) 붙여질 멱집합들을 temp에 담다.
    temp = []

    for i in range(k+1, n+1):
        temp = temp + getPowerSet(n,i)
        #if k == 1
        # temp = [[2],[2,3],[3]]

    for i in range(len(temp)):
        temp[i] = [k] + temp[i]

    return result+temp


def powerSet(n) :
    '''
    n개의 원소를 가지는 집합 A의 멱집합의 원소를 사전 순서대로 list로 반환하는 함수를 작성하시오.

    예를 들어, n = 3 일 경우 다음의 list를 반환한다.

    [ [1], [1, 2], [1, 3], [1, 2, 3], [2], [2, 3], [3] ]

    (3,1)+(3,2)+(3,3)
    '''
    result = []

    for i in range(1, n+1):
        result += getPowerSet(n,i)


    return result

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    n = int(input())

    result = powerSet(n)
    
    for line in result :
        print(*line)

if __name__ == "__main__":
    main()

3. 균형 맞추기

import sys
import math
'''
모든 부분 집합
멱집합
'''

def getPowerSet(n, k):
    if n == k:
        return [[k]]
    result = [[k]]
    temp = []
    for i in range(k+1, n+1):
        temp = temp + getPowerSet(n,i)
    for i in range(len(temp)):
        temp[i] = [k] + temp[i]

    return result+temp


def powerSet(n) :
    result = []
    for i in range(1, n+1):
        result += getPowerSet(n,i)

    return result

def makeEqual(data) :
    '''
    n개의 숫자를 두 그룹 A, B로 나눈다고 할 때,

    | (A의 원소의 합) - (B의 원소의 합) | 의 최솟값을 반환하는 함수를 작성하시오.
    '''

    # 모든 부분집합 즉 모든 가능성을 가진 집합이 들어가있는 변수
    combinations = powerSet(len(data))
    
    # 전체 부분집합의 합을 나타내는
    total = sum(data)
    
    # 매순간 최솟값을 저장하기위한 변수
    result = math.inf

    for c in combinations:
        mySumA = 0
        mySumB= 0 

        for i in c:
            mySumA += data[i-1]

            mySumB = total - mySumA

        result = min(result, abs(mySumA - mySumB))

    return result

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    data = [int(x) for x in input().split()]

    print(makeEqual(data))

if __name__ == "__main__":
    main()