1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# ★ 리스트 슬라이싱 — 인덱스 정확히!
arr = [10, 20, 30, 40, 50]

print(arr[1:4])    # [20, 30, 40]  (인덱스 1~3)
print(arr[:3])     # [10, 20, 30]  (처음~2)
print(arr[2:])     # [30, 40, 50]  (인덱스 2~끝)
print(arr[-2:])    # [40, 50]      (뒤에서 2개)
print(arr[::2])    # [10, 30, 50]  (2칸씩)
print(arr[::-1])   # [50, 40, 30, 20, 10]  (역순)

# ★ 리스트 컴프리헨션
squares = [x**2 for x in range(1, 6)]
# [1, 4, 9, 16, 25]

evens = [x for x in range(10) if x % 2 == 0]
# [0, 2, 4, 6, 8]

matrix = [[i*3+j for j in range(3)] for i in range(3)]
# [[0,1,2], [3,4,5], [6,7,8]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# ★ 딕셔너리 활용
d = {'a': 1, 'b': 2, 'c': 3}

print(d.get('x', 0))       # 0 (없으면 기본값)
print(list(d.keys()))       # ['a', 'b', 'c']
print(list(d.values()))     # [1, 2, 3]
print(list(d.items()))      # [('a',1), ('b',2), ('c',3)]

# 빈도수 세기
from collections import Counter
text = "banana"
cnt = Counter(text)
print(cnt)                  # Counter({'a': 3, 'n': 2, 'b': 1})
print(cnt.most_common(2))   # [('a', 3), ('n', 2)]

# ★ 집합 연산
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print(A | B)    # {1,2,3,4,5,6}  합집합
print(A & B)    # {3,4}          교집합
print(A - B)    # {1,2}          차집합
print(A ^ B)    # {1,2,5,6}      대칭차집합

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
# ★ 가변 인자
def add(*args):
    return sum(args)

print(add(1, 2, 3))     # 6
print(add(1, 2, 3, 4))  # 10

# ★ 키워드 인자
def info(**kwargs):
    for k, v in kwargs.items():
        print(f"{k}: {v}")

info(name="Kim", age=25)
# name: Kim
# age: 25

# ★ 람다와 고차 함수
nums = [3, 1, 4, 1, 5, 9]
print(sorted(nums))                      # [1, 1, 3, 4, 5, 9]
print(sorted(nums, reverse=True))        # [9, 5, 4, 3, 1, 1]

pairs = [(1,'b'), (2,'a'), (3,'c')]
print(sorted(pairs, key=lambda x: x[1])) # [(2,'a'), (1,'b'), (3,'c')]

print(list(map(lambda x: x**2, [1,2,3])))    # [1, 4, 9]
print(list(filter(lambda x: x>2, [1,2,3,4])))# [3, 4]

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
# ★ Python 상속과 오버라이딩
class Animal:
    def __init__(self, name):
        self.name = name

    def speak(self):
        return "..."

class Dog(Animal):
    def speak(self):
        return f"{self.name}: Woof!"

class Cat(Animal):
    def speak(self):
        return f"{self.name}: Meow!"

# 다형성
animals = [Dog("Rex"), Cat("Kitty"), Dog("Buddy")]
for a in animals:
    print(a.speak())
# Rex: Woof!
# Kitty: Meow!
# Buddy: Woof!

# ★ 특수 메서드 (매직 메서드)
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __str__(self):
        return f"({self.x}, {self.y})"

p1 = Point(1, 2)
p2 = Point(3, 4)
print(p1 + p2)  # (4, 6)

1
2
3
4
5
6
7
8
9
10
11
12
13
# ★ 버블 정렬 — O(n²), 안정 정렬
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# [5,3,1,4,2] → 과정 추적:
# i=0: [3,1,4,2,5]  ← 5가 맨 뒤로
# i=1: [1,3,2,4,5]  ← 4 확정
# i=2: [1,2,3,4,5]  ← 3 확정

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# ★ 선택 정렬 — O(n²), 불안정 정렬
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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

# [5,3,1,4,2] → 과정:
# i=0: min=1 → [1,3,5,4,2]
# i=1: min=2 → [1,2,5,4,3]
# i=2: min=3 → [1,2,3,4,5]

1
2
3
4
5
6
7
8
9
10
# ★ 삽입 정렬 — O(n²), 안정, 거의 정렬된 데이터에 효율적
def insertion_sort(arr):
    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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# ★ 퀵 정렬 — 평균 O(n log n), 최악 O(n²), 불안정
def quick_sort(arr):
    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)

# ★ 제자리(in-place) 퀵 정렬 — C 스타일 출제 빈출
def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[high] = arr[high], arr[i+1]
        pi = i + 1

        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# ★ 병합 정렬 — O(n log n), 안정, 추가 메모리 O(n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    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

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
# ★ 이진 탐색 — O(log n), 정렬된 배열 필수
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 예) arr=[1,3,5,7,9,11], target=7
# left=0, right=5, mid=2 → arr[2]=5<7 → left=3
# left=3, right=5, mid=4 → arr[4]=9>7 → right=3
# left=3, right=3, mid=3 → arr[3]=7 → return 3

# ★ lower_bound: target 이상인 첫 위치
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

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
# ★ BFS — 큐 사용, 최단 경로
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in sorted(graph[node]):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

# ★ DFS — 스택/재귀 사용
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    result = [node]
    for neighbor in sorted(graph[node]):
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    return result

# 예제 그래프
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6],
    4: [2],
    5: [2, 6],
    6: [3, 5]
}

print(bfs(graph, 1))  # [1, 2, 3, 4, 5, 6]
print(dfs(graph, 1))  # [1, 2, 4, 5, 6, 3]

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
# ★ DP 핵심 패턴 — 피보나치 (탑다운 vs 바텀업)

# 탑다운 (메모이제이션)
def fib_top_down(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_top_down(n-1) + fib_top_down(n-2)
    return memo[n]

# 바텀업 (타뷸레이션)
def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# ★ 0-1 배낭 문제
def knapsack(W, weights, values, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

# ★ 최장 공통 부분수열 (LCS)
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# 예) lcs("ABCBDAB", "BDCAB") = 4 ("BCAB")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# ★ 활동 선택 문제 (Activity Selection)
def activity_selection(activities):
    # activities = [(시작, 종료), ...]
    activities.sort(key=lambda x: x[1])  # 종료 시간순 정렬
    result = [activities[0]]
    for i in range(1, len(activities)):
        if activities[i][0] >= result[-1][1]:
            result.append(activities[i])
    return result

# ★ 거스름돈 문제
def coin_change_greedy(amount, coins=[500, 100, 50, 10]):
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

# coin_change_greedy(1260) → 500×2 + 100×2 + 50×1 + 10×1 = 6개

1
2
3
4
5
6
7
8
9
def mystery(n):
    if n <= 1:
        return str(n)
    if n % 2 == 0:
        return mystery(n // 2) + "0"
    else:
        return mystery(n // 2) + "1"

print(mystery(13))