Algorithm_Stack_4

부분집합의 합(subset)

• 집합 {1,2,3}의 원소에 대해 각 부분집합을 사용하기

def f(i, k, key):
    if i == k: # 하나의 부분집합 완성
        s = 0
        for j in range(k):
            if bit[j]:
                s += A[j] # 부분집합의 합
        if s == key: # 합이 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)
bit = [0] * N
key = 10
f(0, N, key)

• 다른 방법

def f(i, k, s, t): # i: 원소, k: 집합의 크기, s: i-1까지 고려된 원소의 합, t: 목표
    global cnt
    if i == k:
        if s == t:
            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

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

---

순열 모두 만들어보기

def f(i, k):
    if i == k:
        print(p)
    else:
        for j in range(i, 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)

---

분할 정복 알고리즘

• 설계전략
  • 분할(Divide): 해결할 문제를 여러개의 작은 부분으로 나눔
  • 정복(Conquer): 나눈 작은 문제를 각각 해결한다.
  • 통합(Combine): - if necessary - 해결된 해답을 모은다.

퀵 정렬

• 최악의 경우 수행시간은 O**2이지만 평균적으로 가장 빠름
• 주어진 배열을 두 개로 분할하고, 각각을 정렬함
• 합병정렬과의 차이점
  • 합병은 그저 두 부분으로 나누는 반면 퀵 정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오픈편에 위치시킴
  • 각 부분 정렬이 끝난 후 합병정렬은 합병이란 후처리 작업이 필요하나 퀵정렬은 필요로 하지 않음

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 : pivot = R
			a[L], a[R] = a[R], a[L]
	a[pivot], a[R] = a[R], a[pivot]
	return R

• 수행과정

예시: {69,10,30,2,16,8,31,22}

1. 원소의 개수가 8개이므로 네번째 자리에 있는 원소 2를 첫번째 피봇으로 선택하고 퀵 정렬 시작

• L이 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾음
• L은 원소 69를 찾았지만, R은 피봇보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 됨
• L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 2의 위치를 확정

1. 피봇 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행

• 오른쪽 부분 집합의 원소가 7개이므로 가운데 있는 원소 16을 피봇으로 선택
• L이 찾은 30과 R이 찾은 8을 서로 교환
• 현재 위치에서 L과 R의 작업을 반복
• L은 원소 69를 찾았지만, R은 피봇보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 됨
• L과 R이 만났으므로 원소 69를 피봇과 교환하여 피봇 원소 16의 위치를 확정

1. 피봇 16의 왼쪽 부분 집합에서 원소 10을 피봇으로 선택하여 퀵 정렬 수행

• L의 원소 10과 R의 원소 8을 교환하는데, L의 원소가 피봇이므로 피봇원소에 대한 자리 교환이 발생한 것이므로 교환한 자리를 피봇 원소 10의 위치로 확정

1. 피봇 10의 확정된 위치에서의 왼쪽 부분 집합은 원소가 한 개이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합은 공집합이므로 역시 퀵 정렬을 수행하지 않음

• 이제 1단계의 피봇이었던 원소 16에 대한 오른쪽 부분 집합에 대해 퀵 정렬을 수행
• 오른쪽 부분 집합의 원소가 4개이므로 두번째 원소 30을 피봇으로 선택
• L이 찾은 69와 R이 찾은 22를 서로 교환한다.
• 현재 위치에서 L과 R의 작업을 반복함. L은 오른쪽으로 이동하면서 피봇보다 크거나 같은 원소인 30을 찾고, R은 왼쪽으로 이동하면서 피봇보다 작은 원소를 찾다가 원소 30에서 L과 만남
• L과 R이 만났으므로 피봇과 교한. 이 경우 R의 원소가 피봇이므로 피봇에 대한 자리교환이 발생한 것이므로 교환한 자리를 피봇의 자리로 확정