최단 경로와 다익스트라 알고리즘

• 최단 경로 문제: Revisited
  • 모든 정점의 쌍에 대한 최단 경로 구하기 (플로이드 알고리즘)
  • 단일 정점에서 모든 다른 정점으로의 최단경로 구하기 (다익스트라 알고리즘)

다익스트라 알고리즘 슈도 코드

1
2
3
4
5
6
7
8
9

Y = {v1};
F = ∅
while (답을 구하지 못함):
    Y에 속한 정점만 중간에 거쳐 가는 정점으로 하여
        v1에서 최단경로를 가진 정점 v를 V - Y에서 선택한다
    새로운 정점 v를 Y에 추가한다
    최단경로 상에서 v로 가는 간선을 F에 추가한다
    if(Y == V):
        답을 구했으니 return

• W[i][j]: 그래프 G의 인접행렬
• touch[i]: Y에 속한 정점들만 중간에 거치도록 하여 v1에서 vi로 가는 현재 최단경로 상의 마지막 간선을 (v, vi)라고 할 때, Y에 속한 정점 v의 인덱스
• length[i]: Y에 속한 정점들만 중간에 거치도록 하여 v1에서 vi로 가는 현재 최단 경로의 길이

파이썬으로 다익스트라 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def dijkstra (W):
    n = len(W) - 1
    F = []
    touch = [-1] * (n + 1)
    length = [-1] * (n + 1) 
    for i in range(2, n+1):
        touch[i] = 1
        length[i] = W[1][i]

    for _ in range(n - 1):
        minValue = INF
        for i in range(2, n + 1):
            if(0 <= length[i] and length[i] < minValue):
                minValue = length[i]
                vnear = i
        edge = (touch[vnear], vnear, W[touch[vnear]][vnear])
        F.append(edge)
        for i in range(2, n + 1):
            if (length[i] > length[vnear] + W[vnear][i]):
                length[i] = length[vnear] + W[vnear][i]
                touch[i] = vnear
        length[vnear] = -1
    return F

def length (F):
    total = 0
    for e in F:
        total += e[2] # (1, 5, 1) 처럼 들어오기 때문에 가중치는 index 2번에 있음
        return total

Comment and share

서로소 집합과 크루스칼 알고리즘

• 크루스칼 알고리즘

1. 해답의 집합을 공집합으로 두고, V의 서로소 집합을 생성한다. E를 비내림차순으로 정렬한다.
2. 정렬된 E 집합에서 간선 e = (i, j)를 선택하고 두 정점 i, j가 속한 집합 p, q를 찾아서 p, q가 같으면 e를 버리고 다르면 F에 e를 포함시킨 후에 p, q를 합친다.
3. |F| = n - 1이면 종료, 아니면 2단계를 반복한다.

• 사이클 탐지는 어떻게 할까?
  → 교집합이 공집합인 두 집합 A, B, 즉 서로소 집합을 만든다
  → 두 개의 원소가 같은 집합에 속하는지 판단하는 알고리즘: Union-Find 알고리즘

파이썬으로 Union-Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class DisjointSet:
    def __init__ (self, n):
        self.U = []
        for i in range(n):
            self.U.append(i)

    def equal (self, p, q):
        if (p == q): 
            return True
        else: 
            return False 

    def find (self, i):
        j = i
        while (self.U[j] != j):
            j = self.U[j]
        return j
    
    def union (self, p, q):
        if (p < q):
            self.U[q] = p
        else:
            self.U[p] = q

크루스칼 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12

def kruskal (n, E):
    F = []
    dset = DisjointSet(n)
    while (len(F) < n - 1):
        edge = E.pop(0)
        i, j = edge[0], edge[1]
        p = dset.find(i)
        q = dset.find(j)
        if (not dset.equal(p, q)):
            dset.union(p, q)
            F.append(edge)
    return F

Comment and share

탐욕법과 최소비용신장트리

• 동전 거스름돈 문제 슈도코드로 해결해보기

  1 2 3 4 5 6 7 8

  while (동전이 남아있고 문제가 미해결): 가장 가치가 높은 동전을 선택 if (동전을 더하여 거스름돈의 총액이 거슬러주어야 할 액수를 초과): 동전을 다시 집어넣는다 else: 거스름돈에 동전을 포함시킨다 if (거스름돈의 총액이 거슬러주어야 할 액수와 같다) 문제 해결 return

  이는 동전의 구성이 [500, 100, 50, 10, 5, 1]일때는 가능하지만 [500, 100, 80, 10, 5, 1]일 때엔 불가능함

• 탐욕법의 설계전략: 공집합에서 시작
  → 집합에 추가할 다음 최적의 원소를 고른다 (선택 과정)
  → 새로운 집합이 해답으로 적절한지 검사한다 (적절성 검사)
  → 새로운 집합이 문제의 해답인지 판단한다 (해답 점검)
  → 탐욕법은 상대적으로 설계하기 쉽지만 반드시 정확성을 증명해야 함

