자료구조론 완전정복

# O(1) - 상수 시간: 입력 크기와 무관하게 항상 일정
def get_first(arr):
    return arr[0]   # 배열 크기가 1만이든 100만이든 1번 연산

# O(n) - 선형 시간: 입력 크기에 비례
def find_max(arr):
    max_val = arr[0]
    for x in arr:      # n번 반복
        if x > max_val:
            max_val = x
    return max_val

# O(n²) - 이차 시간: 이중 반복문
def has_duplicate(arr):
    for i in range(len(arr)):         # n번
        for j in range(i+1, len(arr)):  # 최대 n번
            if arr[i] == arr[j]:        # n × n = n²
                return True
    return False

# O(log n) - 로그 시간: 매 단계마다 절반으로 줄어듦
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:        # 범위가 절반씩 줄어듦 → log₂(n)번
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# 공간 O(1): 추가 메모리를 상수만큼만 사용
def sum_array(arr):
    total = 0            # 변수 1개 (상수)
    for x in arr:
        total += x
    return total

# 공간 O(n): 입력 크기에 비례하는 추가 메모리
def reverse_array(arr):
    result = []          # 새 배열 → n개 원소 저장
    for x in reversed(arr):
        result.append(x)
    return result

/* 정적 배열: 크기가 컴파일 시점에 결정됨 */
#include <stdio.h>

int main() {
    // 선언과 동시에 초기화
    int arr[5] = {10, 20, 30, 40, 50};
    
    // 인덱스로 접근 - O(1)
    printf("arr[2] = %d\n", arr[2]);  // 30
    
    // 값 변경
    arr[2] = 99;
    
    // 순회 - O(n)
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    // 출력: 10 20 99 40 50
    
    return 0;
}

# Python의 list는 동적 배열
arr = [10, 20, 30, 40, 50]

# 인덱스 접근 - O(1)
print(arr[2])         # 30

# 끝에 추가 - amortized O(1)
arr.append(60)         # [10, 20, 30, 40, 50, 60]

# 중간에 삽입 - O(n) (뒤의 원소를 모두 밀어야 함)
arr.insert(2, 99)      # [10, 20, 99, 30, 40, 50, 60]

# 삭제 - O(n)
arr.pop(2)              # [10, 20, 30, 40, 50, 60]

# 끝에서 삭제 - O(1)
arr.pop()               # [10, 20, 30, 40, 50]

# 길이 확인
print(len(arr))         # 5

# 슬라이싱 - O(k) (k = 슬라이스 크기)
sub = arr[1:4]          # [20, 30, 40]

# 3×4 2차원 배열 (행렬)
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9, 10, 11, 12]
]

# 접근: matrix[행][열]
print(matrix[1][2])   # 7 (2번째 행, 3번째 열)

# 전체 순회
rows = len(matrix)       # 3
cols = len(matrix[0])    # 4

for r in range(rows):
    for c in range(cols):
        print(matrix[r][c], end=" ")
    print()

# 0으로 초기화된 5×5 행렬 만들기
grid = [[0] * 5 for _ in range(5)]

class Node:
    """연결 리스트의 한 칸 (노드)"""
    def __init__(self, data):
        self.data = data    # 저장할 데이터
        self.next = None    # 다음 노드를 가리키는 포인터


class SinglyLinkedList:
    """단일 연결 리스트"""
    def __init__(self):
        self.head = None    # 리스트의 첫 번째 노드
        self.size = 0
    
    def push_front(self, data):
        """맨 앞에 삽입 - O(1)"""
        new_node = Node(data)
        new_node.next = self.head  # 새 노드가 기존 head를 가리킴
        self.head = new_node       # head를 새 노드로 변경
        self.size += 1
    
    def push_back(self, data):
        """맨 뒤에 삽입 - O(n)"""
        new_node = Node(data)
        if not self.head:          # 리스트가 비어있으면
            self.head = new_node
        else:
            curr = self.head
            while curr.next:       # 마지막 노드까지 이동
                curr = curr.next
            curr.next = new_node   # 마지막 뒤에 연결
        self.size += 1
    
    def pop_front(self):
        """맨 앞 삭제 - O(1)"""
        if not self.head:
            return None
        data = self.head.data
        self.head = self.head.next  # head를 다음 노드로 이동
        self.size -= 1
        return data
    
    def search(self, target):
        """값 검색 - O(n)"""
        curr = self.head
        idx = 0
        while curr:
            if curr.data == target:
                return idx
            curr = curr.next
            idx += 1
        return -1
    
    def display(self):
        """전체 출력"""
        curr = self.head
        parts = []
        while curr:
            parts.append(str(curr.data))
            curr = curr.next
        print(" → ".join(parts) + " → None")


