BELFRY
Week-9: 기타 문제
DSA-알고리즘 스터디
Feb 16, 2022

배낭 문제

knapsack.py

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

from typing import NamedTuple, List


class Item(NamedTuple):
    name:str
    weight:int
    value:float


def knapsack(items:List[Item], max_capacity:int) -> List[Item]:
    table:List[List[float]] = [[0.0 for _ in range(max_capacity + 1)] for _ in range(len(items) + 1)]
    for i, item in enumerate(items):
        for capacity in range(1, max_capacity + 1):
            previous_items_value:float = table[i][capacity]
            # 물건이 배낭 용량에 맞는 경우
            if capacity >= item.weight: 
                value_freeing_weight_for_item:float = table[i][capacity - item.weight]
                # 더 가치 있는 물건을 넣는다
                table[i + 1][capacity] = max(value_freeing_weight_for_item + item.value, previous_items_value)
            # 물건이 배낭 용량에 맞지 않는 경우
            else:
                table[i + 1][capacity] = previous_items_value
    solution:List[Item] = []
    capacity = max_capacity
    for i in range(len(items), 0, -1):
        if table[i - 1][capacity] != table[i][capacity]:
            solution.append(items[i - 1])
            capacity -= items[i - 1].weight
    return solution


if __name__ == "__main__":
    items:List[Item] = [Item("TV", 50, 500),
                        Item("촛대", 2, 300),
                        Item("오디오", 35, 400),
                        Item("노트북", 3, 1000),
                        Item("식량", 15, 50),
                        Item("옷", 20, 800),
                        Item("보석", 1, 4000),
                        Item("책", 100, 300),
                        Item("프린터", 18, 30),
                        Item("냉장고", 200, 700),
                        Item("그림", 10, 1000)]
    print(knapsack(items, 75))

메모이제이션을 위해 2차원 리스트 table을 생성한다. 테이블의 행은 물건, 테이블의 열은 배낭의 무게이다.

이해를 돕기 위해 3개의 물건과 3파운드의 용량만을 설정해 문제를 축소했다. 다음 표는 축소한 문제의 테이블이다.

  0파운드 1파운드 2파운드 3파운드
성냥 1파운드 / 5달러 0 5 5 5
손전등 2파운드 / 10달러 0 5 10 15
책 1파운드 / 15달러 0 15 20 25

물건의 종류가 성냥뿐이라면(1행) 최대 값어치는 5달러이다. 하지만 손전등을 추가로 고려한다면(2행), 성냥과 손전등 모두 배낭에 들어가므로 최대 값어치가 15달러로 늘어난다. 책을 추가로 고려한다(3행). 책은 성냥과 비교했을 때 무게에 비해 높은 값어치를 가지며, 따라서 성냥 + 손전등 대신 책 + 손전등으로 배낭을 채운다면 최대 값어치를 25달러로 증가시킬 수 있다.

현재 행의 결과가 이전 행의 결과와 다르다면 구성품이 변경된 것이다. 이를 이용하면 마지막 행으로부터 거슬러 올라가 배낭 구성품을 추적할 수 있다.

실행 결과

1

[Item(name='그림', weight=10, value=1000), Item(name='보석', weight=1, value=4000), Item(name='옷', weight=20, value=800), Item(name='노트북', weight=3, value=1000), Item(name='오디오', weight=35, value=400), Item(name='촛대', weight=2, value=300)]

외판원 문제

tsp.py

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

from typing import Dict, List, Iterable, Tuple
from itertools import permutations


