알고리즘 수학 종합

# 문제: 다음 코드의 시간복잡도?

def mystery(arr):
    n = len(arr)
    result = []
    for i in range(n):           # O(n)
        for j in range(i+1, n):  # O(n)
            if arr[i] + arr[j] == 0:
                result.append((i, j))
    return result


# 분석: O(n²)
# n=10,000 → 1억 연산 → 약 1초
# n=100,000 → 100억 연산 → 100초+ (시간 초과)


# 개선: 해시셋으로 O(n)
def mystery_v2(arr):
    seen = set()
    result = []
    for i, x in enumerate(arr):
        if -x in seen:
            result.append((i, x))
        seen.add(x)
    return result

# 문제: 정렬되지 않은 배열에서 두 수의 합이 target인 쌍 찾기

import bisect

def find_pairs(arr, target):
    arr = sorted(arr)  # O(n log n)
    pairs = []
    for i, x in enumerate(arr):
        # 나머지가 정렬된 부분에 있는지 이진 탐색
        complement = target - x
        idx = bisect.bisect_left(arr, complement, i+1)
        if idx < len(arr) and arr[idx] == complement:
            pairs.append((x, complement))
    return pairs


print(find_pairs([3, 1, 4, 1, 5, 9, 2, 6], 7))
# [(1, 6), (3, 4)]


# 시간: O(n log n) 정렬 + O(n log n) 검색
# 공간: O(n) 정렬 결과

# 문제: 1~n 까지 만들 수 있는 코인 조합 수 (동전 [1,2,5])

def count_ways(coins, amount):
    """동전 조합으로 amount 만드는 경우의 수"""
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]
    return dp[amount]


print(count_ways([1, 2, 5], 11))  # 11
# {1*11}, {1*9+2}, {1*7+2*2}, ..., {5+5+1} 등 11가지


# 시간: O(coins × amount)
# 공간: O(amount)

# 문제: 미로에서 출구까지 최단 경로

from collections import deque

maze = [
    "S#####",
    ".....#",
    "#.#.##",
    "#.#..#",
    "#####E",
]


def shortest_path_maze(maze):
    rows, cols = len(maze), len(maze[0])

    # 시작/끝 찾기
    start = end = None
    for r in range(rows):
        for c in range(cols):
            if maze[r][c] == 'S': start = (r, c)
            elif maze[r][c] == 'E': end = (r, c)

    # BFS
    queue = deque([(start, 0)])
    visited = {start}

    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == end:
            return dist

        for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                and (nr, nc) not in visited
                and maze[nr][nc] != '#'):
                visited.add((nr, nc))
                queue.append(((nr, nc), dist + 1))

    return -1


print(shortest_path_maze(maze))  # 최단 거리 출력


# BFS — 시간 O(rows × cols), 공간 O(rows × cols)

# 문제: N개 도시를 모두 방문하는 최단 경로 (외판원 문제)
# 비트마스크로 방문한 도시 집합 표현 → DP

def tsp(distances):
    n = len(distances)
    INF = float('inf')

    # dp[mask][i] = mask 상태 + 마지막 도시 i까지의 최단 거리
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 시작: 도시 0에서 출발, 비트 0번 켜짐

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            # 도시 u에서 갈 수 있는 다음 도시 v
            for v in range(n):
                if mask & (1 << v):  # 이미 방문
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(
                    dp[new_mask][v],
                    dp[mask][u] + distances[u][v]
                )

    # 모든 도시 방문 후 0으로 돌아오기
    full = (1 << n) - 1
    return min(dp[full][i] + distances[i][0] for i in range(1, n))


distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print(tsp(distances))  # 80


# 시간: O(2^n × n²)
# n=20에서도 약 4억 연산 — 1초 내

□ 빅오 표기법 7가지 (O(1)~O(2^n)) 즉시 판단
□ 시간 vs 공간 트레이드오프 의식적 선택
□ 비교 정렬 하한 O(n log n) 이해 + 카운팅 정렬 조건
□ 이진 검색 + bisect 활용
□ 점화식 → 마스터 정리로 시간복잡도 도출
□ DP 두 조건(최적 부분 구조 + 중복 부분 문제) 판단
□ 그리디 정당성 증명 + 실패 케이스 식별
□ 비트마스크로 부분집합 표현 + DP 결합

1. 백준 / 프로그래머스 — 문제 풀이 (단계별)
   · Bronze → Silver → Gold (3개월~1년)
2. LeetCode — 영어 문제 + Top 100
   · Easy 50개 → Medium 100개 → Hard 30개
3. Codeforces — 실시간 경쟁
   · Round 참여 + 레이팅 1500+ 목표
4. 책: "알고리즘 문제 해결 전략" (구종만)
       "알고리즘 트레이닝" (Steven Halim)
5. 시니어 면접 대비
   · 시간복잡도 즉답 + 코드 작성 + 최적화 토론