# 사용 예시
ll = SinglyLinkedList()
ll.push_back(10)
ll.push_back(20)
ll.push_back(30)
ll.push_front(5)
ll.display()   # 5 → 10 → 20 → 30 → None

print(ll.search(20))  # 2 (인덱스)
ll.pop_front()
ll.display()   # 10 → 20 → 30 → None

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None   # 이전 노드
        self.next = None   # 다음 노드


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def push_back(self, data):
        """맨 뒤 삽입 - O(1) (tail 포인터 덕분)"""
        new_node = DNode(data)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    
    def pop_back(self):
        """맨 뒤 삭제 - O(1) (이중 연결이므로 가능!)"""
        if not self.tail:
            return None
        data = self.tail.data
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
        self.size -= 1
        return data

class Stack:
    """리스트 기반 스택 구현"""
    def __init__(self):
        self._data = []
    
    def push(self, item):
        """맨 위에 추가"""
        self._data.append(item)
    
    def pop(self):
        """맨 위 제거 및 반환"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._data.pop()
    
    def peek(self):
        """맨 위 확인 (제거하지 않음)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._data[-1]
    
    def is_empty(self):
        return len(self._data) == 0
    
    def __len__(self):
        return len(self._data)


# 사용 예시
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s.peek())   # 30
print(s.pop())    # 30
print(s.pop())    # 20
print(len(s))      # 1

def is_valid_parentheses(s):
    """괄호 문자열이 올바른지 검사"""
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    
    for ch in s:
        if ch in '({[':
            stack.append(ch)       # 여는 괄호 → push
        elif ch in ')}]':
            if not stack or stack[-1] != pairs[ch]:
                return False      # 짝이 안 맞음
            stack.pop()            # 닫는 괄호 → pop
    
    return len(stack) == 0       # 스택이 비어야 올바름

# 테스트
print(is_valid_parentheses("({[]})"))   # True
print(is_valid_parentheses("({[})"))    # False
print(is_valid_parentheses("(("))       # False

from collections import deque

# deque를 사용한 효율적인 큐
queue = deque()

# enqueue (뒤에 추가)
queue.append(10)
queue.append(20)
queue.append(30)
print(queue)        # deque([10, 20, 30])

# dequeue (앞에서 제거) - O(1)!
front = queue.popleft()
print(front)        # 10
print(queue)        # deque([20, 30])

# peek (앞 원소 확인)
print(queue[0])      # 20