• 최소비용 신장트리 (MST:Minimum Spanning Tree) 문제
  → G = (V, E) : 모든 정점이 연결된 가중치가 있는 무방향 그래프
  → G의 부분 그래프 T = (V, F), F ⊆ E
  → 그래프 G의 모든 정점을 연결하는 트리, 간선의 개수는 n-1개
  → 이 때, 모든 신장트리 T 중에 가중치의 합이 최소가 되는 신장트리를 최소비용 신장트리라 함

• 최소비용 신장트리를 Brute-Force 방식으로 풀기
  → 모든 신장트리를 찾고 가중치의 합이 가장 작은 것을 선택
  → 간선의 개수가 n-1인 연결된 트리가 될때까지 간선을 제거

• 최소비용 신장트리를 Greedy 방식으로 풀기

1. 해답의 집합을 공집합으로 둔다: 간선 집합 E의 부분 집합 F를 공집합으로 둔다
2. E에서 최적의 간선 하나를 추출하여 F에 포함시킴
   → 최적을 선택할 때 사용되는 알고리즘에는 프림, 크루스칼 알고리즘이 있다

• 프림 알고리즘

1. Y = {V1}: Y는 정점의 집합 V의 부분 집합
2. Y에 최적의 원소 하나를 포함시킨다 (가중치가 가장 작은 정점 vnear를 선택)
   → F집합에 (nearest(vnear), vnear)를 추가
3. 해답의 집합이 최종이면 종료하고 아니면 2단계를 반복함
   → Y = V가 되면(모든 원소를 포함한다면) 종료

• 프림 알고리즘 어떻게 구현할까?
  → W[i][j]: 인접행렬 (간선의 가중치)
  → nearest[i] : Y 집합에서 vi에 가장 가까운 정점의 인덱스
  → distance[i] : vi와 nearest[i]의 정점을 연결하는 간선의 가중치

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def prim (W):
    n = len(W) - 1
    F = []
    nearest = [-1] * (n + 1)
    distance = [-1] * (n + 1)
    for i in range(2, n+1):
        nearest[i] = 1
        distance[i] = W[1][i]
    for _ in range (n - 1):
        minValue = INF
        for i in range(2, n+1):
            if (0 <= distance[i] and distance[i] < minValue):
                minValue = distance[i]
                vnear = i
        edge = (nearest[vnear], vnear, W[nearest[vnear]][vnear])
        F.append(edge)
        distance[vnear] = -1
        for i in range(2, n+1):
            if (distance[i] > W[i][vnear]):
                distance[i] = W[i][vnear]
                nearest[i] = vnear
    return F

def cost (F):
    total = 0
    for e in F:
        total += e[2]
    return total

Comment and share

최적 이진검색트리

• 주어진 n개의 키로 최적 이진검색트리를 구하는 문제
  → 주어진 n개의 키: K1, K2…, Kn
  → 각 키의 검색 확률 pi: 전체 검색횟수 중에서 Ki를 검색하는 확률
  → 각 키의 비교 횟수 ci: Ki를 검색하는데 필요한 키의 비교 횟수
  → 각 키의 평균 검색 시간: 검색 확률 * 비교 횟수 (pi * ci)
  → 전체 키의 평균 검색 시간: pi * ci의 총 합(n ~ i=1)

• Dynamic Programming 방식으로 접근하기

  1. 재귀 관계식을 찾는다
  • A: 이진검색트리를 만드는데 최적 검색비용의 행렬
  • A[i][j]: Ki에서 Kj까지 이진검색트리를 만드는데 최적 검색 비용
  • Ki … Kj를 (Ki … Kk-1)Kk(Kk+1 … Kj)로 분할하는 재귀 관계식 찾기
  2. 상향식 방법으로 해답을 구하기
  • A[i][i] = pi
  • 대각선의 상향식 계산으로 A[1][n]을 구함
  3. 최적 이진검색트리의 재귀관계식
  • 트리 k: 키 Kk가 루트 노드에 있는 최적 이진검색트리
  • 키 비교 횟수: 서브 트리의 비교 횟수에 루트에서 비교 한 번 추가
  • m ≠ k 인 Km에 대해서 트리 k에 Km을 놓기 위한 비교 한 번 추가
    → A[1][n] = minimum(A[1][k-1]+A[k+1][n] + ∑(n ∼ m=1)Pm) (단, i ≤ k ≤ j)

파이썬으로 최적 이진검색트리

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def optsearchtree (p):
    n = len(p) - 1
    A = [[-1] * (n + 1) for _ in range(n + 2)] # 최소비용
    R = [[-1] * (n + 1) for _ in range(n + 2)] # 루트노드
    for i in range(1, n + 1):
        A[i][i - 1] = 0
        A[i][i] = p[i]
        R[i][i - 1] = 0
        R[i][i] = i
    A[n + 1][n] = 0 # 주대각선은 초기화
    R[n + 1][n] = 0 
    for diagonal in range(1, n): # 대각선을 거치며 최소값 구하기
        for i in range(1, n - diagonal + 1):
            j = i + diagonal 
            # j값은 주 대각선 값(diagonal)만큼 우측에 있어야 하므로 더해준다
            A[i][j], R[i][j] = minimum(A, p, i, j)
    return A, R

