[Python] [알고리즘] 5. 스택(3)

#합이 key인 부분집합 구하기

def f(i,k, key):
    if i==k:
        s = 0
        for j in range(k):
            if bit[j]:
                s+=A[j]
        if key == s: #합이 key와 같은 부분집합 출력
            for j in range(k):
                if bit[j]:
                    print(A[j], end = ' ')
            print()
    else:
        bit[i] = 1
        f(i+1, k, key)
        bit[i] = 0
        f(i+1,k, key)

A = [1,2,3,4,5,6,7,8,9,10]
N = len(A)
key = 10
bit = [0]*N
f(0,N, key)​

 

def f(i,k):
    if i==k: #하나의 부분집합 완성
        for j in range(k):
            if bit[j]:
                print(A[j], end =' ')
        print()
    else:
        bit[i] = 1
        f(i+1,k)
        bit[i] = 0
        f(i+1,k)

A = [1,2,3]
N = len(A)
bit = [0]*N
f(0,N)
''' 출력
1 2 3 
1 2 
1 3 
1 
2 3 
2 
3
'''

 

def f(i,k):
    if i==k:
        s = 0
        for j in range(k):
            if bit[j]:
                s+=A[j]
        print(bit, s)
    else:
        bit[i] = 1
        f(i+1,k)
        bit[i] = 0
        f(i+1,k)

A = [1,2,3]
N = len(A)
bit = [0]*N
f(0,N)
'''
[1, 1, 1] 6
[1, 1, 0] 3
[1, 0, 1] 4
[1, 0, 0] 1
[0, 1, 1] 5
[0, 1, 0] 2
[0, 0, 1] 3
[0, 0, 0] 0
'''

 

#합이 key인 부분집합의 존재 유무 파악하기
def f(i,k, key):
    if i==k:
        s = 0
        for j in range(k):
            if bit[j]:
                s+=A[j]
        if key == s:
            return 1
        return 0
    else:
        bit[i] = 1
        if f(i+1, k, key):
            return 1
        bit[i] = 0
        if f(i+1,k, key):
            return 1
        return 0

A = [1,2,3,4,5,6,7,8,9,10]
N = len(A)
key = 10
bit = [0]*N
print(f(0,N, key))

i번째 원소의 포함 여부에 따라 부분집합의 합이 달라진다. i번째 원소가 포함되지 않은 부분집합의 합을 Si라고 해보자. Si가 찾고자 하는 부분집합의 합보다 크다면 남은 원소를 고려할 필요가 없다.

def f(i,k,s,t): #i원소, k 집합의 크기, s i-1까지 고려한 집합의 합
    global cnt
    if i==k:
        if s==t:
            cnt+=1
        return
    else:
	# bit[k] = 1
        f(i+1,k,s+A[i],t) #A[i]를 포함
	# bit[k] = 0
        f(i+1,k,s,t) #A[i]를 미포함
				#두 가지 경우에 대한 함수를 다 돌리기 때문에(가지가 뻗어 나가기 때문에)
				#이 과정이 필수적이다. 만일 세 개의 가지가 뻗는다면 f가 3번 시행될 것.
A = [1,2,3,4,5,6,7,8,9,10]
N = len(A)
key = 10
cnt = 0
bit = [0]*N

f(0,N,0,key)
print(cnt) #합이 key인 부분집합의 수.

 

def f(i,k,s,t): #i원소, k 집합의 크기, s i-1까지 고려한 집합의 합
    global cnt
    global fcnt
    fcnt+=1
    if i==k:
        if s==t:
            for j in range(k):
                if bit[j]:
                    print(A[j])
            #print()
            cnt+=1
        return
    else:
        # s += A[i]
        f(i+1,k,s+A[i],t) #A[i]를 포함
        # bit[k] = 0
        f(i+1,k,s,t) #A[i]를 미포함
A = [1,2,3,4,5,6,7,8,9,10]
N = len(A)
key = 10
cnt = 0
bit = [0]*N
fcnt = 0 #함수가 도는 수 세기
f(0,N,0,key)
print(cnt) #합이 key인 부분집합의 수
print(fcnt) #2047 출력

#출력은 적게 되는 거 같지만... fcnt가 2047번 돌고 있어서 매우 비효율적이다. 조건을 걸어주자.