class CircularQueue:
    """고정 크기 원형 큐"""
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0        # 앞 인덱스
        self.rear = -1        # 뒤 인덱스
        self.size = 0
    
    def enqueue(self, item):
        if self.size == self.capacity:
            raise OverflowError("Queue is full")
        self.rear = (self.rear + 1) % self.capacity  # 원형으로!
        self.queue[self.rear] = item
        self.size += 1
    
    def dequeue(self):
        if self.size == 0:
            raise IndexError("Queue is empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity  # 원형으로!
        self.size -= 1
        return item

from collections import deque

dq = deque()

# 양쪽에서 삽입
dq.append(20)        # 뒤에 추가:       [20]
dq.append(30)        # 뒤에 추가:       [20, 30]
dq.appendleft(10)   # 앞에 추가:       [10, 20, 30]
dq.append(40)        # 뒤에 추가:       [10, 20, 30, 40]

# 양쪽에서 삭제
print(dq.popleft())  # 10 (앞에서 제거): [20, 30, 40]
print(dq.pop())      # 40 (뒤에서 제거): [20, 30]

# maxlen으로 크기 제한 (슬라이딩 윈도우에 유용)
window = deque(maxlen=3)
for i in range(5):
    window.append(i)
    print(list(window))

# 출력:
# [0]
# [0, 1]
# [0, 1, 2]
# [1, 2, 3]    ← 0이 자동으로 빠짐
# [2, 3, 4]    ← 1이 자동으로 빠짐

def factorial(n):
    """n! = n × (n-1) × ... × 1"""
    # 기저 사례 (Base Case)
    if n <= 1:
        return 1
    # 재귀 사례 (Recursive Case)
    return n * factorial(n - 1)

print(factorial(5))  # 120

# 호출 과정 시각화:
# factorial(5) = 5 × factorial(4)
#              = 5 × 4 × factorial(3)
#              = 5 × 4 × 3 × factorial(2)
#              = 5 × 4 × 3 × 2 × factorial(1)
#              = 5 × 4 × 3 × 2 × 1
#              = 120

# ❌ 비효율적 재귀 - O(2ⁿ)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# ✅ 메모이제이션 - O(n)
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# ✅ 반복문 (Bottom-Up DP) - O(n), 공간 O(1)
def fib_iter(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

print(fib_memo(50))   # 12586269025 (즉시 계산됨)
print(fib_iter(50))   # 12586269025

def hanoi(n, source, target, auxiliary):
    """원판 n개를 source에서 target으로 이동"""
    if n == 1:
        print(f"원판 1: {source} → {target}")
        return
    # 1) 위의 n-1개를 보조 기둥으로
    hanoi(n-1, source, auxiliary, target)
    # 2) 가장 큰 원판을 목표 기둥으로
    print(f"원판 {n}: {source} → {target}")
    # 3) 보조 기둥의 n-1개를 목표 기둥으로
    hanoi(n-1, auxiliary, target, source)

hanoi(3, 'A', 'C', 'B')
# 원판 1: A → C
# 원판 2: A → B
# 원판 1: C → B
# 원판 3: A → C
# 원판 1: B → A
# 원판 2: B → C
# 원판 1: A → C
# → 총 2³ - 1 = 7번 이동

class TreeNode:
    """이진 트리 노드"""
    def __init__(self, data):
        self.data = data
        self.left = None     # 왼쪽 자식
        self.right = None    # 오른쪽 자식


# 트리 구성 예시
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

from collections import deque

# 1. 전위 순회 (Pre-order): 루트 → 왼쪽 → 오른쪽
def preorder(node):
    if node is None:
        return
    print(node.data, end=" ")   # 루트 먼저
    preorder(node.left)
    preorder(node.right)

# 2. 중위 순회 (In-order): 왼쪽 → 루트 → 오른쪽
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.data, end=" ")   # 가운데
    inorder(node.right)

# 3. 후위 순회 (Post-order): 왼쪽 → 오른쪽 → 루트
def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end=" ")   # 루트 마지막

# 4. 레벨 순회 (Level-order / BFS)
def levelorder(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.data, end=" ")
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

# 실행 결과 (위에서 만든 트리 기준)
preorder(root)     # 1 2 4 5 3 6
inorder(root)      # 4 2 5 1 3 6
postorder(root)    # 4 5 2 6 3 1
levelorder(root)   # 1 2 3 4 5 6

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


class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        """삽입 - 올바른 위치를 찾아 새 노드 배치"""
        self.root = self._insert(self.root, key)
    
    def _insert(self, node, key):
        if node is None:
            return BSTNode(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        # 중복 키는 무시
        return node
    
    def search(self, key):
        """탐색 - 값 비교로 좌/우 결정"""
        return self._search(self.root, key)
    
    def _search(self, node, key):
        if node is None:
            return False
        if key == node.key:
            return True
        elif key < node.key:
            return self._search(node.left, key)
        else:
            return self._search(node.right, key)
    
    def inorder(self):
        """중위 순회 → 정렬된 순서 출력"""
        result = []
        self._inorder(self.root, result)
        return result
    
    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.key)
            self._inorder(node.right, result)


# 사용 예시
bst = BST()
for v in [15, 8, 23, 4, 12, 18, 30, 2, 13]:
    bst.insert(v)

print(bst.inorder())     # [2, 4, 8, 12, 13, 15, 18, 23, 30]
print(bst.search(12))   # True
print(bst.search(99))   # False