# minimum 함수는 연쇄 행렬 곱셈에서 썼던것과 거의 동일
def minimum (A, p, i, j):
    minVal = INF
    minK = 0
    for k in range(i, j + 1):
        value = A[i][k - 1] + A[k + 1][j]
        for m in range(i, j + 1):
            value += p[m]
        if (minVal > value):
            minVal = value
            minK = k
    return minVal, minK

참고: 연쇄 행렬 곱셈 알고리즘

최적 이진검색트리의 노드 순서 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def tree (R, i, j):
    k = R[i][j]
    if (k == 0):
        return None
    else:
        node = BSTNode(keys[k])
        node.left = tree(R, i, k - 1)
        node.right = tree(R, k + 1, j)
        return node

class BSTNode:
    def __init__ (self, key):
        self.key = key
        self.left = None
        self.right = None

def preorder (node):
    if (node is None): return
    else: 
        print(node.key, end = ' ')
        preorder(node.left)
        preorder(node.right)

def inorder (node) :
    if (node is None): return
    else:
        inorder(node.left)
        print(node.key, end = ' ')
        inorder(node.right)

자바스크립트로 최적 이진검색트리의 노드 순서 구하기(수정 중)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

const optsearchtree = p => {
    let n = p.length - 1;
    let arr = Array.from(Array(n+2), () => Array(n+1).fill(-1))
    let arr2 = [...arr]
    for (let i = 1; i < n+1; i++){
        arr[i][i-1] = 0
        arr[i][i] = p[i]
        arr2[i][i-1] = 0
        arr2[i][i] = i
    }
    arr[n+1][n] = 0
    arr2[n+1][n] = 0
    for(let diagonal = 1; diagonal < n; diagonal++) {
        for (let i = 1; i < n - diagonal + 1; i++){
            let j = i + diagonal;
            arr[i][j] = minimum(arr, p, i, j).minVal;
            arr2[i][j] = minimum(arr2, p, i, j).minK;
        }
        console.log(arr)
    }
    return { arr: arr, arr2: arr2 }
}

const minimum = (arr, p, i, j) => {
    let minVal = Infinity;
    let minK = 0
    for (let k = i; k < j+1; k++){
        let value = arr[i][k-1] + arr[k+1][j]
        for (let m = i; m < j+1; m++){
            value += p[m]
        }

        if (minVal > value) {
            minVal = value
            minK = k
        }        
    }
    return { minVal: minVal, minK: minK }
}

Comment and share

연쇄 행렬 곱셈

연쇄 행렬 곱셈은 주어진 n개의 연쇄 행렬을 곱하는 최적의 순서를 구하는 문제

• 행렬 곱셈은 결합 법칙이 성립하지만 곱셈 순서에 따라 각 원소의 곱셈 횟수가 달라짐 → 이 곱셈 횟수가 가장 작아지는 최적의 순서를 구하기
• 2 x 3 행렬과 3 x 4 행렬을 곱하면 2 x 4 행렬이 됨
  → i x k 행렬과 k x j 행렬을 곱하면 i x j 행렬이 되며
  → 원소 곱셈의 횟수는 i * k * j가 된다

• Brute-force 방식으로 접근하기
  • 모든 경우의 수(카탈랑 수)를 계산하여 최적의 순서를 선택
  • 카탈랑 수는 결국 지수함수이므로 너무 오래걸림
• Dynamic Programming 방식으로 접근하기
  1. 재귀 관계식을 찾는다
  • M: 연쇄 행렬을 곱하는데 필요한 최소 횟수 행렬
  • M[i][j]: Ai에서 Aj까지 행렬을 곱하는데 필요한 최소 횟수
  • Ai … Aj 행렬을 (Ai … Ak)(Ak+1 … Aj)로 분할하는 재귀 관계식 찾기
  2. 상향식 방법으로 해답을 구하기
  • M[i][i] = 0 (대각선에 위치하는 원소를 0으로 초기화)
  • M[1][n]을 상향식으로 계산 (대각선 1번, 대각선 2번 … 대각선 n-1번)
  • n개의 행렬을 두 개의 최적 부분행렬의 곱으로 분할
  • M[i][j] = minimum(M[i][k] + M[k+1][j] + di-1dkdj) // 단, i ≤ k ≤ j-1

파이썬으로 연쇄 행렬 곱셈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def minmult (d):
    n = len(d) - 1
    M = [[-1] * (n + 1) for _ in range(n+1)]
    P = [[-1] * (n + 1) for _ in range(n+1)]
    for i in range(1, n + 1):
        M[i][i] = 0
    for diagonal in range(1, n):
        for i in range(1, n - diagonal + 1):
            j = i + diagonal
            M[i][j], P[i][j] = minimum(M, d, i, j)
    return M, P 

