1. 부분집합(Power Set)

1-1. for문 이용

중첩 for문을 사용하여 구한다. 가변 길이의 원소가 주어지는 경우, 중첩 for문을 사용하여 부분집합을 구할 때 문제가 발생한다.


1-2. Binary Counting 이용

원소 수에 해당하는 N개의 비트열을 사용하여 n번째 비트값이 1이면 n번째 원소가 포함되어 있음을 의미한다.

arr = [1,2,3]
n = len(arr)
for i in range(1<<n) :
​    for j in range(n) :
​        if i & (1<<j) :
​            print(arr[j], end=", ")
​    print()


2. 순열(Permutation)

{1,2,3}에서 2개를 뽑아 순열, 조합, 중복순열, 중복조합 만들기

순열 : {1,2},{1,3},{2,1},{2,3},{3,1},{3,2}
조합 : {1,2},{1,3},{2,3}
중복순열 :{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}
중복조합 : {1,1},{1,2},{1,3},{2,2},{2,3},{3,3}

2-1. for문 이용

def perm() :
    for i in range(N) :
        for j in range(N) :
            if i != j :
                print(a[i],a[j])


2-2. Binary Counting 이용

a =[1,2,3]
R = 2

N = len(a)
visited = [False]*N
t = [0]*R

def perm(k) :
​    if k == R :
​        print(t)
​    else :
​        for i in range(N) :
​            if visited[i] :
​                continue
​            t[k] = a[i]
​            visited[i] = True
​            perm(k+1)
​            visited[i] = False


3. 조합

3-1. for문 이용

def comb():
    for i in range(N-1) :
        for j in range(i+1,N) :
            print(a[i],a[j])


4. 중복순열

4-1. for문 이용

def pi() :
    for i in range(N) :
        for j in range(N) :
            print(a[j],a[i])


5. 중복조합

5-1. for문 이용

def h() :
    for i in range(N) :
        for j in range(i, N) :
            print(a[i],a[j])


6. 그리디

  • 일반적으로 머리 속에 떠오르는 생각을 바로 구현하는 경우, 반드시 최적이라는 보장은 없다.
  • 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 방법

그리디 VS 동적계획법(DP)

  • 그리디: 하위 문제를 풀기 전에 선택이 먼저 이뤄진다.(top-down방식)
  • 동적계획법 : 매 단계의 선택은 해결한 하위 문제의 해를 기반으로 한다.(bottom-up방식)

알고리즘 문제 풀이

1. 거스름돈 줄이기

지폐와 동전의 갯수를 최소한으로 줄일 때, 거스름돈의 갯수는 ? (단, 동전의 케이스는 500, 400, 100, 50, 10)

[예] 800원을 거슬러주는 방법은 400원짜리 동전 2개로 최소 갯수는 2개이다.

  1. 중복순열로 가지치기를 해서 문제를 풀 수 있지만, 잘 생각해보면 거스름돈에는 순서가 없으므로 중복조합으로 풀 수 있다.
  2. 중복조합의 트리를 그려보면 작은 수 일 수록 가지가 많아진다. 즉, 큰 값부터 검색을 시작하면 많은 가지를 한번에 칠 수 있다.
  3. 가장 적은 거스름돈의 갯수를 찾는 것이므로 트리를 깊이우선탐색을 하는 것이 아니라, 너비우선탐색(트리의 깊이=거스름돈 수)으로 접근하는 것이 좋다.

2. 프로젝트 배분

7개의 회사가 각각 입찰가를 제시할 때, 총 7번의 입찰에서 한 회사당 한 번의 입찰이 성사되어야 한다. 전체 입찰가의 합이 최소가 되어야 한다면, 입찰가의 총합은 얼마인가?

  1. 각 회사당 한번의 입찰을 할 수 있다. 순서가 존재하므로 순열, 중복순열로 접근 가능
  2. 한번의 입찰만 가능하므로 중복이 불가능하므로 수열로 문제를 풀이한다.

3. 병원짓기

N개의 마을이 있고, 병원을 짓는 비용이 주어진다. 마을의 연결정보가 주어질때 최소한의 비용으로 병원을 지어 모든 마을 사람들이 병원진료를 받을 수 있도록 해라. 연결된 마을이라면 병원의 진료를 받을 수 있을 때, 최소비용은 얼마인가?

  1. 연결 방법이 다양하므로 부분집합으로 접근한다.

4. 배낭 짐싸기

배낭이 수용할 수 있는 무게(W)를 초과하지 않으면서, 값이 최대가 되는 물건들을 담는다.

  1. 완전검색 : 부분집합 중 무게가 W를 초과하는 집합은 버리고, 가장 큰 가치를 가진 집합을 선택한다.

  2. 백트래킹 : 무게당 가치가 큰 순서대로 소팅한 후, 현재 가질 수 있는 가치의 기대치로 가지치기를 진행한다.

    [예] 단위 무게 당 가치의 크기로 Sorting된 리스트가 아래와 같다.

    # 가치 무게 가치/무게
    1 40 2 20
    2 30 5 6
    3 50 10 5
    4 10 5 2
    • 배낭의 최대 무게가 16일때, 가치의 기대값은? 40(2) +30(5) +45(9) = 115(16)이다.
    • 그렇다면 1번을 제외하고 짐을 쌀때의 기대값은? 30(5) +50(10) + 2(1) = 82(16)이다.
  3. Best-First-Search : 우선순위큐를 사용한다. 가장 빠른 방법이다.

5. 회의실 배정하기

회의 시작과 종료시간이 주어질 때, 가능한 많은 회의가 열리도록 회의실을 배정한다. 몇개의 회의가 열릴 수 있는가? (단, 겹치는 회의는 동시에 열릴 수 없다.)

  1. 회의를 끝나는 순서대로 sorting한다.
  2. 종료시간이 가장 빠른 회의를 선택한다.
  3. 선택된 회의와 회의시간이 겹치는 회의는 제외하여 다음 후보 회의를 구한다.
  4. 2, 3번을 반복한다.(그리디)