import heapq

# Python의 heapq는 최소 힙(Min Heap)
heap = []
heapq.heappush(heap, 8)
heapq.heappush(heap, 3)
heapq.heappush(heap, 5)
heapq.heappush(heap, 12)
heapq.heappush(heap, 1)

print(heap)              # [1, 3, 5, 12, 8]
print(heap[0])            # 1 (최소값 확인 - O(1))

# 최소값 꺼내기 - O(log n)
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 5

# 리스트를 힙으로 변환 - O(n)
data = [9, 1, 7, 3, 5]
heapq.heapify(data)
print(data)              # [1, 3, 7, 9, 5]

# 최대 힙이 필요할 때: 값에 -를 붙여서 사용
max_heap = []
for v in [3, 1, 5, 2]:
    heapq.heappush(max_heap, -v)

print(-heapq.heappop(max_heap))  # 5 (최대값)
print(-heapq.heappop(max_heap))  # 3

import heapq

def kth_largest(nums, k):
    """크기 k의 최소 힙을 유지하여 k번째 큰 원소를 찾음"""
    heap = nums[:k]
    heapq.heapify(heap)
    
    for num in nums[k:]:
        if num > heap[0]:       # 현재 k번째보다 크면
            heapq.heapreplace(heap, num)  # 교체
    
    return heap[0]              # 힙의 루트 = k번째 큰 값

print(kth_largest([3,1,5,12,7,9,2], 3))  # 7 (3번째 큰 수)

# 또는 더 간단하게:
print(heapq.nlargest(3, [3,1,5,12,7,9,2])[-1])  # 7

class HashTable:
    """체이닝 방식 해시 테이블"""
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    
    def _hash(self, key):
        """해시 함수: 키를 인덱스로 변환"""
        return hash(key) % self.capacity
    
    def put(self, key, value):
        """삽입/수정 - 평균 O(1)"""
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)  # 기존 키 → 수정
                return
        self.buckets[idx].append((key, value))  # 새 키 → 추가
        self.size += 1
    
    def get(self, key):
        """검색 - 평균 O(1)"""
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)
    
    def remove(self, key):
        """삭제 - 평균 O(1)"""
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx].pop(i)
                self.size -= 1
                return
        raise KeyError(key)

# 사용
ht = HashTable()
ht.put("apple", 500)
ht.put("banana", 300)
print(ht.get("apple"))    # 500

# Python dict = 고성능 해시 테이블
d = {}
d["apple"] = 500        # 삽입 O(1)
d["banana"] = 300
print(d["apple"])        # 500 - 조회 O(1)
print("apple" in d)      # True - 존재 확인 O(1)
del d["banana"]         # 삭제 O(1)

# 실전 활용: 빈도 세기
def count_frequency(arr):
    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1
    return freq

print(count_frequency(["a","b","a","c","b","a"]))
# {'a': 3, 'b': 2, 'c': 1}

# 실전 활용: 두 수의 합 (Two Sum)
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

# 인접 리스트 (딕셔너리)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# "A와 연결된 정점은?" → O(1)
print(graph['A'])   # ['B', 'C']

# 가중 그래프: 인접 리스트 + 가중치
weighted_graph = {
    '서울': [('대전', 140), ('강릉', 165)],
    '대전': [('서울', 140), ('부산', 200)],
    '부산': [('대전', 200)],
    '강릉': [('서울', 165)]
}

# 인접 행렬 (0: 연결 안 됨, 1: 연결됨)
# 정점: A=0, B=1, C=2, D=3
matrix = [
    [0, 1, 1, 0],  # A: B, C와 연결
    [1, 0, 0, 1],  # B: A, D와 연결
    [1, 0, 0, 1],  # C: A, D와 연결
    [0, 1, 1, 0],  # D: B, C와 연결
]

# "A와 B가 연결되어 있나?" → O(1)
print(matrix[0][1])  # 1 (연결됨)

from collections import deque

