이산수학 종합 문제

# 소셜 네트워크에서 친구의 친구 중 미친구 추천
# 집합 + 그래프 BFS 결합

from collections import defaultdict

friends = defaultdict(set)

def add_friend(a, b):
    friends[a].add(b)
    friends[b].add(a)


# 친구 관계 구성
relations = [
    ('alice', 'bob'),
    ('alice', 'charlie'),
    ('bob', 'dave'),
    ('charlie', 'eve'),
    ('dave', 'frank'),
    ('eve', 'grace'),
    ('frank', 'grace'),
]
for a, b in relations:
    add_friend(a, b)


def recommend_friends(user, max_n=5):
    """
    1. 사용자의 친구 집합 구성 (직접)
    2. 친구의 친구 집합 (간접)
    3. 차집합으로 추천 = 친구의 친구 - 직접 친구 - 본인
    4. 공통 친구 수로 정렬
    """
    direct_friends = friends[user]
    candidates = defaultdict(int)

    for friend in direct_friends:
        for fof in friends[friend]:
            if fof != user and fof not in direct_friends:
                candidates[fof] += 1

    # 공통 친구 수 내림차순 정렬
    ranked = sorted(candidates.items(), key=lambda x: -x[1])
    return ranked[:max_n]


print(recommend_friends('alice'))
# [('dave', 1), ('eve', 1)]
# alice의 친구 bob과 dave 친구 → dave 추천
# alice의 친구 charlie와 eve 친구 → eve 추천

# 해시 함수 + 충돌 해결 — bit.ly 스타일

import hashlib
import string

class URLShortener:
    def __init__(self):
        self.url_to_short = {}
        self.short_to_url = {}
        self.chars = string.ascii_letters + string.digits

    def _generate_short(self, url):
        """SHA-256 해시 → Base62 변환 → 첫 7자"""
        digest = hashlib.sha256(url.encode()).hexdigest()
        n = int(digest, 16)
        result = []
        for _ in range(7):
            result.append(self.chars[n % 62])
            n //= 62
        return ''.join(result)

    def shorten(self, url):
        # 이미 단축된 URL이면 재사용
        if url in self.url_to_short:
            return self.url_to_short[url]

        short = self._generate_short(url)
        # 충돌 해결 — 충돌 시 해시 재계산
        i = 0
        while short in self.short_to_url:
            i += 1
            short = self._generate_short(url + str(i))

        self.url_to_short[url] = short
        self.short_to_url[short] = url
        return short

    def expand(self, short):
        return self.short_to_url.get(short)


s = URLShortener()
print(s.shorten("https://openhyperstep.com/theory/math/1"))
print(s.shorten("https://openhyperstep.com/theory/math/2"))

# 파일 import 순환 의존 탐지 — DFS + 색상 마킹

WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(graph):
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:  # 진행 중인 경로 → 사이클
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(color[n] == WHITE and dfs(n) for n in graph)


# 정상
graph_ok = {
    'a.js': ['b.js'],
    'b.js': ['c.js'],
    'c.js': [],
}
print(has_cycle(graph_ok))  # False

# 순환 — 사이클
graph_cycle = {
    'a.js': ['b.js'],
    'b.js': ['c.js'],
    'c.js': ['a.js'],  # 순환 의존
}
print(has_cycle(graph_cycle))  # True

# 두 배열의 교집합을 O(n+m)으로

def common_elements(arr1, arr2):
    """해시셋으로 O(n+m), 단순 비교는 O(n*m)"""
    set1 = set(arr1)
    return [x for x in arr2 if x in set1]


a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b = [3, 5, 7, 9, 11, 13]
print(common_elements(a, b))  # [3, 5, 7, 9]


# 더 효율적 — 작은 배열을 set으로
def common_elements_v2(arr1, arr2):
    if len(arr1) > len(arr2):
        arr1, arr2 = arr2, arr1  # 작은 게 set
    set1 = set(arr1)
    return [x for x in arr2 if x in set1]

# 학습 챕터의 선수 관계 → 학습 순서 결정
from collections import deque, defaultdict

prereqs = {
    'CH.16 집합':       set(),
    'CH.17 벤다이어그램': {'CH.16 집합'},
    'CH.18 순열':       {'CH.16 집합'},
    'CH.19 조합':       {'CH.18 순열'},
    'CH.20 재귀':       set(),
    'CH.21 그래프':      {'CH.16 집합'},
    'CH.22 BFS/DFS':    {'CH.21 그래프', 'CH.20 재귀'},
    'CH.23 트리':       {'CH.22 BFS/DFS'},
    'CH.24 해시':       {'CH.16 집합'},
}


def topological_sort(prereqs):
    """Kahn's algorithm"""
    in_degree = {node: len(deps) for node, deps in prereqs.items()}
    queue = deque([node for node, d in in_degree.items() if d == 0])
    order = []

    # 역방향 그래프 — 누가 누구의 선수인지
    dependents = defaultdict(list)
    for node, deps in prereqs.items():
        for d in deps:
            dependents[d].append(node)

    while queue:
        node = queue.popleft()
        order.append(node)
        for dep_node in dependents[node]:
            in_degree[dep_node] -= 1
            if in_degree[dep_node] == 0:
                queue.append(dep_node)

    if len(order) != len(prereqs):
        raise ValueError("순환 의존 — 학습 불가")

    return order


for ch in topological_sort(prereqs):
    print(ch)

□ 집합 4가지 연산 (∪/∩/−/△) Python·JS로 구현
□ 벤 다이어그램 시각화 (matplotlib_venn)
□ 순열 nPr·조합 nCr 직접 계산
□ 재귀 함수 + 기저 조건 + 스택 한도 이해
□ 그래프 인접 행렬 vs 인접 리스트 선택
□ BFS·DFS 구현 + 최단 경로
□ 이진 탐색 트리 + 4가지 순회
□ 해시 함수 원리 + bcrypt·체크섬