Update misc codes.

likejazz · likejazz · commit ca7bd3a8d3a7 · 2020-07-21T14:52:18.000+09:00
diff --git a/README.md b/README.md
@@ -108,3 +108,12 @@
 | 93(문제 5) | 뉴스 클러스터링 | ★★ | 부록 B. 카카오 공채 문제 풀이 | [5.py](appendix-B/5.py) |
 | 94(문제 6) | 프렌즈4블록 | ★★★ | 부록 B. 카카오 공채 문제 풀이 | [6.py](appendix-B/6.py) |
 | 95(문제 7) | 추석 트래픽 | ★★★ | 부록 B. 카카오 공채 문제 풀이 | [7.py](appendix-B/7.py) |
+
+## 기타 코드
+- 11장 [생일 문제](miscellaneous/11-birthday.py)
+- 12장 [그래프 순회](miscellaneous/12-graph-traversals.py)
+- 14장 [트리 순회](miscellaneous/14-tree-traversals.py)
+- 17장 [버블 정렬](miscellaneous/17-bubble-sort.py)
+- 17장 [퀵 정렬](miscellaneous/17-quick-sort.py)
+- 21장 [분할 가능 배낭 문제](miscellaneous/21-fractional-knapsack.py)
+- 23장 [0-1 배낭 문제](miscellaneous/23-zero-one-knapsack.py)
diff --git a/miscellaneous/11-birthday.py b/miscellaneous/11-birthday.py
@@ -0,0 +1,18 @@
+import random
+
+TRIALS = 100000     # 10만 번 실험
+same_birthdays = 0  # 생일이 같은 실험의 수
+
+# 10만 번 실험 진행
+for _ in range(TRIALS):
+    birthdays = []
+    # 23명이 모였을 때, 생일이 같을 경우 same_birthdays +=1
+    for i in range(23):
+        birthday = random.randint(1, 365)
+        if birthday in birthdays:
+            same_birthdays += 1
+            break
+        birthdays.append(birthday)
+
+# 전체 10만 번 실험 중 생일이 같은 실험의 확률
+print(f'{same_birthdays / TRIALS * 100}%')
diff --git a/miscellaneous/12-graph-traversals.py b/miscellaneous/12-graph-traversals.py
@@ -0,0 +1,46 @@
+graph = {
+    1: [2, 3, 4],
+    2: [5],
+    3: [5],
+    4: [],
+    5: [6, 7],
+    6: [],
+    7: [3],
+}
+
+
+def recursive_dfs(v, discovered=[]):
+    discovered.append(v)
+    for w in graph[v]:
+        if w not in discovered:
+            discovered = recursive_dfs(w, discovered)
+    return discovered
+
+
+def iterative_dfs(start_v):
+    discovered = []
+    stack = [start_v]
+    while stack:
+        v = stack.pop()
+        if v not in discovered:
+            discovered.append(v)
+            for w in graph[v]:
+                stack.append(w)
+    return discovered
+
+
+def iterative_bfs(start_v):
+    discovered = [start_v]
+    queue = [start_v]
+    while queue:
+        v = queue.pop(0)
+        for w in graph[v]:
+            if w not in discovered:
+                discovered.append(w)
+                queue.append(w)
+    return discovered
+
+
+print(f'recursive dfs: {recursive_dfs(1)}')
+print(f'iterative dfs: {iterative_dfs(1)}')
+print(f'iterative bfs: {iterative_bfs(1)}')
diff --git a/miscellaneous/14-tree-traversals.py b/miscellaneous/14-tree-traversals.py
@@ -0,0 +1,46 @@
+class Node:
+    def __init__(self, val, left=None, right=None):
+        self.val = val
+        self.left = left
+        self.right = right
+
+
+root = Node('F',
+            Node('B',
+                 Node('A'),
+                 Node('D',
+                      Node('C'), Node('E'))),
+            Node('G',
+                 None,
+                 Node('I', Node('H'))
+                 )
+            )
+
+
+def preorder(node):
+    if node is None:
+        return
+    print(node.val)
+    preorder(node.left)
+    preorder(node.right)
+
+
+def inorder(node):
+    if node is None:
+        return
+    inorder(node.left)
+    print(node.val)
+    inorder(node.right)
+
+
+def postorder(node):
+    if node is None:
+        return
+    postorder(node.left)
+    postorder(node.right)
+    print(node.val)
+
+
+preorder(root)
+inorder(root)
+postorder(root)
diff --git a/miscellaneous/17-bubble-sort.py b/miscellaneous/17-bubble-sort.py
@@ -0,0 +1,10 @@
+def bubblesort(A):
+    for i in range(1, len(A)):
+        for j in range(0, len(A) - 1):
+            if A[j] > A[j + 1]:
+                A[j], A[j + 1] = A[j + 1], A[j]
+
+
+A = [38, 27, 43, 3, 9, 82, 10]
+bubblesort(A)
+print(A)
diff --git a/miscellaneous/17-quick-sort.py b/miscellaneous/17-quick-sort.py
@@ -0,0 +1,20 @@
+def quicksort(A, lo, hi):
+    def partition(lo, hi):
+        pivot = A[hi]
+        left = lo
+        for right in range(lo, hi):
+            if A[right] < pivot:
+                A[left], A[right] = A[right], A[left]
+                left += 1
+        A[left], A[hi] = A[hi], A[left]
+        return left
+
+    if lo < hi:
+        pivot = partition(lo, hi)
+        quicksort(A, lo, pivot - 1)
+        quicksort(A, pivot + 1, hi)
+
+
+A = [38, 27, 43, 3, 9, 82, 10]
+quicksort(A, 0, len(A) - 1)
+print(A)
diff --git a/miscellaneous/21-fractional-knapsack.py b/miscellaneous/21-fractional-knapsack.py
@@ -0,0 +1,33 @@
+cargo = [
+    (4, 12),
+    (2, 1),
+    (10, 4),
+    (1, 1),
+    (2, 2),
+]
+
+
+def fractional_knapsack(cargo):
+    capacity = 15
+    pack = []
+    # 단가 계산 역순 정렬
+    for c in cargo:
+        pack.append((c[0] / c[1], c[0], c[1]))
+    pack.sort(reverse=True)
+
+    # 단가 순 그리디계산
+    total_value: float = 0
+    for p in pack:
+        if capacity - p[2] >= 0:
+            capacity -= p[2]
+            total_value += p[1]
+        else:
+            fraction = capacity / p[2]
+            total_value += p[1] * fraction
+            break
+
+    return total_value
+
+
+r = fractional_knapsack(cargo)
+print(r)
diff --git a/miscellaneous/23-zero-one-knapsack.py b/miscellaneous/23-zero-one-knapsack.py
@@ -0,0 +1,31 @@
+cargo = [
+    (4, 12),
+    (2, 1),
+    (10, 4),
+    (1, 1),
+    (2, 2),
+]
+
+
+def zero_one_knapsack(cargo):
+    capacity = 15
+    pack = []
+
+    for i in range(len(cargo) + 1):
+        pack.append([])
+        for c in range(capacity + 1):
+            if i == 0 or c == 0:
+                pack[i].append(0)
+            elif cargo[i - 1][1] <= c:
+                pack[i].append(
+                    max(
+                        cargo[i - 1][0] + pack[i - 1][c - cargo[i - 1][1]],
+                        pack[i - 1][c]
+                    ))
+            else:
+                pack[i].append(pack[i - 1][c])
+    return pack[-1][-1]
+
+
+r = zero_one_knapsack(cargo)
+print(r)