def bfs(graph, start):
    """너비 우선 탐색"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []
    
    while queue:
        node = queue.popleft()          # 큐에서 꺼냄
        order.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)  # 큐에 넣음
    
    return order

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

# DFS - 재귀 버전
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# DFS - 스택 버전 (반복)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    
    while stack:
        node = stack.pop()             # 스택에서 꺼냄
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)  # 스택에 넣음
    
    return order

dfs_recursive(graph, 'A')        # A B D E F C
print()
print(dfs_iterative(graph, 'A'))  # ['A', 'B', 'D', 'E', 'F', 'C']

def bubble_sort(arr):
    """버블 정렬 - O(n²)"""
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:       # 교환이 없으면 이미 정렬됨
            break
    return arr

def selection_sort(arr):
    """선택 정렬 - O(n²), 교환 횟수는 최대 n번"""
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

def insertion_sort(arr):
    """삽입 정렬 - O(n²), 거의 정렬된 데이터에는 O(n)"""
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]       # 한 칸씩 오른쪽으로 밀기
            j -= 1
        arr[j+1] = key             # 올바른 위치에 삽입
    return arr

def merge_sort(arr):
    """병합 정렬 - O(n log n), 공간 O(n)"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # 왼쪽 반 정렬
    right = merge_sort(arr[mid:])     # 오른쪽 반 정렬
    
    return merge(left, right)          # 합치기

def merge(left, right):
    """두 정렬된 배열을 하나로 합침"""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

def quick_sort(arr):
    """퀵 정렬 - 평균 O(n log n), 최악 O(n²)"""
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]        # 피벗 선택
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

def linear_search(arr, target):
    """선형 탐색 - O(n)"""
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def binary_search(arr, target):
    """이진 탐색 - O(log n), 배열이 정렬되어 있어야 함"""
    lo, hi = 0, len(arr) - 1
    
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid               # 찾음!
        elif arr[mid] < target:
            lo = mid + 1             # 오른쪽 절반 탐색
        else:
            hi = mid - 1             # 왼쪽 절반 탐색
    
    return -1                       # 못 찾음

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23))  # 5 (인덱스)
print(binary_search(arr, 99))  # -1 (없음)

# Python 내장 모듈
import bisect
idx = bisect.bisect_left(arr, 23)
print(idx, arr[idx])  # 5, 23

class TrieNode:
    def __init__(self):
        self.children = {}       # 자식 노드 (문자 → TrieNode)
        self.is_end = False     # 단어의 끝인지 표시