vt_distances:Dict[str, Dict[str, int]] = {
    "러틀랜드": {
        "벌링턴": 67,
        "화이트 리버 정션": 46,
        "베닝턴": 55,
        "브래틀보로": 75
    },
    "벌링턴": {
        "러틀랜드": 67,
        "화이트 리버 정션": 91,
        "베닝턴": 122,
        "브래틀보로": 153
    },
    "화이트 리버 정션": {
        "러틀랜드": 46,
        "벌링턴": 91,
        "베닝턴": 98,
        "브래틀보로": 65
    },
    "베닝턴": {
        "러틀랜드": 55,
        "벌링턴": 122,
        "화이트 리버 정션": 98,
        "브래틀보로": 40
    },
    "브래틀보로": {
        "러틀랜드": 75,
        "벌링턴": 153,
        "화이트 리버 정션": 65,
        "베닝턴": 40
    }
}


vt_cities:Iterable[str] = vt_distances.keys()
city_permutations:Iterable[Tuple[str, ...]] = permutations(vt_cities)
tsp_paths:List[Tuple[str, ...]] = [c + (c[0],) for c in city_permutations]


if __name__ == "__main__":
    best_path:Tuple[str, ...]
    min_distance:int = 99999999999
    for path in tsp_paths:
        distance:int = 0
        last:str = path[0]
        for next in path[1:]:
            distance += vt_distances[last][next]
            last = next
        if distance < min_distance:
            min_distance = distance
            best_path = path
    print(f"최단 경로는 {best_path}이고, {min_distance} 마일입니다.")

itertools 모듈을 사용해 permutations(순열)를 생성하고, 모든 가능성(5! = 120)을 브루트 포스로 검사해 최단 경로를 갖는 경우를 반환한다.

새로 발견한 경로가 최단 경로보다 더 짧을 경우 갱신이 이루어진다.

실행 결과

1

최단 경로는 ('러틀랜드', '벌링턴', '화이트 리버 정션', '브래틀보로', '베닝턴', '러틀랜드')이고, 318 마일입니다.

전화번호 니모닉

phone_number_mnemonics.py

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

from typing import Dict, Tuple, Iterable, List
from itertools import product


phone_mapping:Dict[str, Tuple[str, ...]] = {
    "1": ("1",),
    "2": ("a", "b", "c"),
    "3": ("d", "e", "f"),
    "4": ("g", "h", "i"),
    "5": ("j", "k", "l"),
    "6": ("m", "n", "o"),
    "7": ("p", "q", "r", "s"),
    "8": ("t", "u", "v"),
    "9": ("w", "x", "y", "z"),
    "0": ("0",),
}


def possible_mnemonics(phone_number:str) -> Iterable[Tuple[str, ...]]:
    letter_tuples:List[Tuple[str, ...]] = []
    for digit in phone_number:
        letter_tuples.append(phone_mapping.get(digit, (digit,)))
    return product(*letter_tuples)


if __name__ == "__main__":
    phone_number:str = input("전화번호를 입력해주세요: ")
    print("가능한 니모닉 목록: ")
    for mnemonic in possible_mnemonics(phone_number):
        print("".join(mnemonic))

itertools 모듈의 product(중복 순열)를 사용해 문제를 해결한다.

실행 결과

1
2
3
4
5
6
7
8
9

전화번호를 입력해주세요: 2024738
가능한 니모닉 목록: 
a0agpdt
a0agpdu

...

c0cisfu
c0cisfv

연습문제

📝 9-1

4장의 그래프 프레임워크를 사용하여 외판원 문제 코드를 다시 작성하라.

_practice_question_9_1.py

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

from __future__ import annotations
from weighted_graph import WeightedGraph
from itertools import permutations


def search(weightedGraph:WeightedGraph):
    best = 999_999_999
    path = None

    def vertex2_to_weight(from_vertex, to_vertex):
        from_index = weightedGraph.index_of(from_vertex)
        items = weightedGraph.neighbors_for_index_with_weights(from_index)
        weight = [item[1] for item in items if item[0] == to_vertex][0]
        return weight

    for a in list(permutations(weightedGraph._vertices)):
        current = vertex2_to_weight(a[0], a[-1])
        for idx in range(weightedGraph.vertex_count - 1):
            current += vertex2_to_weight(a[idx], a[idx + 1])
        if current < best:
            best = current
            path = a
    
    path = list(path)
    path.append(path[0])
    return f"최단 경로는 {path} 이고, {best} 마일입니다."