def minimum (M, d, i, j):
    minVal = INF
    minK = 0
    for k in range(i, j):
        value = M[i][k] + M[k + 1][j]
        value += d[i -1] * d[k] * d[j]
        if (minVal > value):
            minVal = value
            minK = k
    return minVal, minK

def order(P, i, j):
    if (i == j):
        print('A%d'%(i), end = '')
    else:
        k = P[i][j]
        print('(', end = '')
        order(P, j, k)
        order(P, k + 1, j)
        print(')', end = '')

자바스크립트로 연쇄 행렬 곱셈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

const minmult = d => {
    let n = d.length -1
    let arr = Array.from(Array(n+1), () => Array(n+1).fill(-1))
    let arr2 = [...arr];
    for (let i = 1; i < n+1; i++){
        arr[i][i] = 0;
    }

    for (let diagonal = 1; diagonal < n; diagonal++){
        for (let i = 1; i < n - diagonal + 1; i++){
            j = i + diagonal;
            arr[i][j] = minimum(arr, d, i, j).minVal; 
            arr2[i][j] = minimum(arr, d, i, j).minK; 
        }
    }
    return { result : arr, optimal: arr2 };
}

const minimum = (arr, d, i, j) => {
    let minVal = Infinity;
    for (let k = i; k < j; k++) {
        let value = arr[i][k] + arr[k+1][j] + d[i - 1] * d[k] * d[j]
        if (minVal > value){
            minVal = value;
            minK = k
        }
    }
    return {minVal : minVal, minK : minK}
}

const order = (arr2, i, j) => {
    if (i === j) str += `A${i}`
    else {
        let k = arr2[i][j]
        str += '('
        order(arr2, i, k)
        order(arr2, k+1, j)
        str += ')'
    }
}
/*
예시) 
let d = [5, 2, 3, 4, 6, 7, 8];
let { result, optimal } = minmult(d)
order(optimal, 1, d.length - 1)
console.log(result)
console.log(str) -> `(A1(A2(A3(A4(A5A6)))))`
*/

Comment and share

최단경로와 플로이드 알고리즘

• 최단 경로 문제

  • 주어진 그래프에서 모든 정점의 쌍에 대한 최단 경로를 구하기

  • G = (V, E)일 때, G는 Graph, V는 Vertex set, E는 Edge set

  • G는 방향성, 가중치 그래프로, V1 -6→ V3 와 같은 것을 표로 표현

  • 최단 경로는 단순 경로: 같은 정점을 두 번 거치지 않음

    
    figure 01) 그래프로 표현되는 경우

• 최단 경로 문제의 이해

  • Brute-force로 해결하기
    • 각 정점들에서 다른 정점으로 가는 모든 경로를 구하고
    • 그 경로들 중에서 가장 짧은 경로를 찾는 방법
    • 효율성 분석: 모든 정점간 간선이 존재하면 O(n!)만큼 복잡해진다
  • 최단 경로 문제는 최적화 문제(optimization problem)
    • 최적화 문제는 하나 이상의 해답 후보가 있을 수 있음
    • 그 중에 가장 최적의 값을 가진 해답을 찾는 문제
  • Dynamic programming으로 해결하기
    1. 재귀 관계식을 찾는다
    • D: 각 정점의 쌍이 가지는 최단 경로의 길이를 나타내는 행렬
    • D[i][j]: Vi에서 Vj로 가는 최단 경로의 길이
    • 인접 행렬 W에서 최단 경로의 행렬 D와의 재귀 관계식을 구해야 함
    2. 상향식 방법으로 해답을 구한다
    • D^0^ = W로 초기화, 최종 목표는 D^n^ = D (D^0^, D^1^,…, D^n^)
    3. 행렬의 이해
    • D^k^ : k개의 중간 정점을 지나는 최단 경로 길이의 행렬
    • D^k^[i][j] : vi에서 vj로 k개의 중간 정점을 지나는 최단 경로 길이
    • D^0^ : 다른 어떤 정점도 지나지 않는 최단 경로의 길이 (=W)
    • D^n^ : 다른 모든 정점을 지날 수 있는 최단 경로의 길이 (=D)
    4. 재귀 관계식 구하기
    • D^0^ = W, D^k^는 D^k-1^로부터 구함 (1 ≤ k ≤ n)
    • D^k-1^[i][j]: vi에서 vj로 k-1개의 중간 정점을 지남
    • D^k^[i][j]의 경우
      → 하나의 정점을 더 지나도 최단경로가 없는 경우
      D^k^[i][j] = D^k-1^[i][j]
      → 하나의 정점을 더 지나면 최단경로가 되는 경우
      D^k^[i][j] = D^k-1^[i][k] + D^k-1^[k][j]
      (임의의 경로 = v가 갖는 열 내 k 번째 가중치 + 해당 k번째 v가 갖는 가중치)
    5. 최단 경로의 재귀 관계식
       D^k^[i][j] = min(D^k-1^[i][j], D^k-1^[i][k] + D^k-1^[k][j])

파이썬으로 플로이드 알고리즘