class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """단어 삽입 - O(m), m = 단어 길이"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
    
    def search(self, word):
        """정확한 단어 검색 - O(m)"""
        node = self._find_node(word)
        return node is not None and node.is_end
    
    def starts_with(self, prefix):
        """접두사 존재 여부 - O(m)"""
        return self._find_node(prefix) is not None
    
    def _find_node(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node


# 사용 예시
trie = Trie()
for w in ["apple", "app", "bat", "bar"]:
    trie.insert(w)

print(trie.search("app"))        # True
print(trie.search("ap"))         # False (단어의 끝이 아님)
print(trie.starts_with("ap"))    # True (접두사로는 존재)
print(trie.starts_with("cat"))   # False

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 처음엔 각자 자기 자신이 대표
        self.rank = [0] * n              # 트리 높이 (최적화용)
    
    def find(self, x):
        """경로 압축: 루트까지 가면서 모든 노드를 루트에 직접 연결"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """랭크 기반 합치기: 낮은 트리를 높은 트리 아래에"""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False    # 이미 같은 집합
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True
    
    def connected(self, x, y):
        """같은 집합인지 확인"""
        return self.find(x) == self.find(y)


# 사용 예시: 5명의 친구 관계
uf = UnionFind(5)   # 0, 1, 2, 3, 4

uf.union(0, 1)       # {0,1} {2} {3} {4}
uf.union(2, 3)       # {0,1} {2,3} {4}
print(uf.connected(0, 1))  # True
print(uf.connected(0, 3))  # False

uf.union(1, 3)       # {0,1,2,3} {4}
print(uf.connected(0, 3))  # True (이제 같은 그룹)

# 문제: 괄호 (), {}, []로만 이루어진 문자열이 올바른지 판단
# 자료구조 선택: 스택 (여는 괄호 push, 닫는 괄호에서 pop하여 짝 확인)

def is_valid(s):
    stack = []
    pair = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in pair.values():
            stack.append(ch)
        elif ch in pair:
            if not stack or stack.pop() != pair[ch]:
                return False
    return len(stack) == 0

print(is_valid("()[]{}"))   # True
print(is_valid("([)]"))     # False
print(is_valid("{[]}"))     # True

# 문제: 미로에서 (0,0)부터 (n-1,m-1)까지 최단 거리
# 자료구조 선택: 큐(BFS) - 비가중 그래프 최단 경로 보장

from collections import deque

def shortest_path(maze):
    rows, cols = len(maze), len(maze[0])
    if maze[0][0] == 1 or maze[rows-1][cols-1] == 1:
        return -1
    
    queue = deque([(0, 0, 1)])   # (행, 열, 거리)
    visited = {(0, 0)}
    directions = [(0,1), (0,-1), (1,0), (-1,0)]
    
    while queue:
        r, c, dist = queue.popleft()
        if r == rows-1 and c == cols-1:
            return dist
        
        for dr, dc in directions:
            nr, nc = r+dr, c+dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and maze[nr][nc] == 0
                    and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist+1))
    
    return -1

maze = [
    [0, 0, 0, 1],
    [1, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
]
print(shortest_path(maze))  # 7

# 문제: 배열에서 가장 자주 등장하는 k개 원소 반환
# 자료구조: dict(빈도 세기) + heapq(Top-K 추출)

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)            # 빈도 세기 O(n)
    return heapq.nlargest(k, count.keys(), key=count.get)

print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]

/* =============================================
   자료구조 치트시트 - 핵심 요약
   ============================================= */

/* ── 1. 배열 (Array) ── */
접근: O(1)  |  탐색: O(n)  |  삽입/삭제(끝): O(1)  |  삽입/삭제(중간): O(n)
→ 인덱스 접근이 많을 때, 순차 데이터에 적합

/* ── 2. 연결 리스트 (Linked List) ── */
접근: O(n)  |  탐색: O(n)  |  삽입/삭제(위치 알 때): O(1)
→ 잦은 삽입/삭제, 크기가 동적으로 변할 때

/* ── 3. 스택 (Stack) ── */
push/pop/peek: O(1)  |  LIFO (후입선출)
→ 괄호 검사, DFS, 되돌리기, 수식 계산

/* ── 4. 큐 (Queue) ── */
enqueue/dequeue/peek: O(1)  |  FIFO (선입선출)
→ BFS, 프로세스 스케줄링, 버퍼

/* ── 5. 해시 테이블 (Hash Table) ── */
삽입/탐색/삭제: O(1) 평균, O(n) 최악
→ 빈도 세기, 중복 확인, 캐시, 딕셔너리

/* ── 6. 이진 탐색 트리 (BST) ── */
삽입/탐색/삭제: O(log n) 평균, O(n) 최악(편향)
중위 순회 = 정렬된 순서
→ 정렬된 데이터 관리, 범위 탐색

/* ── 7. 힙 (Heap) ── */
최대/최소 확인: O(1)  |  삽입/삭제: O(log n)
→ 우선순위 큐, Top-K, 힙 정렬

/* ── 8. 그래프 (Graph) ── */
인접 리스트: 공간 O(V+E), 탐색 O(V+E)
인접 행렬: 공간 O(V²), 연결 확인 O(1)
BFS: 큐 사용, 최단 경로  |  DFS: 스택/재귀, 경로 탐색

/* ── 9. 트라이 (Trie) ── */
삽입/탐색: O(m), m = 문자열 길이
→ 자동 완성, 접두사 검색, 사전

/* ── 10. 유니온-파인드 (Union-Find) ── */
find/union: 거의 O(1) (경로 압축 + 랭크)
→ 집합 관리, 연결 여부, 크루스칼 MST

/* ── 정렬 알고리즘 ── */
버블/선택/삽입: O(n²) — 교육용
병합 정렬: O(n log n), 안정, 공간 O(n)
퀵 정렬: O(n log n) 평균, 실무에서 빠름
파이썬 sorted(): Timsort, O(n log n), 안정

/* ── Big-O 성장 순서 ── */
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)