if __name__ == "__main__":
    tsp_graph:WeightedGraph[str] = WeightedGraph(
        ["러틀랜드", "벌링턴", "화이트 리버 정션", "베닝턴", "브래틀보로"]
    )
    tsp_graph.add_edge_by_vertices("러틀랜드", "벌링턴", 67)
    tsp_graph.add_edge_by_vertices("러틀랜드", "화이트 리버 정션", 46)
    tsp_graph.add_edge_by_vertices("러틀랜드", "베닝턴", 55)
    tsp_graph.add_edge_by_vertices("러틀랜드", "브래틀보로", 75)
    tsp_graph.add_edge_by_vertices("벌링턴", "화이트 리버 정션", 91)
    tsp_graph.add_edge_by_vertices("벌링턴", "베닝턴", 122)
    tsp_graph.add_edge_by_vertices("벌링턴", "브래틀보로", 153)
    tsp_graph.add_edge_by_vertices("화이트 리버 정션", "베닝턴", 98)
    tsp_graph.add_edge_by_vertices("화이트 리버 정션", "브래틀보로", 65)
    tsp_graph.add_edge_by_vertices("베닝턴", "브래틀보로", 40)

    result = search(tsp_graph)
    print(result)

실행 결과

1
2

최단 경로는 ['러틀랜드', '벌링턴', '화이트 리버 정션', '브래틀보로', '베닝턴', '러틀랜드'] 이고, 318 마일
입니다.

📝 9-2

5장에서 배운 유전 알고리즘을 사용하여 외판원 문제를 구현하라. 이 장에서 설명한 버몬트 주 도시의 간단한 데이터셋부터 시작한다.

유전 알고리즘이 짧은 시간 내에 최적의 답을 제공하는가? 그런 다음 점점 더 많은 도시를 추가하여 문제를 풀어보라.

유전 알고리즘은 얼마나 잘 유지되는가? 인터넷에서 외판원 문제를 위해 특별히 제작된 많은 데이터셋을 찾을 수 있다.

문제 분석의 효율성을 확인하기 위한 테스트 프레임워크를 구현하라.

📝 9-3

전화번호 니모닉 프로그램에 사전 기능을 추가하여 유효한 단어가 포함된 순열만 반환하라.

_practice_question_9_3.py

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

from typing import Dict, Tuple, Iterable, List
from itertools import product


phone_mapping:Dict[str, Tuple[str, ...]] = {
    "1": ("1",),
    "2": ("a", "b", "c"),
    "3": ("d", "e", "f"),
    "4": ("g", "h", "i"),
    "5": ("j", "k", "l"),
    "6": ("m", "n", "o"),
    "7": ("p", "q", "r", "s"),
    "8": ("t", "u", "v"),
    "9": ("w", "x", "y", "z"),
    "0": ("0",),
}

dictionary = ["gate", "gave", "hate", "have", "code", "love"]

def possible_mnemonics(phone_number:str) -> Iterable[Tuple[str, ...]]:
    letter_tuples:List[Tuple[str, ...]] = []
    for digit in phone_number:
        letter_tuples.append(phone_mapping.get(digit, (digit,)))
    possible_mnemonics = []
    [possible_mnemonics.append(x) for x in product(*letter_tuples) if "".join(x) in dictionary]
    return possible_mnemonics


if __name__ == "__main__":
    phone_number:str = input("전화번호를 입력해주세요: ")
    print("가능한 니모닉 목록: ")
    for mnemonic in possible_mnemonics(phone_number):
        print("".join(mnemonic))

실행 결과

1
2
3
4
5
6

전화번호를 입력해주세요: 4283
가능한 니모닉 목록: 
gate
gave
hate
have