1
2
3
4
5
6
7
8

def floyd (W):
    D = W
    n = len(W)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D

자바스크립트로 플로이드 알고리즘

1
2
3
4
5
6
7
8
9

const floyd = W => {
    let arr = [...W];
    let n = W.length;
    for (let k = 0; k < n; k++) 
        for (let i = 0; i < n; i++)  
            for (let j = 0; j < n; j++) 
                arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j])
    return arr
}

• 최단 길이는 구했으나, 최단 경로는?
  • 최단 경로를 구하기 위해서는 과정을 기록해야 함
  • P[i][j]: vi에서 vj로 가는 최단 경로가 거쳐야 하는 새로운 정점
    • vi에서 vj로 가는 최단 경로 중간에 놓여있는 정점이 최소한 하나 있다면 그 놓여있는 정점 중에서 가장 큰 인덱스
    • 최단 경로의 중간에 놓여있는 정점이 없는 경우에는 -1
  • P[i][j] 값이 -1이라면 간선이 최단경로
  • P[i][j] = k 라면 탐색해서 가장 길이가 짧은 값의 index를 탐색해야 함

파이썬으로 최단 경로 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def floyd (W):
    n = len(W)
    D = W
    P = [[-1] * n for _ in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (D[i][j] > D[i][k] + D[k][j]):
                    D[i][j] = D[i][k] + D[k][j]
                    P[i][j] = k
    return D, P

def path (P, u, v):
    if(P[u][v] != -1):
        path(P, u, P[u][v])
        print('v%d' %(P[u][v]), end = '-> ')
        path(P, P[u][v], v)

D, P = floyd2(W)
for i in range(len(D)):
    print(D[i])
for i in range(len(P)):
    print(P[i])

자바스크립트로 최단 경로 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

const floydWarshall2 = nodes => {
    let n = nodes.length;
    let arr = [...nodes];
    let route = Array.from(Array(n), () => Array(n).fill(-1));
    for (let k = 0; k < n; k++) 
        for (let i = 0; i < n; i++)  
            for (let j = 0; j < n; j++) {
                if (arr[i][j] > arr[i][k] + arr[k][j]) {
                 arr[i][j] = arr[i][k] + arr[k][j];
                 route[i][j] = k;
                } 
            }
    return { arr: arr, route: route };
}


let { arr, route } = floydWarshall2(nodes)

let str = `v${u}` // u값을 미리 정의한다면 이렇게 사용할 수 있다
const path = (route, u, v) => {
    if (route[u][v] !== -1) {
        path(route, u, route[u][v])
        str += ` → v${route[u][v]}`
        path(route, route[u][v], v);        
    } 
    return str + ` → v${v}`
}

from(itarable obj, map function) 함수를 사용해야 함 fill 함수를 사용하게 될 경우 배열 내 채워지는 모든 배열들의 주소값이 동일한 주소로 입력되기 때문

Comment and share

동적 계획과 이항 계수

수식 깨진 것들은 자체 검색으로 보완할 것

• 동적계획법(Dynamic Programming): 문제를 더 작은 문제로 분할하되 상향식으로 문제를 해결

• 메모이제이션(Memoization): 가장 작은 입력 사례의 해답을 테이블에 저장하고 필요할 때 꺼내 쓴다

• 동적계획법으로 문제 풀기

  1. 문제를 해결할 수 있는 재귀 관계식(점화식)을 구한다
  2. 가장 작은 입력사례로부터 상향식 방법으로 문제를 해결한다

• 분할 정복법 vs 동적 계획법

  • 문제를 작은 사례로 분할하여 해결한다는 점에서 동일
  • Top-Down vs Bottom-Up

• 이항 계수

  • $\binom{n}{k} = \frac{n!}{k!(n-k)!}$, for $0 \le k \le n$
  • $\ n!, k!$의 값은 매우 커서 계산이 어렵다
  • 이항 계수의 재귀적 정의: 분할 정복
  • $\binom{n}{k} = \begin{cases}\binom{n-1}{k-1} + \binom{n-1}{k-1}&0<k<n\{1}&k=0||k=n\end{cases}$

파이썬으로 이항 계수의 재귀적 정의

1
2
3
4
5
6
7
8
9
10

def bin (n, k):
    if (k == 0 or n == k):
        return 1
    else:
        return bin(n - 1, k - 1) + bin(n -1, k)
# 함수 결과를 n = 10까지 출력
for n in range(10):
    for k in range(n + 1):
        print(bin(n, k), end = " ")
    print()

자바스크립트

1
2
3

function bin(n, k) {
    return (k == 0 || k == n) ? 1 : bin(n - 1, k - 1) + bin(n - 1, k);
}

$0 \le k \le n$에 의해 $k$는 $n$보다 큰 값일 수 없다

• 이 방식은 중복 호출이 생김 → 반복적 방법이 요구됨
• 이항 계수의 성질: 파스칼의 삼각형
• 이항 계수 구하기
  1. 재귀 관계식을 찾는다
     $$B[i][j] = \begin{cases}B[i-1][j-1]+B[i-1][j]&0<j<i\1&j=0orj=i\end{cases}$$
  2. 상향식 방법으로 해답을 구한다
     • 파스칼의 삼각형이 가진 특성을 이용한다

파이썬으로 파스칼의 삼각형 구하기

1
2
3
4
5
6
7
8
9
10

def bin2 (n,k):
    B = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if (j == 0 or j == i):
                B[i][j] = 1
            else:
                B[i][j] = B[i - 1][j - 1] + B[i - 1][j]
    return B[n][k]
# 출력은 bin(n,k)와 동일

자바스크립트로 파스칼의 삼각형 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function bin2(n) {
    let result = []; // 빈 배열을 선언
    for (let row = 1; row <= n; row++) {
        // 행 수 만큼 for 루프
        let arr = [];
        // 추가할 새 배열을 선언 (루프 돌면서 초기화됨)
        for (let col = 0; col < row; col++) {
            if (col === 0 || col === row - 1) 
                // 파스칼의 삼각형에서 처음과 맨 마지막 숫자는 1로 채운다
                arr.push(1);
             else 
                // 안쪽 숫자는 이미 result 배열에 추가된 이전 열의 연속된 숫자를 더함
                arr.push((result[row-2][col-1] + result[row-2][col]));
        }
        result.push(arr);
    }
    return result
}

• 이항 계수의 시간 복잡도와 성능 개선
  • $k$가 $n/2$보다 클 경우, 나머지 절반 삼각형은 중복값
  • 1차원 배열만으로도 구현이 가능

파이썬으로 파스칼의 삼각형 성능개선

1
2
3
4
5
6
7
8
9
10
11
12

def bin3 (n,k):
    if (k > n // 2):
        k = n - k
    B = [0] * (k + 1)
    B[0] = 1
    for i in range(1, n + 1):
        j = min(i, k)
        while (j > 0):
            B[j] = B[j] + B[j - 1]
            j -= 1
    return B[k]
# 출력은 bin(n,k)와 동일

자바스크립트로 파스칼의 삼각형 성능개선

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function bin3(n,k) {
    if(n === 1) return [1] // n이 1일때엔 [1]을 리턴하도록 함
    // 파스칼의 삼각형은 절반 이후로는 전반 절반과 같은 값이다
    if(k > Math.floor(n/2)) k = n - k
    // 배열을 k+1 길이만큼 생성하고 0으로 채운다
    let arr = Array(k+1).fill(0)
    // 첫번째 값을 1로 설정한다
    arr[0] = 1;
    for (let i = 1; i < n + 1; i++){
        let j = Math.min(i, k)
        while (j > 0) {
            arr[j] = arr[j] + arr[j-1] // 이전값과 더한 값
            j -= 1 // j를 줄여나간다
        }
    }
    // 파스칼 삼각형 열이 홀수라면 중간 숫자는 중복되는 숫자이므로 slice함
    return n % 2 !== 0 
        ? [...arr, ...arr.slice(0,-1).reverse()] 
        : [...arr, ...arr.reverse()]
}

Comment and share

큰 정수의 계산

• 특정 컴퓨터/언어가 표현할 수 없는 큰 정수의 산술 연산은 어떻게 할까?
• int값은 대부분 32bit (부호값 1bit + 31bit) 이므로 -2^32^ ~ 2^31^-1까지만 표현 가능
• 가정: 10진수 체계에서의 덧셈과 곱셈
• 10진수를 소프트웨어적으로 표현하는 법 : 리스트를 이용하여 각 자리수를 하나의 원소로 저장 (예: 567,832: S = [2,3,8,7,6,5])
  :point_right: 참고 자바스크립트가 숫자를 다루는 법
  • 자바스크립트에는 number라는 하나의 숫자형만 존재하며 이는 64비트 2진 부동소수점 타입
  • 1개의 부호비트와 11비트의 지수, 53비트의 유효 숫자로 구성됨
  • Number.MAX_SAFE_INTEGER = 9007199254740991
  • 예로 숫자 9000000000000000000 는 ["+", 8650752, 7098594, 31974]로 표현된다

큰 정수의 덧셈

• n개의 자릿수 각각을 더하면서 올림수(carry)를 고려

파이썬으로 정수 더하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def ladd (u, v):
    n = len(u) if (len(u) > len(v)) else len(v) 
    # 파이썬에서 타 언어의 삼항연산자 처럼 쓰는 법
    # (u.length > v.length) ? n = u.length : n = v.length; 같은 것
    result = []
    carry = 0
    for k in range(n):
        i = u[k] if(k < len(u)) else 0
        j = v[k] if(k < len(v)) else 0
        value = i + j + carry
        carry = value // 10
        result.append(value % 10)
    if (carry > 0):
        result.append(carry)
    return result

자바스크립트로 정수 더하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

const add = (a, b) => {
    let n = 0;
    (a.length > b.length) ? n = a.length : n = b.length;
    let result = [];
    let carry  = 0;
    for (let k = 0; k < n; k++) {
        let i = 0, j = 0
        
        if (k < a.length) i = a[k]
        else              i = 0;
        if (k < b.length) j = b[k]
        else              j = 0;

        let value = i + j + carry;
        carry = Math.floor(value / 10)
        result.push(value % 10)
    }
    if (carry > 0) result.push(carry);
    return Number(result.reverse().join(''))
}

큰 정수의 곱셈

• Brute-Force 방법 : O(n^2^)
• Divide-and-Conquer
  • u (n자리) = *x * 10^m^* (n/2자리) + y (n/2자리)
  • uv = (x * 10^m^** + y)(**w * 10^m^ + z)
    → uv = xw * 10^2m^ + (xy + yw) * 10^m^ + yz

파이썬으로 정수 곱하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

def prod(u, v):
    n = len(u) if (len(u) > len(v)) else len(v) 
    if (len(u) == 0 or len(v) == 0):
        return [0]
    elif (n <= threshold):
        return lmult(u, v)
    else:
        m = n // 2
        # divide
        x = div(u, m); y = rem(u, m)
        w = div(v, m); z = rem(v, m)
        # conquer
        p1 = prod(x, w) # xw
        p2 = ladd(prod(x, z), prod(w, y)) # (xy + yw)
        p3 = prod(y, z) # yz
        return ladd(ladd(exp(p1, 2*m), exp(p2, m)), p3)

def exp(u, m):
    if(u == [0]):
        return [0]
    else:
        return ([0] * m) + u
         # 배열의 합은 두 배열을 단순히 합하는 것
         # ex) [0, 0, 0] + [5, 6, 7] = [0, 0, 0, 5, 6, 7]

def div(u, m):
    if(len(u) < m):
        u.append(0)
    return u[m : len(u)]

def rem(u, m):
    if(len(u) < m):
        u.append(0)
    return u[0 : m]

def lmult (u, v):
    i = u[0] if (0 < len(u)) else 0
    j = v[0] if (0 < len(v)) else 0
    value = i * j
    carry = value // 10
    result = []
    result.append(value % 10)
    if(carry > 0):
        result.append(carry)
    return result

곱셈 개선

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

def prod2(u, v):
    n = len(u) if (len(u) > len(v)) else len(v) 
    if (len(u) == 0 or len(v) == 0):
        return [0]
    elif (n <= threshold):
        return lmult(u, v)
    else:
        m = n // 2
    
        x = div(u, m); y = rem(u, m)
        w = div(v, m); z = rem(v, m)

        # 이 부분이 바뀜
        r = prod2(ladd(x, y), ladd(w, z))
        
        p1 = prod2(x, w) # xw
        p3 = prod2(y, z) # yz

         # 이 부분이 바뀜
        p2 = lsub(r, ladd(p1, p3)) # (xy + yw)
        return ladd(ladd(exp(p1, 2*m), exp(p2, m)), p3)

def lsub (u, v):
    n = len(u) if (len(u) > len(v)) else len(v)
    result = []
    borrow = 0
    for k in range(n):
        i = u[k] if (k < len(u)) else 0
        j = v[k] if (k < len(v)) else 0
        value = i - j + borrow
        if (value < 0):
            value += 10
            borrow = -1
        else:
            borrow = 0
        result.apeend(value % 10)
    if(borrow < 0):
        print("음의 정수는 처리할 수 없음")
    return result

# 나머지 함수는 동일

Comment and share

슈트라센 행렬 곱셈

• 단순 참고용으로만 공부함 (행렬 계산은 어려워…)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

  def strassen (A, B): n = len(A) if (n <= threshold): return matrixmult(A,B) A11, A12, A21, A22 = divide(A) B11, B12, B21, B22 = divide(B) M1 = strassen(madd(A11, A22), madd(B11, B22)) M2 = strassen(madd(A21, A22), B11) M3 = strassen(A11, msub(B12, B22)) M4 = strassen(A22, madd(B21, B11)) M5 = strassen(madd(A11, A12), B22) M6 = strassen(madd(A21, A11), madd(B11, B12)) M7 = strassen(madd(A12, A22), madd(B21, B22)) return conquer(M1, M2, M3, M4, M5, M6, M7) def divide (A): n = len(A) m = n // 2 A11 = [[0] * m for _ in range(m)] A12 = [[0] * m for _ in range(m)] A21 = [[0] * m for _ in range(m)] A22 = [[0] * m for _ in range(m)] for i in range(m): for j in range(m): A11[i][j] = A[i][j] A12[i][j] = A[i][j + m] A21[i][j] = A[i + m][j] A22[i][j] = A[i + m][j + m] return A11, A12, A21, A22 def conquer(M1, M2, M3, M4, M5, M6, M7): C11 = madd(msub(madd(M1, M4), M5), M7) C12 = madd(M3, M5) C21 = madd(M2, M4) C22 = madd(msub((madd(M1, M3), M2), M6) m = len(C11) n = 2 * m C = [[0] * n for _ in range(n)] for i in range(m): for j in range(m): C[i][j] = C11[i][j] C[i][j + m] = C12[i][j] C[i + m][j] = C21[i][j] C[i + m][j + m] = C22[i][j] return C def madd(A, B): n = len(A) C = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): C[i][j] = A[i][j] + B[i][j] return C def msub (A, B): n = len(A) C = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): C[i][j] = A[i][j] - B[i][j] return C def matrixmult (A, B): n = len(A) C = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): for k in range(n): C[i][j] += A[i][k] * B[k][j] return C

  자바스크립트에서 행렬계산 (참고용)
• map과 reduce를 사용하여 iterable 객체를 돌며 행렬을 계산
• 단순 덧셈은 하나의 행렬을 돌며 두번째 인수로 인덱스를 받아 double for문 처럼 사용

  1 2 3 4 5 6 7 8 9 10 11 12 13

  function sumMatrix (arr1, arr2) { return arr1.map((arr, i) => arr.map((v, j) => v + arr2[i][j])) } function multiplyMatrix(arr1, arr2) { return arr1.map( row => row.map( // x = arr[0] 값, y = index 값 (_, i) => row.reduce( // reduce는 (acc, cur, index) (sum, cell, j) => sum + cell * arr2[j][i], 0))) }

Comment and share

퀵정렬

• 내부정렬 : 추가적인 리스트를 사용하지 않는 정렬(Quick Sort Algorithm: Hoare, 1962)
• 퀵정렬

  Divide: 기준 원소를 정해서 좌우로 분할
  Conquer: 왼쪽/오른쪽 리스트를 각각 재귀적으로 정렬
  Obtain: 정렬된 리스트를 리턴

파이썬으로 퀵정렬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def quicksort(S, low, high):
    if (high > low):
        pivotpoint = partition(S, low, high)
        quicksort(S, low, pivotpoint - 1)
        quicksort(S, pivotpoint + 1 , high)

def partition(S, low, high):
    pivotitem = S[low]
    j = low
    for i in range(low + 1, high + 1):
        if(S[i] < pivotitem):
            j += 1;
            S[i], S[j] = S[j], S[i] # swap 2 items
    pivotpoint = j
    S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap 2 items
    return pivotpoint

• 기준원소(pivotpoint)를 어떻게 정할까? : 편의상 첫 원소를 기준 원소로 정한다
• 두 개의 인덱스(i, j)를 이용해서 비교하고 교환한다

자바스크립트로 퀵정렬 (기준 원소가 배열의 맨마지막 요소일 때)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function quickSort (arr, start, end) {
    if (start >= end) return;

    let index = partition(arr, start, end);
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end)

}

function partition (arr, start = 0, end = arr.length - 1) {
    let pivotIndex = start;
    let pivotValue = arr[end];
    for(let i = start; i < end; i++){
        if(arr[i] < pivotValue) {
            swap(arr, i, pivotIndex);
            pivotIndex++
        }
    }
    swap(arr, pivotIndex, end);
    return pivotIndex;
}

function swap (arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

참고영상 : Coding Challenge #143​: Quicksort Visualization

퀵정렬(분할 교환 정렬)

파이썬으로 퀵정렬 할 때 다른 방법으로 파티션 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def partition2 (S, low, high):
    pivotitem = S[low]
    i = low + 1
    j = high
    while (i <= j):
        while (S[i] < pivotitem):
            i += 1
        while (S[j] > pivotitem):
            j -= 1
        if (i < j):
            S[i], S[j] = S[j], S[i] # swap 2 items
        pivotpoint = j
        S[low], s[pivotpoint] = S[pivotpoint], S[low] # swap 2 items 
        return pivotpoint

자바스크립트로 퀵정렬 할 때 다른 방법으로 파티션 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function partition2 (array, start, end) {
    // 맨 마지막이나 맨 처음으로 설정했던 pivot값을 배열의 중간값으로 설정
	const pivotValue = array[ Math.floor((start + end) / 2) ];

    // 양 끝의 인덱스를 하나씩 늘리거나 하나씩 줄이면서
    // 피봇값보다 작은 값인 start와 피봇값보다 큰 값인end값을 구함
	while (start <= end) { 
		while (array[start] < pivotValue) start = start + 1;
		while (array[end] > pivotValue) end = end - 1;
        
        // start값이 end값보다 크단 뜻은 배열을 한번 다 돌았다는 뜻임
		if (start <= end) { 
            // 이 구문을 들어온다는 뜻은 배열을 돌면서 pivotValue보다 
            // 큰 값(array[start]값)과 작은 값(array[end]값)의 두 값을 교체해줌
			swap(array, start, end);
			start = start + 1;
			end = end - 1;
		}
	}
    // 이 과정이 끝나면 pivotValue보다 작은 값은 왼쪽에, 큰 값은 오른쪽으로 정렬되었단 뜻이므로 
    // 해당 인덱스 값을 리턴하여 다시 배열을 둘로 쪼갬
	return start; 
}

Comment and share