#조건 걸어주기
def f(i,k,s,t): #i원소, k 집합의 크기, s i-1까지 고려한 집합의 합
    global cnt
    global fcnt
    fcnt+=1
    if s>t: #조건 걸기
        return
    if i==k:
        if s==t:
            for j in range(k):
                if bit[j]:
                    print(A[j])
                # print()
            cnt+=1
        return
    else:
        f(i+1,k,s+A[i],t) #A[i]를 포함
        f(i+1,k,s,t) #A[i]를 미포함
A = [1,2,3,4,5,6,7,8,9,10]
N = len(A)
key = 10
cnt = 0
bit = [0]*N
fcnt = 0 #함수가 도는 수 세기
f(0,N,0,key)
print(cnt) #합이 key인 부분집합의 수
print(fcnt) #415 출력

 

def f(i,k,s,t): #i원소, k 집합의 크기, s i-1까지 고려한 집합의 합
    global cnt
    global fcnt
    fcnt+=1
    if s>t: #남은 원소가 고려할 필요가 없는 경우의 수
        return
    elif s==t: #남은 원소가 고려할 필요가 없는 경우의 수. 합을 찾았다.
        cnt += 1
        return
    if i==k: #모든 원소가 고려된 것
        if s==t:
            for j in range(k):
                if bit[j]:
                    cnt+=1
        return
    else:
        f(i+1,k,s+A[i],t) #A[i]를 포함
        f(i+1,k,s,t) #A[i]를 미포함
A = [1,2,3,4,5,6,7,8,9,10]
N = len(A)
key = 10
cnt = 0
bit = [0]*N
fcnt = 0 #함수가 도는 수 세기
f(0,N,0,key)
print(cnt) #합이 key인 부분집합의 수
print(fcnt) #349 출력

 

def f(i,k):
    if i==k:
        print(p)
    else:
        #자신을 i라고 하고, 바꿀 자리를 j라고 하자.
        for j in range(k):
            p[i], p[j] = p[j], p[i]
            f(i+1,k)
            p[i], p[j] = p[j], p[i]

p = [1,2,3]
N = len(p)
f(0, N)

 

+순열 만들기

nums = [20,30,40]
#goal = [20,30,40],[40,30,20],[30,20,40],...

def Permutation(k):
    if k==N:
        print(a)
        for i in range(N):
            idx = a[i]
            print(nums[idx], end =' ')
    for i in range(N):#원소가 3개일 경우 순열의 경우의 수는 3개가 되고, 4개일 경우 4개가 되고...
	if not visited[i]:
            visited[i] = True
            a[k] = i
            Permutation(k+1)
            visited[i] = False
#다음 순열을 만들 때 지장받지 않기 위해서 visited를 원복시키는 것임. 차근차근 읽어보면 visited를 원복시켜도 결과에 악영향을 주지 않는다.

N = 3
a = [-1] * N
visited = [False] * N
Permutation(0)

 

 

분할 정복 알고리즘

분할: 해결할 문제를 여러 개의 작은 부분으로 나눈다.

정복: 나눈 작은 문제를 각각 해결한다.

통합: 해결된 해답을 모은다.

퀵 정렬

주어진 배열을 두 개로 분할하고, 각각을 정렬한다. 병합정렬과 다른 점은 병합정렬은 그냥 두 부분으로 나누는 반면, 퀵정렬은 분할할 때 기준 아이템 중심으로, 이보다 작은 건 왼편, 큰 건 오른편에 위치시킨다. 각 부분 정렬이 끝난 후, 병힙정렬은 ‘병합’이란 후처리 작업이 필요하나, 퀵정렬은 필요로 하지 않는다. 평균적으로 빠르게 진행되나 O는 n^2이다.

def quicksort(a,begin, end):
    if begin < end:
        p = partition(a,begin,end)
        quicksort(a,begin,p-1) #피봇을 기준으로 왼쪽 정렬
        quicksort(a,p+1,end) #피봇을 기준으로 오른쪽 정렬

def partition(a,begin, end):
    pivot = (begin+end)//2
    L = begin
    R = end
    while L<R:
        while(L<R and a[L] < a[pivot]):
            L += 1
        while(L<R and a[R]>=a[pivot]):
            R -= 1
        if L<R:
            if L==pivot: #L 영역에 피봇보다 작은 값만 모여 있다면
                pivot = R
            else:
                a[L], a[R] = a[R], a[L]
    a[pivot], a[R] = a[R], a[pivot]
    return R