다목적 최적화 문제에서 하나의 목적함수만 최적화하고 나머지 목적함수들은 허용 한계값(ε) 이하로 제한하여 해를 구하는 방법

단일 최적해가 아닌 Pareto optimal solution들을 생성하는 대표적인 방법

다목적 최적화를 단일 목적 최적화 문제로 변환하는 기법

⭐ ε-constraint의 특징

✅ 1. 하나의 목적함수만 직접 최적화

• 여러 목적함수 중 하나를 주 목적함수로 선택

• 나머지 목적함수들은 제약조건(constraint) 으로 처리

예:

비용 최소화 (목적함수)

이동 거리 ≤ ε

불균형 ≤ ε₂

✅ 2. ε(엡실론)는 허용 한계값

• ε는 각 목적함수에 대해 “이 정도까지는 허용” 이라는 기준

• ε 값을 바꾸면 다른 Pareto 해가 생성됨

• ε 조절 = 목적 간 trade-off 조절

✅ 3. Pareto front를 간접적으로 생성

• ε 값을 단계적으로 변화시키며 문제를 반복 해결

• 각 실행 결과가 하나의 Pareto optimal solution

• 결과적으로 Pareto optimal set / Pareto front 구성

📌 ε-constraint의 절차

✅ 1. 목적함수 정의

• 가장 중요하다고 판단되는 목적함수 하나 선택

예:

f₁(x): 총 비용 최소화

✅ 2. ε 값 설정

• 나머지 목적함수에 대해 허용 가능한 상한 설정

예:

f₂(x) ≤ ε (이동 거리)

f₃(x) ≤ ε₂ (불균형)

✅ 3. 단일 목적 최적화 수행

• 일반적인 최적화 기법 그대로 사용

• LP / MILP / MIP / 휴리스틱 등 적용 가능

✅ 4. ε 값 변경

• ε 값을 바꿔가며 반복 실행

• 서로 다른 Pareto 해 획득

❗ ε-constraint의 구현 방식

✅ 1. 반복 실행 방식

• ε 값을 일정 간격으로 변화

• 각 실행 결과 = 하나의 Pareto solution

• 계산 비용이 큼 (ε 개수 × 최적화 비용)

✅ 2. 적응적 ε 설정

• 이전 해를 기준으로 ε 범위 조정

• 불필요한 영역 탐색 감소

✅ 3. 정수 최적화 문제와 궁합이 좋음

• MIP / MILP와 자연스럽게 결합 가능

• 물류, 네트워크, 스케줄링 문제에 자주 사용

⚠️ ε-constraint의 장단점

✅ 장점

• 모든 Pareto optimal solution 생성 가능

• 비볼록 Pareto front도 탐색 가능

• 가중치 설정 불필요 (해석 직관적)

• 기존 단일 목적 솔버 재사용 가능

❌ 단점

• ε 값 설정이 어려움

• 반복 실행으로 계산 비용 큼

• ε 간격에 따라 Pareto front 품질 달라짐

📝 예제

서로 충돌하는 여러 목적함수(Objectives)를 동시에 고려할 때, 어느 하나의 목적을 개선하면 다른 목적이 반드시 악화되는 해들만을 남겨 최적해 집합을 구하는 방법

단일 최적해가 아니라 파레토 최적해 집합(Pareto optimal set)을 구하는 것이 특징 다목적 최적화(Multi-objective Optimization)의 가장 기본적인 개념

⭐ Pareto Optimality의 핵심 개념

✅ 1. 다목적 최적화 (Multi-objective Optimization)

두 개 이상 목적함수를 동시에 고려

예:

• 비용 최소화 + 서비스 수준 최대화

• 이동 거리 최소화 + 불균형 최소화

• 목적함수들은 일반적으로 서로 상충(trade-off) 관계

✅ 2. 파레토 지배 (Pareto Dominance)

해 A가 해 B를 파레토 지배한다는 의미:

모든 목적함수에서 A가 B보다 같거나 더 좋고 적어도 하나의 목적함수에서는 엄격히 더 좋음

📌 지배 관계 정의

A ≺ B ⇔ ∀i, fᵢ(A) ≤ fᵢ(B) 이고 ∃j, fⱼ(A) < fⱼ(B)

✅ 3. 파레토 최적해 (Pareto Optimal Solution)

• 어떤 다른 해에도 지배되지 않는 해

• 더 이상 “모든 목적에서 동시에 개선”할 수 없는 상태

→ 이런 해들의 집합을 Pareto Set이라 부름

✅ 4. 파레토 프론트 (Pareto Front)

• 목적함수 공간(objective space)에서 파레토 최적해들을 시각화한 경계선/곡면

• 의사결정자는 이 프론트 위에서 자신의 선호(preference)에 맞는 해를 선택

📌 Pareto Optimality의 절차

✅ 1. 목적함수 정의

최적화할 목적함수들을 명확히 정의

예:

f₁(x): 총 비용 f₂(x): 총 이동 거리 f₃(x): 불균형 페널티

✅ 2. 후보 해 생성

가능한 해(solution)들을 생성

방법:

완전 탐색 휴리스틱 / 메타휴리스틱 진화 알고리즘(NSGA-II 등)

✅ 3. 파레토 지배 관계 비교

• 모든 해 쌍에 대해 지배 여부 판단

• 지배되는 해 제거

✅ 4. 파레토 최적해 집합 추출

• 지배되지 않는 해들만 남김

• 결과는 하나의 해가 아닌 해 집합

❗ Pareto Optimality의 구현 방식

✅ 1. 완전 비교 방식 (Brute-force Pareto Filtering)

• 모든 해 쌍을 비교

• 시간복잡도: O(N²)

• 해 개수가 적을 때만 실용적

✅ 2. 메타휴리스틱 기반

• NSGA-II, SPEA2, MOEA/D 등

• 대규모 문제에서 주로 사용

• Pareto front를 점진적으로 근사

✅ 3. ε-constraint / 가중합과의 관계

• Pareto method는 선호를 사전에 강제하지 않음

• ε-constraint, weighted sum은:

  • Pareto 해 중 일부만 탐색

  • 파라미터 설정에 따라 해가 달라짐

⚠️ Pareto Optimality의 장단점

✅ 장점

• 선호 독립적

• 의사결정자의 가중치 없이 해 집합 제공

• Trade-off 구조 명확

• 목적 간 상충 관계를 직관적으로 파악 가능

• 의사결정 유연성

• 사후 선택(post-decision making) 가능

❌ 단점

• 해가 너무 많아질 수 있음

• 고차원 목적함수일수록 Pareto set 폭발

• 최종 선택은 여전히 사람의 몫

• “어떤 해가 가장 좋은가?”는 자동으로 결정 불가

• 계산 비용

• 지배 비교 및 프론트 유지 비용 큼

📝 예제

🔹 다목적 문제 예시

해    비용(cost) ↓    거리(distance) ↓
A    10    100
B    12    80
C    15    70
D    11    120

🔹 파레토 분석

A vs D:

A는 비용↓, 거리↓ → A가 D 지배

A, B, C:

서로 한 목적씩 더 좋음 → 상호 비지배

📌 Pareto optimal set = {A, B, C} 📌 D는 제거됨

🔎 Pareto Optimality의 주요 활용 예시

✅ 1. 물류·운송 최적화

• 비용 최소화 vs 서비스 수준

• 이동 거리 vs 차량 불균형

✅ 2. 공공자전거 재배치 문제

• 총 이동거리 최소화

• 수요 불균형 최소화

• 작업 시간 제약 만족

→ 하나의 해가 아닌 Pareto front 제공 후 정책 선택

✅ 3. 공학 설계 문제

• 무게 vs 강도

• 비용 vs 성능

queuestack의 구조는 다음과 같다. $1$번, $2$번, ... , $N$번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

 $x_0$을 입력받는다.  $x_0$을 $1$번 자료구조에 삽입한 뒤 $1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_1$이라 한다.   $x_1$을 $2$번 자료구조에 삽입한 뒤 $2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_2$이라 한다. ...   $x_{N-1}$을 $N$번 자료구조에 삽입한 뒤 $N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_N$이라 한다.   $x_N$을 리턴한다.

$M$의 수열 $C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다.

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100,000$)

둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다.

셋째 줄에 길이 $N$의 수열 $B$가 주어진다. $B_i$는 $i$번 자료구조에 들어 있는 원소이다. ($1 \leq B_i \leq 1,000,000,000$)

넷째 줄에 삽입할 수열의 길이 $M$이 주어진다. ($1 \leq M \leq 100,000$)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 $M$의 수열 $C$가 주어진다. ($1 \leq C_i \leq 1,000,000,000$)

입력으로 주어지는 모든 수는 정수이다.

📝 예제

입력
4 0 1 1 0 1 2 3 4 3 2 4 7

출력 4 1 2

풀이

도대체 무슨 소리인지 모르겠다. 이게 뭔 소리람.╱(・-・ꐦ)👂╲ 일단 문제부터 이해해보자면 이렇다는 것이다.

N = 4
A = [0, 1, 1, 0]   # 0=큐, 1=스택
B = [1, 2, 3, 4]   # 각 칸의 초기 값
M = 3
C = [2, 4, 7]      # 순서대로 넣을 것들 

일단 C가 2일 때부터 보자

A = [0, 1, 1, 0]   # 0=큐, 1=스택
B = [1, 2, 3, 4] 

[1] 인 상태에다가 C가 2라고 했으니 2를 넣으면 [1,2] queue는 FIFO 이므로 1이 pop되고 [2]가 남는다.

[2] 인 상태에다가 그 전 pop된 값이 1이므로 넣으면 [2,1] stack은 LIFO 이므로 1이 pop되고 [2]가 남는다.

[3] 인 상태에다가 그 전 pop된 값이 1이므로 넣으면 [3,1] stack은 LIFO 이므로 1이 pop되고 [3]이 남는다.

[4] 인 상태에다가 그 전 pop된 값이 1이므로 넣으면 [4,1] queue는 FIFO 이므로 4가 pop되고 [1]이 남는다.

--> C가 2일 때 결과는 4

문제가 이해가 됐으면 그 다음에는 코딩을 해보자.

✅ stack(1) 은 “그냥 통과” → 무시해도 됨 ✅ queue(0) 만 “기존에 있던 값”을 실제로 내보냄

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split())) # 0 = queue, 1 = stack
B = list(map(int, input().split())) # 초기 상태
M = int(input())
C = list(map(int, input().split())) # 넣을 값들


pipe = deque(b for a, b in zip(A, B) if a == 0)

ans = []
for c in C:
    if pipe:
        # 오른쪽(마지막 큐)의 값이 리턴
        ans.append(pipe.pop())
        # 새 입력값은 왼쪽(첫 큐)으로 들어가 저장
        pipe.appendleft(c)
    else:
        # 큐가 하나도 없으면 스택만 있으므로 입력값이 그대로 리턴
        ans.append(c)

print(*ans)

zip(A,B)

A = [0, 1, 1, 0]
B = [1, 2, 3, 4]
for a, b in zip(A, B):
    print(a, b)

0 1
1 2
1 3
0 4

그래프나 트리와 같은 자료 구조에서 한 노드에서 시작해 인접한 노드들을 먼저 모두 탐색하는 알고리즘

• 가까운 노드부터 '수평적으로' 탐색하는 것이 특징

⭐ BFS의 특징

✅ 1. 너비 우선 탐색

• 시작 노드로부터 가까운 노드를 먼저 탐색합니다. 특정 깊이에 있는 모든 노드를 먼저 방문한 후, 다음 깊이로 넘어감

✅ 2. 큐(Queue) 사용

• BFS는 선입선출(FIFO) 구조인 큐(Queue)를 사용
• 큐에 들어간 순서대로 노드를 탐색하므로, 가까운 노드부터 처리할 수 있음

✅ 3. 재귀(Recursion) 사용하지 않음

• 일반적으로 DFS(깊이 우선 탐색)와 달리, BFS는 재귀 호출을 사용하지 않고 반복문(while, for)을 사용하여 구현

✅ 4. 최단 경로 보장

• 모든 간선 가중치가 동일할 때, 시작 노드에서 목표 노드까지의 최단 경로를 항상 보장
• 시작 노드로부터 거리가 1인 모든 노드를 탐색하고, 그다음 거리가 2인 모든 노드를 탐색하는 방식으로 진행되기 때문

DFS는 스택 또는 재귀 사용하고, 최단 경로 보장 불가함

📌 BFS의 단계

✅ 1. 시작점

• 탐색을 시작할 노드를 선택하고 큐에 넣은 뒤, 방문 처리

✅ 2. 노드 탐색

• 큐가 빌 때까지 다음을 반복

✅ 3. 큐에서 꺼내기

• 큐의 맨 앞에서 노드를 하나 꺼내기

✅ 4. 인접 노드 확인

• 꺼낸 노드와 연결된 모든 인접 노드를 확인

✅ 5. 방문 처리 및 큐에 추가

• 아직 방문하지 않은 인접 노드가 있다면, 방문 처리하고 큐에 추가

❗ BFS의 구현

✅ 1. 큐(Queue) 자료 구조를 이용한 구현

• 큐는 먼저 들어간 데이터가 먼저 나오는 FIFO(First-In, First-Out) 방식이므로, 시작 노드로부터 가까운 노드를 먼저 탐색하는 BFS의 원리와 정확히 일치

• 파이썬의 collections.deque는 양방향 큐로, 노드를 넣고 빼는 작업이 매우 효율적이어서 BFS 구현에 자주 사용

• 구현 과정

  • 1. 큐와 방문 집합 초기화: 탐색할 노드를 담을 큐와 이미 방문한 노드를 기록할 방문(visited) 집합을 만듦. 시작 노드를 큐에 넣고 방문 집합에 추가함.
  • 2. 반복문: 큐가 비어 있지 않은 동안 반복
  • 3. 노드 추출: 큐의 맨 앞에서 노드를 하나 꺼냄
  • 4. 인접 노드 탐색: 현재 노드와 연결된 모든 인접 노드를 확인
  • 5. 새 노드 추가: 인접 노드 중 아직 방문하지 않은 노드가 있다면, 해당 노드를 방문 집합에 추가하고 큐의 맨 뒤에 넣음

✅ 2. 재귀(Recursion)를 이용한 구현

• 이론적으로 큐를 전역 변수로 관리하는 방식으로 재귀적인 BFS를 구현할 수 있음
• 매우 비효율적이고 비직관적이기 때문에 실용적인 예시에서는 거의 찾아보기 어려움

일반적인 BFS 구현 방식은 오직 큐를 이용한 반복문 방식임. 다양한 구현 방법을 찾는 경우, 큐를 배열이나 리스트로 구현하는 방법 등을 생각해볼 수 있지만, 근본적인 탐색 원리는 동일함.

⚠️ BFS의 장단점

✅ 장점

• 최단 경로 탐색:

  • 가중치가 없는 그래프에서 최단 거리를 보장
  • BFS는 시작 노드에서부터 한 레벨씩 모든 노드를 탐색하므로, 목표 노드에 처음 도달했을 때의 경로가 가장 짧은 경로가 됨

• 탐색의 안정성:

  • 탐색이 단계별로 확장되기 때문에 특정 깊이 내에서 답을 찾아야 하는 문제에 유리
  • ex) 특정 노드와 3단계 이내로 연결된 모든 노드를 찾고 싶을 때, BFS는 3단계 탐색 후 바로 멈출 수 있어 효율적임

❌ 단점

• 메모리 사용량:

  • 탐색해야 할 그래프의 크기가 크고, 특히 가지가 넓게 퍼지는 경우(가지치기 계수가 큰 경우), 큐에 매우 많은 노드를 저장해야 하므로 메모리를 많이 소비
  • DFS가 주로 스택을 사용하고 한 경로를 깊게 탐색하는 것과 대조적

• 비효율적인 탐색:

  • 만약 목표 노드가 시작 노드로부터 매우 깊은 곳에 위치하거나, 그래프의 한쪽 끝에 있다면, BFS는 불필요하게 넓은 영역을 모두 탐색해야 할 수 있음
  • 이 경우, 한 방향으로 깊게 탐색하는 DFS가 더 효율적일 수 있음

• 가중치 그래프 문제:

  • 간선에 가중치(비용)가 있는 그래프에서는 최단 경로를 보장하지 못함
  • ex) 짧은 거리를 여러 번 거치는 경로가 긴 거리 한 번에 도달하는 경로보다 짧을 수 있는데, BFS는 단순히 단계(레벨)만 고려하기 때문
  • 가중치 그래프의 최단 경로는 다익스트라(Dijkstra)나 벨만-포드(Bellman-Ford) 알고리즘을 사용

📝 예제

BFS를 사용했을 때 탐색 순서는 어떻게 되는가?

   A
  / \
 B   C
 |   |
 D   E
  \ /
   F

다음과 같은 그래프가 있다. 그래프는 노드와 노드 사이의 연결로 이루어져 있다. *너비 우선 탐색(BFS)을 이용해 모든 노드를 방문하는 순서를 구하라. *

조건

• 시작 노드는 A
• 같은 레벨(같은 거리에 있는 노드)부터 방문
• 각 노드는 한 번만 방문

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

1. 시작 노드를 큐에 넣는다.
2. 큐에서 노드를 하나 꺼낸다.
3. 그 노드의 인접한 노드 중 방문하지 않은 노드를 모두 큐에 넣는다.
4. 큐가 빌 때까지 반복

--> 같은 레벨(거리)에 있는 노드들을 먼저 방문하는 방식

from collections import deque  # BFS에서 사용할 큐 자료구조 import

def bfs(graph, start):
    visited = set()        # 이미 방문한 노드를 기록하는 집합
    queue = deque([start]) # BFS는 큐(Queue) 사용, 시작 노드를 넣음
    order = []             # 방문 순서를 저장할 리스트

    while queue:           # 큐가 빌 때까지 반복
        node = queue.popleft()  # 큐에서 가장 앞에 있는 노드를 꺼냄 (FIFO)
        if node not in visited: # 아직 방문하지 않은 노드이면
            visited.add(node)   # 방문 표시
            order.append(node)  # 방문 순서를 리스트에 저장

            # 현재 노드의 인접 노드들을 확인
            # 작은 번호 순서대로 큐에 추가 (옵션: 테스트에서 작은 번호 먼저 방문)
            for neighbor in sorted(graph[node]):
                if neighbor not in visited:  # 이미 방문한 노드는 큐에 넣지 않음
                    queue.append(neighbor)  # 다음에 방문할 노드로 큐에 추가

    return order  # BFS 탐색 순서 반환


# ---------------------
# 입력 처리
# ---------------------
n, m = map(int, input().split())  # 정점 개수(n)와 간선 개수(m) 입력
graph = {i: [] for i in range(1, n+1)}  # 1~n까지의 정점을 키로 하는 빈 리스트 생성

for _ in range(m):
    u, v = map(int, input().split())  # 간선 연결 정보 입력
    graph[u].append(v)                # u->v 연결
    graph[v].append(u)                # v->u 연결 (무방향 그래프)

start = int(input())  # 시작 정점 입력

# BFS 실행
result = bfs(graph, start)
print(' '.join(map(str, result)))  # 방문 순서 출력

적용 결과

1. 시작: 큐에 ['A']를 넣는다. visited는 {'A'}가 된다.
2. 노드 A: 큐에서 A를 꺼낸다. 방문 순서에 A를 추가한다. A의 인접 노드인 B, C를 큐에 넣는다. (알파벳 순으로 정렬되어 있으므로 B가 먼저 들어간다.) 큐는 ['B', 'C']가 된다.
3. 노드 B: 큐에서 B를 꺼낸다. 방문 순서에 B를 추가한다. B의 인접 노드인 D를 큐에 넣습니다. 큐는 ['C', 'D']가 된다.

...

8. 노드 F: 큐에서 F를 꺼낸다. 이미 visited에 있으므로 아무 작업도 하지 않고 건너뛴다. 큐는 비게 된다.
9. 종료: 큐가 비었으므로 반복이 종료된다.

--> 최종 방문 순서는 A -> B -> C -> D -> E -> F

🔎 BFS의 주요 활용 예시

✅ 1. 최단 경로 찾기

BFS의 가장 대표적인 활용 예시로, 가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 찾는 데 사용됨. 이는 BFS가 시작 노드로부터 같은 거리에 있는 모든 노드를 먼저 탐색하는 '너비 우선' 방식 때문.

• 동작 방식
  • 1. 시작 노드: 시작 노드로부터 한 단계씩 거리를 넓혀가며 탐색을 진행. 큐에 현재 레벨의 모든 노드를 넣고, 큐가 빌 때까지 노드를 꺼내고 인접 노드를 큐에 추가하는 과정을 반복.
  • 2. 거리 기록: 각 노드를 방문할 때, 시작 노드로부터의 거리를 기록하면 최단 거리를 쉽게 계산할 수 있음. 예를 들어, 시작 노드의 거리를 0으로 설정하고, 인접 노드의 거리는 현재 노드의 거리 + 1로 설정합니다.

그래프나 트리와 같은 자료 구조에서 한 노드에서 시작해 가능한 한 깊숙이 탐색하는 알고리즘

• 막다른 길에 다다르면 이전 노드로 돌아와(백트래킹) 다른 경로를 탐색하는 방식으로 동작

⭐ DFS의 특징

✅ 1. 깊이 우선 탐색

• 현재 노드에서 방문하지 않은 인접 노드가 있다면, 그 노드로 이동하여 다시 깊이 탐색을 시작
• 더 이상 갈 수 없을 때까지 이 과정을 반복

✅ 2. 백트래킹(Backtracking)

• 막다른 길에 도착하면, 탐색 경로를 거슬러 올라가(백트래킹) 다른 경로를 찾음
• 이를 통해 아직 방문하지 않은 노드를 탐색

✅ 3. 스택 또는 재귀 사용

• DFS는 후입선출(LIFO) 구조의 스택과 유사하게 동작
• 가장 최근에 방문한 노드의 이웃부터 탐색하기 때문에, 명시적인 스택 자료 구조나 재귀 호출 스택을 사용하여 구현할 수 있음

✅ 4. 최단 경로 보장 불가

• DFS는 깊이를 우선적으로 탐색하기 때문에, 시작 노드에서 목표 노드까지의 최단 경로를 보장하지 않음
• 최단 경로를 찾으려면 일반적으로 BFS(너비 우선 탐색)를 사용

📌 DFS의 단계

✅ 1. 시작점

• 그래프의 임의의 한 노드에서 탐색을 시작

✅ 2. 깊이 우선

• 현재 노드와 연결된 방문하지 않은 노드가 있다면, 그 노드로 이동하고 다시 그 노드에서 탐색을 시작
• 이 과정을 더 이상 갈 곳이 없을 때까지 반복

✅ 3. 백트래킹

• 더 이상 방문할 노드가 없는 막다른 길에 도착하면, 이전 노드로 되돌아가(Backtrack) 아직 방문하지 않은 다른 노드가 있는지 확인

✅ 4. 반복

• 모든 노드를 방문할 때까지 이 과정을 반복

이 과정에서 방문했던 노드를 다시 방문하지 않기 위해 방문 여부를 기록하는 배열이나 리스트를 사용

❗ DFS의 구현

✅ 1. 재귀 호출을 이용한 구현

• 가장 직관적인 방법
• 함수가 자기 자신을 호출하는 재귀적인 특성을 활용하여 깊이 우선 탐색을 쉽게 구현할 수 있음

✅ 2. 스택 자료 구조를 이용한 구현

• 재귀 호출 없이 명시적인 스택(Stack)을 사용하여 DFS를 구현할 수도 있음

  • 1. 시작 노드르 스택에 넣고 방문 처리
  • 2. 스택이 빌 때까지 다음 과정 반복
  • 3. 스택에서 노드를 하나 꺼냄
  • 4. 꺼낸 노드와 연결된 방문하지 않은 노드가 있다면 그 노드를 넣고 방문 처리
  • 5. 스택의 LIFO(Last-In, First-Out) 특성 덕분에 가장 최근에 넣은 노드(가장 깊은 노드)부터 탐색하게 되어 DFS가 구현

⚠️ DFS의 장단점

✅ 장점

• 간단한 구현: 특히 재귀를 이용하면 코드가 매우 간결해짐
• 메모리 효율성: 너비 우선 탐색(BFS)에 비해 메모리 사용량이 적음. 한 경로를 탐색하는 동안의 노드들만 스택에 저장하면 되기 때문
• 해 찾기: 깊은 경로에 해답이 있는 경우, BFS보다 빠르게 해를 찾을 수 있음

❌ 단점

• 비효율성: 해답이 시작 노드 근처에 있거나, 탐색 트리의 깊이가 매우 깊은 경우 비효율적일 수 있음. 무한 루프에 빠질 수도 있음

• 최단 경로 보장 X: 시작 노드에서 목표 노드까지의 최단 경로를 보장하지 않음. 최단 경로를 찾으려면 보통 BFS 사용

• 시간 및 공간 복잡도

  • 시간 복잡도: 그래프의 모든 노드와 간선을 한 번씩 방문하므로, 인접 리스트로 구현했을 때 $O(V+E)$, 인접 행렬로 구현했을 때 $O(V^2)$가 됨 (V는 노드의 수, E는 간선의 수)
  • 공간 복잡도: 스택에 저장되는 노드의 수가 최대 그래프의 깊이와 비례하므로 $O(V)$가 됨

📝 예제

모든 노드 방문하기

A -- B
|    |
C -- D

노드 A는 노드 B와 노드 C에 연결 노드 B는 노드 A와 노드 D에 연결 노드 C는 노드 A와 노드 D에 연결 노드 D는 노드 B와 노드 C에 연결

✅ 1. 재귀 DFS

'A'에서 시작해 'A'와 연결된 'B'로 가고, 다시 'B'와 연결된 'D'로 깊숙이 들어감. 'D'에서 더 이상 갈 곳이 없으면 'B'로 돌아와 'C'로 가는 경로를 찾음. 결과적으로 A -> B -> D -> C 순서로 모든 노드를 방문.

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

def dfs_recursive(graph, start_node, visited):
    # 현재 노드 방문 처리
    visited.add(start_node)
    print(start_node, end=' ')

    # 현재 노드와 연결된 모든 노드 탐색
    for neighbor in graph[start_node]:
        # 아직 방문하지 않았다면 재귀 호출
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# 실행 예제
print("재귀 DFS 결과:", end=' ')
visited = set()
dfs_recursive(graph, 'A', visited)
# 출력: 재귀 DFS 결과: A B D C

✅ 2. 스택을 이용한 DFS

재귀와 동일한 원리로 동작하지만, 명시적인 스택을 사용하여 깊이를 탐색. 스택의 LIFO(Last-In, First-Out) 특성을 이용해 가장 최근에 넣은 노드(가장 깊은 노드)부터 꺼내어 탐색. 예시 코드에서는 A -> C -> D -> B 순서로 노드를 방문.

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

def dfs_stack(graph, start_node):
    visited = set()
    stack = [start_node]

    while stack:
        # 스택의 맨 위 노드를 꺼냄 (가장 마지막에 넣은 노드)
        node = stack.pop()

        if node not in visited:
            # 방문 처리
            visited.add(node)
            print(node, end=' ')

            # 인접 노드들을 스택에 넣음.
            # 스택의 특성상 마지막에 넣은 노드부터 탐색하게 됨
            # 여기서는 C가 B보다 먼저 탐색되도록 순서를 뒤집음 (A의 인접 노드: ['B', 'C'])
            # 순서는 결과에 영향을 미치므로 구현에 따라 다를 수 있음
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

# 실행 예제
print("\n스택 DFS 결과:", end=' ')
dfs_stack(graph, 'A')
# 출력: 스택 DFS 결과: A C D B

🔎 DFS의 주요 활용 예시

DFS는 단순히 노드를 방문하는 것 외에 다양한 문제 해결에 활용될 수 있음

✅ 1. 그래프 연결 요소 찾기

DFS는 서로 연결된 노드들의 집합, 즉 연결 요소(Connected Components)를 찾는 데 매우 효과적

• 동작 방식

  • 1. 탐색을 시작한 노드와 방문한 노드를 기록하는 두 가지의 종류의 배열(또는 집합) 사용
  • 2. DFS 탐색 중 현재 노드와 연결된 다음 노드가 이미 '탐색 중인 경로에 포함된 노드(재귀 호출 스택에 있는 노드)'라면, 이는 사이클이 존재한다는 뜻
  • 3. DFS가 한 노드의 모든 이웃을 탐색하고 돌아올 때(백트래킹), 해당 노드를 '탐색 중인 경로'에서 제외

• ex) A -> B -> C -> A와 같이 연결된합니다. C에서 다시 A를 방문하려 할 때, A는 이미 '탐색 중인 경로'에 포함되어 있으므로 사이클이 감지됨.

✅ 2. 사이클(Cycle) 감지

DFS는 그래프에 순환(Cycle) 구조가 있는지 여부를 감지하는 데 유용

• 동작 방식

  • 1. 탐색을 시작한 노드와 방문한 노드를 기록한느 두가지 종류의 배열(또는 집합) 사용
  • 2. DFS 탐색 중 현재 노드와 연결된 다음 노드가 이미 '탐색 중인 경로에 포함된 노드(재귀 호출 스택에 있는 노드)'라면, 이는 사이클이 존재한다는 뜻
  • 3. DFS가 한 노드의 모든 이웃을 탐색하고 돌아올 때(백트래킹), 해당 노드를 '탐색 중인 경로'에서 제외

• ex) A -> B -> C -> A와 같이 연결된 그래프에서, A에서 DFS를 시작하여 B를 거쳐 C로 이동. C에서 다시 A를 방문하려 할 때, A는 이미 '탐색 중인 경로'에 포함되어 있으므로 사이클이 감지됨.

✅ 3. 위상 정렬(Topological Sort)

방향성 비순환 그래프(DAG, Directed Acyclic Graph)의 노드들을, 모든 간선이 정렬된 순서를 따르도록 순서대로 나열하는 것을 위상 정렬이라고 함. DFS를 이용하면 이를 효율적으로 수행할 수 있음.

• 동작 방식

  • 1. 그래프의 모든 노드에 대해 DFS를 실행
  • 2. FS 탐색이 끝나서 '더 이상 방문할 노드가 없는' 상태가 되면, 해당 노드를 결과 목록의 가장 앞쪽에 추가 (또는 리스트의 맨 뒤에 추가한 뒤, 리스트를 뒤집는다.)
  • 3. 이 과정을 반복하면, 모든 선행 노드가 후행 노드보다 먼저 오게 되는 순서를 얻을 수 있음

• ex) 과목 수강 순서와 같은 문제에 적용할 수 있음. 자료구조 과목을 수강해야 알고리즘 과목을 들을 수 있다면, 위상 정렬을 통해 자료구조가 알고리즘보다 먼저 오도록 순서를 정할 수 있음. DFS는 가장 깊숙이 있는(가장 후행하는) 노드부터 처리하기 때문에 이 문제를 해결하기에 적합.

✅ 4. 미로 찾기

미로의 한 지점에서 시작해 막다른 길에 다다를 때까지 한 방향으로 깊게 탐색하는 과정은 DFS와 동일

✅ 5. 백트래킹(Backtracking)

'N-Queens', 스도쿠, 조합 문제 등 해를 찾기 위해 모든 가능성을 탐색하다가 해가 될 수 없는 경로이면 되돌아오는 모든 종류의 문제에 DFS가 기본 원리로 활용

• https://velog.io/@00_deidre_00/Backtracking

백트래킹은 단순히 되돌아가는 것을 넘어, 상태 공간 트리(State Space Tree)를 체계적으로 탐색하며 해답을 찾는 강력한 알고리즘

⭐ Backtracking의 특징

✅ 1. 깊이 우선 탐색(DFS) 기반

• 백트래킹은 상태 공간 트리를 깊이 우선 탐색(DFS) 방식으로 탐색
• 현재 경로를 따라 끝까지 진행하다가 더 이상 해답이 될 수 없는 상황에 이르면 이전 단계로 돌아와 다른 경로를 탐색

DFS(Depth-First Search)란?

• https://velog.io/@00_deidre_00/DFS-Depth-First-Search

✅ 2. 유망성 검사 (Promising Check)

• 현재 경로가 해답으로 이어질 가능성이 있는지 검사합니다. 만약 해가 될 수 없다고 판단되면 더 이상 그 경로를 탐색하지 않고 즉시 되돌아감. 이를 가지치기(Pruning)라고 함

✅ 3. 재귀 호출

• 재귀 함수를 통해 구현되는 경우가 많음
• 각 재귀 호출은 상태 공간 트리의 한 단계 깊이로 이동하는 것을 의미

📌 Backtracking의 단계

✅ 1. 초기 상태

• 문제의 초기 상태를 나타내는 루트 노드에서 탐색을 시작

✅ 2. 후보 선택

• 현재 상태에서 다음 결정을 내릴 수 있는 모든 후보를 고려

✅ 3. 유망성 검사

• 선택한 후보가 해답으로 이어질 가능성이 있는지 확인

✅ 4. 다음 단계 이동

• 만약 유망하다면, 해당 후보를 포함한 새로운 상태로 이동하여 다음 단계의 탐색을 계속 (재귀 호출)

✅ 5. Backtracking

• 만약 후보가 유망하지 않거나, 현재 경로의 끝에 도달했으나 해답을 찾지 못했다면, 이전 상태로 되돌아와 다른 후보를 선택

✅ 6. 종료

• 모든 가능한 경로를 탐색하거나 해답을 찾을 때까지 이 과정을 반복

❗ Backtracking의 구현

✅ 1. 재귀 호출을 이용한 구현

• 백트래킹은 재귀 함수를 사용하여 구현되는 경우가 많음

• 함수는 현재 상태를 인자로 받고, 다음 단계의 모든 후보를 순회하며 자기 자신을 재귀적으로 호출

• 함수 구조

  function backtrack(current_state):
    if is_solution(current_state):
        save_solution(current_state)
        return
  
    for next_candidate in get_candidates(current_state):
        if is_promising(next_candidate):
            backtrack(next_candidate)

✅ 2. 상태 저장 및 복원

• 재귀 호출이 끝난 후, 다음 후보를 탐색하기 위해 이전 상태로 돌아가야 함
• 이는 함수가 반환될 때 자동으로 이루어지거나, 명시적으로 상태를 복원하는 코드를 작성하여 구현

⚠️ Backtracking의 장단점

✅ 장점

• 모든 해답 찾기: 가지치기 기능을 통해 불필요한 탐색을 줄이면서도, 모든 가능한 해답을 찾을 수 있음
• 체계적 탐색: 상태 공간 트리를 깊이 우선 방식으로 체계적으로 탐색하여 문제를 효율적으로 해결

❌ 단점

• 높은 복잡도: 최악의 경우, 모든 가능한 경로를 탐색해야 하므로 시간 복잡도가 매우 높을 수 있음
• 가지치기 의존성: 알고리즘의 효율성은 '유망성 검사'를 통해 얼마나 효과적으로 가지치기를 수행하는지에 달려 있음

📝 예제

N × N 체스판에 N개의 퀸을 서로 공격할 수 없도록 놓는 모든 경우의 수를 찾는 함수

def solve_n_queens(n):
    # 해답을 저장할 리스트
    solutions = []
    # 현재 체스판 상태 (각 행의 퀸 위치를 저장)
    board = [-1] * n

    # 백트래킹 탐색 시작
    backtrack(0, n, board, solutions)
    return solutions

def backtrack(row, n, board, solutions):
    # 5. 해답: 모든 행에 퀸을 놓는 데 성공했다면, 해답을 찾은 것
    if row == n:
        solutions.append(board[:])
        return

    # 2. 다음 단계: 현재 행(row)의 모든 열(col)에 대해 퀸을 놓아보기
    for col in range(n):
        # 3. 유망성 검사: 현재 위치(row, col)가 유망한지 확인
        if is_promising(row, col, board):
            # 퀸을 현재 위치에 놓음
            board[row] = col
            # 4. 다음 행으로 이동하여 재귀 호출
            backtrack(row + 1, n, board, solutions)
            # 백트래킹이 일어난 후, 다음 열을 시도하기 위해 상태 복원
            # board[row]는 다음 반복에서 덮어쓰여지므로 명시적 복원 불필요

def is_promising(row, col, board):
    # 이전 행들을 검사하며 퀸의 위치를 확인
    for prev_row in range(row):
        # 같은 열에 퀸이 있는지 확인
        if board[prev_row] == col:
            return False
        # 대각선에 퀸이 있는지 확인 (row 간 거리 == col 간 거리)
        if abs(board[prev_row] - col) == abs(prev_row - row):
            return False
    return True

# 실행 예제: N=4인 경우
n = 4
solutions = solve_n_queens(n)

print(f"N = {n} 일 때, 총 {len(solutions)}개의 해답을 찾았습니다.")
for i, sol in enumerate(solutions):
    print(f"해답 {i+1}: {sol}")
    # 퀸이 놓인 체스판 시각화 (선택 사항)
    for r in range(n):
        row_str = ["."]*n
        row_str[sol[r]] = "Q"
        print(" ".join(row_str))
    print()

1. 시작: 첫 번째 행에 퀸을 놓는 위치를 결정
2. 다음 단계: 다음 행으로 이동하여 퀸을 놓을 수 있는 모든 열을 확인
3. 유망성 검사: 현재 위치가 유망한지(다른 퀸에게 공격받지 않는지) 확인
4. 백트래킹: 만약 유망하지 않다면, 현재 행의 다른 열로 이동하여 다시 시도. 모든 열을 시도했음에도 퀸을 놓을 수 없다면, 이전 행으로 돌아가(백트래킹) 다른 위치를 탐색.
5. 해답: N개의 퀸을 모두 성공적으로 놓으면 하나의 해답을 찾은 것

🔎 Backtracking의 주요 활용 예시

✅ 1. N-Queen 문제

N개의 퀸을 놓는 모든 해를 찾는 문제

✅ 2. 스도쿠

✅ 3. 조합(Combination) 문제

주어진 집합에서 특정 조건을 만족하는 모든 조합을 찾는 문제

✅ 4. 미로 찾기

미로의 출구를 찾는 모든 경로를 탐색하는 문제

미래에 발생할 수 있는 여러 상황이나 결정의 결과를 미리 예측하고 평가하여, 현재의 최적의 행동을 결정하는 탐색 전략

당장의 이득만을 쫓는 탐욕적인 결정이 아닌, 장기적인 관점에서 더 나은 결과를 가져올 수 있는 결정을 내리기 위함

⭐ Lookahead의 특징

✅ 1. 지역 최적점 탈출:

당장 가장 좋은 선택이 장기적으로는 최악의 결과를 초래할 수 있다. Lookahead는 이런 '지역 최적점'에 갇히는 것을 방지하고 더 나은 전역 최적해를 찾을 기회를 제공한다.

✅ 2. 복잡한 의사결정:

여러 가지 선택지가 있고 각 선택이 미래에 다양한 결과를 낳을 때, Lookahead는 복잡한 상황에서 합리적인 판단을 내리는 데 도움을 준다.

✅ 3. 위험 관리:

특정 결정이 가져올 수 있는 잠재적 위험을 미리 파악하고 회피할 수 있게 한다.

📌 Lookahead의 단계

✅ 1. 탐색 트리 구축

현재 상태를 트리의 뿌리로 설정하고, 취할 수 있는 모든 가능한 행동을 탐색하며 트리를 만들어 나간다. 이 과정은 정해진 깊이(Lookahead Depth)까지만 진행된다.

ex) 깊이가 3이라면 현재 상태에서 3단계 앞까지의 모든 가능성들을 가지와 노드로 표현

✅ 2. '말단 노드' 평가

트리의 가장 끝단에 있는 노드들(Lookahead 깊이에 도달한 노드들)에 평가 함수를 적용하여 점수를 매긴다. (이 점수는 해당 노드가 얼마나 유망한 상태인지를 나타내는 추정치)

ex) 체스 AI라면 '상대방의 말이 몇 개 남았고, king이 얼마나 안전한지'와 같은 요소들을 평가하여 점수를 부여

✅ 3. 점수 역전파 (Backpropagation of Scores)

말단 노드에서 얻은 점수를 거꾸로 거슬러 올라가(역전파) 트리의 뿌리까지 전달한다. 이 과정에서 각 층위의 노드들은 자신에게 유리한 선택을 한다.

ex) '나'의 턴(Max player): 내 차례인 노드는 아래 노드들 중 가장 높은 점수를 자신에게 가져온다.

'상대'의 턴(Min player): 상대방의 차례인 노드는 아래 노드들 중 가장 낮은 점수를 자신에게 가져온다 (상대방이 나에게 가장 불리한 선택을 할 것이라고 가정하기 때문).

✅ 4. 최적의 행동 선택

뿌리 노드에 도달한 최종 점수들을 비교하여 가장 높은 점수를 가져온 행동을 현재의 최적의 행동으로 선택한다. 이는 단순히 한 단계 앞의 이득이 아니라, Lookahead 깊이 내에서 상대방의 반격까지 고려한 가장 현명한 선택이 된다.

❗ Lookahead의 구현

✅ 1. 탐색 깊이 (Search Depth)

탐색의 깊이는 몇 수 앞까지 예측할 것인지를 의미

• 깊이가 깊을수록 더 정확한 예측이 가능하지만, 계산량이 기하급수적으로 늘어나기 때문에 시간이 오래 걸림
• 깊이가 얕으면 계산은 빠르지만, 단기적인 최적해에 머물러 장기적인 최적해를 놓칠 수 있음. 따라서 탐색 깊이는 문제의 복잡성과 허용 가능한 시간 사이의 균형을 고려하여 설정해야 함.

✅ 2. 상태 평가 함수 (Evaluation Function)

각 단계에서 탐색한 상태가 얼마나 좋은지 평가하는 함수

• 단순히 현재 상태뿐만 아니라 미래 예측의 결과를 종합적으로 평가하여 최적의 경로를 선택하는 데 결정적인 역할을 함
• 예를 들어, 체스 게임에서 상대방의 왕을 위협하는 상태, 유리한 위치에 있는 말의 수 등을 점수로 환산하여 평가할 수 있음

✅ 3. 탐색 알고리즘

Lookahead는 단독으로 사용되기보다, 미니맥스(Minimax) 알고리즘이나 알파-베타 가지치기(Alpha-Beta Pruning)와 같은 탐색 알고리즘과 결합하여 구현됨

• 미니맥스 (Minimax) 알고리즘

  • '나'의 차례에서는 점수를 최대화(Maximize)하는 수를, '상대방'의 차례에서는 점수를 최소화(Minimize)하는 수를 선택하는 방식으로 탐색
  • 이를 통해 상대방의 최적의 대응을 가정한 상태에서 나의 최적의 수를 찾음

• 알파-베타 가지치기 (Alpha-Beta Pruning)

  • 미니맥스 알고리즘의 비효율성을 개선한 방법
  • 탐색 과정에서 더 이상 최적해가 나올 가능성이 없는 가지(branch)를 미리 잘라내어 탐색 범위를 줄이는 방식
  • 이를 통해 탐색 속도를 비약적으로 향상시킬 수 있음

⚠️ Lookahead의 장단점

✅ 장점

• 전략적 판단: 현재의 이득뿐만 아니라 미래에 발생할 수 있는 여러 상황을 예측하여 더 나은 장기적인 결정을 내릴 수 있음
• 지역 최적해 방지: 단기적으로는 최선이 아닐 수 있지만, 장기적으로 유리한 수를 찾아 지역 최적해(Local Optimum)에 갇히는 것을 방지함
• 상대방의 대응 고려: 미니맥스(Minimax)와 같은 알고리즘과 결합하여 상대방의 최적 대응을 가정한 상태에서 나의 수를 결정하므로, 더 정교하고 방어적인 전략을 세울 수 있음

❌ 단점

• 높은 연산 복잡도: 탐색 깊이가 깊어질수록 고려해야 할 경우의 수가 기하급수적으로 증가합니다. 이로 인해 연산량이 매우 많아져 실행 시간이 길어짐
• 비현실성: 복잡한 문제에서는 모든 경우의 수를 탐색하는 것이 사실상 불가능함
• 평가 함수의 의존성: Lookahead의 성능은 상태 평가 함수가 얼마나 정확하게 미래를 예측하는지에 크게 의존함. 평가 함수가 부실하면 잘못된 결정을 내릴 수 있음.

📝 예제

0부터 시작해서 10에 가장 빨리 도달하는 것. 각 위치에서 +1, +2, +3 이동이 가능하며, 각 이동에는 비용이 든다

# 비용 예시: 이동 거리가 길수록 비용이 높거나, 특정 지점은 비용이 높을 수 있음. 여기서는 간단히 이동 거리를 비용으로 간주

move_costs = {1: 1, 2: 2, 3: 3}

# 목표 지점
TARGET = 10

def evaluate_position(position):
    """
    현재 위치를 평가하는 함수 (목표에 가까울수록 좋음)
    여기서는 목표까지 남은 거리가 짧을수록 좋다고 가정
    """
    return TARGET - position # 남은 거리가 짧을수록 높은 점수 (역으로 해석)

def find_best_move_greedy(current_pos):
    """
    탐욕적인 방식: 한 칸만 보고 가장 좋은 이동 선택
    (여기서는 비용이 가장 적게 드는 이동 = 짧은 이동)
    """
    best_move = -1
    min_cost = float('inf')

    print(f"현재 위치: {current_pos} (탐욕적)")
    for move_distance in [1, 2, 3]:
        cost = move_costs[move_distance]
        if cost < min_cost and current_pos + move_distance <= TARGET:
            min_cost = cost
            best_move = move_distance

    if best_move != -1:
        print(f"  탐욕적 선택: +{best_move} (비용: {min_cost}) -> 다음 위치: {current_pos + best_move}")
    return best_move

def find_best_move_with_lookahead(current_pos, lookahead_depth):
    """
    Lookahead 방식: 주어진 깊이만큼 미래를 예측하여 가장 좋은 이동 선택
    """
    if current_pos == TARGET:
        return 0 # 목표 도달

    best_overall_score = -float('inf') # 더 높은 점수가 좋은 선택 (평가 함수 기준)
    best_initial_move = -1

    print(f"현재 위치: {current_pos} (Lookahead 깊이: {lookahead_depth})")

    for initial_move in [1, 2, 3]:
        next_pos = current_pos + initial_move

        if next_pos > TARGET:
            continue # 목표를 넘어가는 이동은 무시

        current_path_cost = move_costs[initial_move]

        # Lookahead 시뮬레이션
        if lookahead_depth > 0:
            # 재귀적으로 다음 단계 Lookahead 호출 (가장 좋은 다음 이동을 찾음)
            # 여기서는 다음 이동으로 인해 얻을 '미래 가치'를 고려하는 간단한 로직
            # 실제로는 Minimax나 Alpha-Beta Pruning 같은 알고리즘이 사용될 수 있음
            future_value_score = evaluate_position(next_pos) # 다음 위치의 예상 가치

            # 미래 경로를 더 깊이 탐색하는 로직 (간단화)
            # 예를 들어, 다음 스텝에서 또 다시 Lookahead를 수행하여 미래 점수 합산
            if next_pos < TARGET:
                # 다음 스텝에서 얻을 수 있는 최대 점수를 대략적으로 예측
                # (실제로는 복잡한 탐색 트리를 구성하고 모든 경로를 평가)
                # 여기서는 단순히 다음 스텝의 평가 점수를 추가
                future_value_score += evaluate_position(next_pos + 1) # 예시로 한 스텝 더 예측
                if lookahead_depth > 1:
                    future_value_score += evaluate_position(next_pos + 2) # 더 깊이 예측하는 흉내


            # 현재 이동 비용과 미래 가치를 결합하여 이 행동의 최종 점수 계산
            # (점수는 높을수록 좋고, 비용은 낮을수록 좋으므로, 비용을 점수에서 뺌)
            overall_score_for_this_move = future_value_score - current_path_cost
        else: # Lookahead 깊이가 0이면 현재 위치만 평가 (탐욕적과 유사)
            overall_score_for_this_move = evaluate_position(next_pos) - current_path_cost


        print(f"  +{initial_move} 선택 시 예상 점수 (비용 포함): {overall_score_for_this_move:.2f}")

        if overall_score_for_this_move > best_overall_score:
            best_overall_score = overall_score_for_this_move
            best_initial_move = initial_move

    if best_initial_move != -1:
        print(f"  Lookahead 선택: +{best_initial_move} (예상 점수: {best_overall_score:.2f}) -> 다음 위치: {current_pos + best_initial_move}")
    return best_initial_move

print("--- 탐욕적 방식 ---")
current_position = 0
while current_position < TARGET:
    move = find_best_move_greedy(current_position)
    if move == -1: # 더 이상 움직일 수 없을 때
        print("더 이상 움직일 수 없습니다.")
        break
    current_position += move
print(f"최종 위치: {current_position}\n")


print("--- Lookahead 방식 (깊이 1) ---")
current_position = 0
while current_position < TARGET:
    move = find_best_move_with_lookahead(current_position, lookahead_depth=1)
    if move == -1:
        print("더 이상 움직일 수 없습니다.")
        break
    current_position += move
print(f"최종 위치: {current_position}\n")


print("--- Lookahead 방식 (깊이 2) ---")
current_position = 0
while current_position < TARGET:
    move = find_best_move_with_lookahead(current_position, lookahead_depth=2)
    if move == -1:
        print("더 이상 움직일 수 없습니다.")
        break
    current_position += move
print(f"최종 위치: {current_position}\n")

🔎 Lookahead의 주요 활용 예시

✅ 1. 게임 인공지능 (Game AI)

체스, 바둑, 틱택토와 같은 보드 게임에서 컴퓨터가 다음 수를 결정할 때 사용. Lookahead를 통해 몇 수 앞의 상황을 미리 예측하여 상대방의 대응까지 고려한 최적의 수를 찾음.

• 동작 방식

  • 미니맥스(Minimax)나 알파-베타 가지치기(Alpha-Beta Pruning)와 같은 알고리즘을 사용
  • 내가 최적의 수를 두었을 때 상대방도 최적의 대응을 할 것을 가정하여 탐색

• ex) 체스 게임에서 룩어헤드를 사용하면, 단순히 현재 폰을 잡는 수가 아니라, 몇 수 뒤에 상대방의 퀸을 잡을 수 있는 더 유리한 경로를 찾아낼 수 있음

✅ 2. 경로 계획 및 탐색

로봇 공학이나 자율 주행 차량에서 최적의 경로를 찾거나 장애물을 피할 때 사용되는 전략

• 동작 방식

  • 현재 위치에서 몇 초 후의 로봇 위치나 주변 환경의 변화를 미리 예측하고, 그 예측을 바탕으로 충돌 위험이 가장 적고 목표에 빠르게 도달할 수 있는 경로를 선택

• ex) 자율 주행 차량이 교차로에서 좌회전할 때, 반대편에서 오는 차량의 속도를 예측하여 충돌이 발생하지 않는 최적의 진입 시점을 결정

✅ 3. 스케줄링 및 자원 할당

복잡한 작업 스케줄링이나 자원 할당 문제에서 발생할 수 있는 병목 현상이나 비효율성을 미리 예측하여 최적의 계획을 세움

• 동작방식

  • 각 작업의 우선순위와 소요 시간을 기반으로 다양한 스케줄 시나리오를 미리 탐색하고, 가장 효율적인 스케줄을 찾아냄

• ex) 공장의 생산 라인에서 작업을 배정할 때, 특정 기계에 부하가 집중될 경우를 미리 예측하여 이를 방지하고 전체 생산 효율을 높이는 스케줄을 만듦

현재 해(solution)에서 더 나은 해를 찾기 위해 주변을 탐색하는 방식

• 단순히 가장 좋은 해만 따라가는 '탐욕적(greedy)' 알고리즘의 단점을 보완하기 위해 '금기 목록(tabu list)'이라는 개념을 도입한 것이 특징

https://medium.com/the-modern-scientist/exploring-the-efficiency-of-tabu-search-in-optimization-problems-c72833873c31

⭐ Tabu Search의 특징

✅ 1. 지역 최적해(Local Optimum) 탈출

• Greedy algorithm이 매 순간 가장 좋은 해를 따라가다 보면 더 이상 개선할 수 없는 지역 최적해에 갇히게 됨

✅ 2. 금기 목록(Tabu List) 사용

• 최근에 시도했던 이동이나 방문했던 해를 일정 기간 동안 '금지' 상태로 저장하는 메모리 구조
• 일반적으로 FIFO(선입선출) 구조를 가지며, 매 반복마다 가장 오래된 항목이 삭제되고 새로운 항목이 추가됨

✅ 3. 예외 조건(Aspiration Criteria)

• 타부 리스트에 금지된 이동이라도, 만약 그 이동이 지금까지 찾은 최적해보다 더 좋은 해로 이어진다면 예외적으로 허용
• 이러한 예외 조건을 통해 알고리즘의 유연성을 높여 탐색 효율을 개선

✅ 4. 집중화(Intensification)와 다양화(Diversification)

• 집중화: 현재까지 찾은 좋은 해 주변을 집중적으로 탐색하여 해의 품질을 높임
• 다양화: 탐색이 정체될 때, 아직 탐색하지 않은 새로운 영역을 탐색하여 더 나은 해를 찾을 기회를 만듦

📌 Tabu Search의 단계

✅ 1. 시작점 (Starting Point)

• 알고리즘은 일반적으로 무작위 또는 간단한 휴리스틱 기반윽로 초기 해를 선택하며 시작

✅ 2. 이웃 탐색 (Neighborhood Search)

• 각 단계에서 현재 해의 이웃(neighborhood)을 탐색
• neighborhood: 현재 해에서 작은 변화를 준 해들

✅ 3. 타부 리스트 (Tabu List)

• 리스트에 일시적으로 금지된 이동(move) 또는 해(solution)들이 저장됨
• 최근에 방문한 해를 다시 선택하는 것을 방지하여, 지역 최적해에서 벗어나도록 함

✅ 4. 예외 조건 (Aspiration Criteria)

• 때로는 Tabu list에 포함된 이동이 매우 좋은 해로 이어질 수 있음
• -> 이 때 예외적으로 허용됨

✅ 5. 종료 조건 (Stopping Criteria)

• 알고리즘은 다음 조건 중 하나를 만족할 때까지 반복됨
  • 정해진 반복 횟수 도달
  • 시간 제한 초과
  • 더 이상 개선되지 않음

✅ 6. 기억 구조 (Memory Structures)

• 탐색 과정의 정보를 저장하는 메모리 구조를 사용
  • 단기 기억(short-term memeory): Tabu list (최근 이동 저장)
  • 장기 기억(long-term memory): 과거에 찾은 좋은 해에 대한 정보 저장

✅ 7. 집중화와 다양화 (Intensification & Diversification)

• 좋은 해 주변을 집중적으로 탐색 (Intensification)
• 새로운 영역 탐색 (Diversification)
• -> 해의 품질 향상

일반적으로 FIFO (first in first out) 구조로 매 반복마다 갱신됨

❗ Tabu Search의 구현

✅ 1. 단기 기억 (Short-Term Memory)을 이용한 구현

가장 기본적인 구현 방식으로, 금기 목록(Tabu List)이 여기에 해당함

• 목적: 최근해 방문한 해(solution)나 이동(move)을 일시적으로 금지하여 탐색이 같은 경로를 반복하는 순환(cycle) 현상을 막고, 지역 최적해에 갇히는 것을 방지함
• 구현: 일반적으로 큐(Queue) 또는 덱(Deque)과 같은 FIFO(First-In, First-Out) 자료 구조를 사용. 새로운 이동이 발생하면 리스트에 추가하고, 리스트의 크기가 정해진 금기 지속 기간(Tabu Tenure)을 초과하면 가장 오래된 항목을 삭제하는 방식

✅ 2. 장기 기억 (Long-Term Memory)을 이용한 구현

탐색의 효율성을 높이기 위해 더 복잡한 전략을 사용하는 고급 구현 방식

• 목적: 탐색이 너무 한 곳에만 치우치는 것을 방지하고, 새로운 탐색 영역으로 확장하여 전역 최적해를 찾을 가능성을 높임

• 구현

  • 빈도 기억(Frequency Memory): 특정 이동이나 해가 너무 자주 선택되었을 경우, 다음에 선택될 가능성을 낮추는 방식으로 탐색의 다양성(Diversification)을 높임
  • 집중화(Intensification): 반대로 좋은 해가 발견된 영역 주변을 더 집중적으로 탐색하여 해의 품질을 향상
  • 재시작 전략: 탐색이 더 이상 진전되지 않을 때, 이전에 찾았던 좋은 해를 기반으로 다시 탐색을 시작하여 새로운 경로를 모색

⚠️ Tabu Search의 장단점

✅ 장점

• 지역 최적해 탈출: 타부 리스트를 통해 이미 방문했던 경로로 다시 돌아가지 않도록 금지함으로써, 지역 최적해(Local Optimum)에 갇히는 것을 방지하고 더 넓은 탐색 공간을 탐험할 수 있게 함.
• 효율적인 탐색: 그리디 알고리즘의 탐욕적인 접근 방식은 유지하면서도, 금기 목록과 예외 조건 등을 통해 무작위 탐색보다 더 체계적으로 최적해를 찾아감

❌ 단점

• 매개변수 튜닝: 타부 리스트의 크기(Tabu Tenure)와 같은 매개변수를 문제에 맞게 조절해야 함. 이 값이 너무 작으면 지역 최적해에 빠지기 쉽고, 너무 크면 비효율적인 탐색이 될 수 있음.

• 복잡성: 리디 알고리즘에 비해 구현이 복잡하고, 메모리 구조(단기/장기 기억)와 같은 추가적인 개념을 고려해야 함

📝예제

리스트 내 숫자 조합 중 합이 최소가 되는 해를 찾기

import random
from collections import deque

def objective(solution):
    # 목적 함수: 합이 작을수록 좋음
    return sum(solution)

def generate_neighbors(solution):
    # 이웃 해 생성: 랜덤한 위치 2개를 바꾼다
    neighbors = []
    for _ in range(10):
        new_solution = solution.copy()
        i, j = random.sample(range(len(solution)), 2)
        new_solution[i], new_solution[j] = new_solution[j], new_solution[i]
        neighbors.append(new_solution)
    return neighbors

def tabu_search(initial_solution, max_iter=100, tabu_size=10):
    current_solution = initial_solution
    best_solution = current_solution
    best_score = objective(best_solution)

    tabu_list = deque(maxlen=tabu_size)

    for iteration in range(max_iter):
        neighbors = generate_neighbors(current_solution)
        neighbors = [n for n in neighbors if n not in tabu_list]

        if not neighbors:
            break

        neighbor_scores = [(n, objective(n)) for n in neighbors]
        next_solution, next_score = min(neighbor_scores, key=lambda x: x[1])

        # Aspiration Criteria: 좋은 해면 Tabu여도 허용
        if next_score < best_score:
            best_solution = next_solution
            best_score = next_score

        tabu_list.append(next_solution)
        current_solution = next_solution

        print(f"Iter {iteration+1}: best_score = {best_score}")

    return best_solution, best_score

# 초기 해: 1~10의 무작위 순열
initial = random.sample(range(1, 11), 10)

best_solution, best_score = tabu_search(initial, max_iter=50, tabu_size=5)

print("\nBest solution:", best_solution)
print("Best score:", best_score)

🔎 Tabu Search의 주요 활용 예시

✅ 1. 외판원 문제 (Traveling Salesman Problem, TSP)

여러 도시를 한 번씩 방문하고 시작점으로 돌아오는 가장 짧은 경로를 찾는 문제로, 이는 전형적인 NP-하드 문제로, 모든 경우의 수를 확인하기 어려움

• 동작 방식

  • 1. 현재 경로에서 두 도시의 순서를 바꾸는 것을 '이동'으로 간주.
  • 2. 과거에 시도했던 비효율적인 이동들을 금지 목록 (Tabu list)에 넣어 반복을 피하고, 더 넓은 탐색 공간을 효율적으로 탐색하여 최단 경로를 찾음.

• ex) 100개의 도시를 방문하는 최단 경로를 찾을 때, 모든 경로를 계산하는 대신 Tabu Search를 사용하면 현실적인 시간 안에 좋은 근사 해 얻을 수 있음.

✅ 2. 스케줄링 문제

작업 할당, 생산 계획, 항공기 이착륙 시간 배정 등 복잡한 제약 조건이 있는 스케줄링에서 최적의 해를 찾는 문제

• 동작 방식

  • 1. Tabu Search는 현재 스케줄에서 작업을 재배치하는 것을 '이동'으로 봄
  • 2. 이미 시도했던 비효율적인 재배치들을 금지하여 더 나은 스케줄을 탐색

• ex) 공장에서 여러 기계에 작업을 할당하여 전체 생산 시간을 최소화하는 문제를 해결할 때, 타부 서치를 사용해 최적의 작업 순서를 찾음

✅ 3. 네트워크 설계

통신망에서 가장 효율적인 연결망을 구축하거나, 물류 네트워크에서 운송 비용을 최소화하는 경로를 설계하는 문제

• 동작 방식

  • 네트워크 구성 요소를 변경하는 것을 '이동'으로 간주하여 최적의 네트워크 구조를 찾음

• ex) 물류 회사가 배송 지점 간의 최단 경로를 찾거나, 통신 회사가 기지국을 설치할 최적의 위치를 결정할 때 사용할 수 있음

✅ 4. 포트폴리오 최적화

주어진 자산들로 수익은 최대화하면서 위험은 최소화하는 투자 포트폴리오를 구성하는 문제

• 동작 방식

  • 포트폴리오의 자산 구성을 변경하는 것을 '이동'으로 보고, 과거의 비효율적인 자산 조합을 금지하여 더 나은 포트폴리오를 찾음

• ex) 주식, 채권, 부동산 등 다양한 자산에 투자할 때, 타부 서치를 이용해 투자 비율을 조정함으로써 기대 수익률을 높이고 위험을 관리하는 최적의 포트폴리오를 찾을 수 있음

📑 용어 설명

Tabu list

• 최근 수행한 이동들을 기록하는 단기 기억 장치
• Closed list, 이전에 방문한 해를 다시 탐색하지 않도록 함

Tabu Tenure (Tabu 지속 기간)

• 한 번 Tabu 리스트에 들어간 이동이 금지되는 횟수
• 이 기간이 지나기 전에는 같은 이동을 다시 시도할 수 없음

Frequency Memory (빈도 기억 장치)

• 너무 자주 선택되었지만 해결책에 도움이 되지 않은 이동은 다음에 선택될 가능성을 낮춤
• 탐색 다양성을 높이기 위한 전략

매 순간 가장 최적의 선택을 하는 방식으로 문제를 해결하는 알고리즘

⭐ Greedy algorithm의 특징

✅ 1. 현재 최선의 선택

그리디 알고리즘은 문제를 해결하는 동안 각 단계에서 가장 최적인 선택을 함

✅ 2. 전역적 최적해는 보장되지 않음

그리디 알고리즘은 각 단계에서 최적의 선택을 하지만, 그 선택들이 전체적으로 최적의 해를 보장하지 않음

✅ 3. 단계적 해결

문제를 작은 하위 문제로 나누고 각 하위 문제를 해결하면서 점진적으로 전체 문제를 해결함

✅ 4. 단일 선택

한 번 선택된 값은 변경되지 않으며, 후속 단계에서 그 값을 바꾸지 않음

❗Greedy algorithm의 구현

✅ 1. 정렬을 통한 구현

• 가장 많이 사용되는 구현 방식 중 하나
• ex) 크루스칼 알고리즘처럼 간선을 가중치 순으로 정렬하거나, 회의실 배정 문제처럼 종료 시간을 기준으로 정렬한 후 순서대로 선택하는 경우가 많음

✅ 2. 반복문을 통한 구현

• 보통 for 또는 while 반복문을 통해 각 단계마다 greedy 선택을 수행함.
• ex) 거스름돈 문제에서 동전의 종류를 순회하며 동전의 게수를 세는 방식

⚠️ Greedy algorithm의 장단점

✅ 장점

• 간단함: 복잡한 사고 과정 없이 현재 상황에서 가장 좋은 선택을 하기 때문에 알고리즘의 구현이 매우 쉽고 직관적임

• 효율성: 동적 계획법처럼 모든 경우의 수를 고려하지 않고, 한 번의 선택만 하기 때문에 실행 시간이 빠르며 메모리도 적게 사용

❌ 단점

• 최적의 해를 보장하지 않음: 가장 큰 단점은 매 순간의 최적 선택이 최종적으로 전체 문제의 최적 해를 보장하지 못할 수 있다는 점

• ** 적용 가능성 제한**: 그리디 알고리즘이 항상 최적의 해를 보장하는 문제는 '탐욕적 선택 속성'과 '최적 부분 구조'라는 특정 조건을 만족해야만 함. 이 조건이 충족되지 않는 문제에는 적용하기 어려움.

📝 예제

500원, 100원, 50원, 10원 동전으로 거스름돈 N원을 최소한의 개수로 거슬러주는 방법

N = 1260
count = 0
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += N // coin  # 해당 동전으로 거슬러줄 수 있는 개수
    N %= coin  # 남은 금액

print(count)  # 출력: 6

🔎 Greedy algorithm의 주요 활용 예시

✅ 1. 거스름돈 문제

거스름돈을 줄 때 동전의 개수를 최소화하는 문제

• 동작 방식

  • 가장 큰 단위의 동전부터 거슬러 주는 방법.
  • 동전의 단위가 큰 것부터 작은 것으로 정렬되어 있다면, 매 순간 남은 금액에 대해 가장 큰 동전을 선택하는 것이 최적의 해 보장.

• ex) 1260원을 거슬러줘야 할 때, 500원, 100원, 50원, 10원 동전이 있다면, 500원 2개, 100원 2개, 50원 1개, 10원 1개를 주게 됨.

✅ 2. 최소 신장 트리 (Minimum Spanning Tree, MST)

그래프의 모든 노드를 연결하면서 간선 가중치의 합이 최소가 되는 트리를 찾는 문제 (그래프에서 일부 간선을 선택해서 만든 트리)

• 동작 방식

  • Kruskal algorithm 과 같이, 모든 간선을 가중치에 따라 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 선에서 가장 가중치가 낮은 간선부터 하나씩 추가하는 방식으로 해결
  • 매 순간 가장 가중치가 낮은 간선을 선택하는 것이 최적의 해 보장

✅ 3. 최단 경로 문제

특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 문제

• 동작 방식

  • Dijkstra algorithm은 매 단계마다 방문하지 않은 노드 중에서 시작점으로부터의 거리가 가장 짧은 노드를 선택하는 Greedy 방식 사용
  • 가중치가 음수가 아닌 그래프에서 최적해를 찾아냄

✅ 4. Huffman Coding

데이터 압축에 사용되는 알고리즘으로, 문자의 빈도수를 기반으로 코드를 할당하여 압축률을 높이는 문제

• 동작 방식

  • 등장 빈도가 가장 낮은 두 문자를 선택하여 이진 트리를 만들고, 이 과정을 반복하여 최종적인 코드 생성
  • 가장 효율적인 압축 코드 만듦

dict.get(key, default)

key: 찾고 싶은 키 (예: 10, -10 등)

default: (선택) 그 키가 없을 때 대신 줄 값 (기본은 None)

결과: 딕셔너리에 해당 키가 있으면 값을 반환, 없으면 default 값을 반환

my_dict = {'apple': 3, 'banana': 5}

print(my_dict.get('apple'))     # 출력: 3
print(my_dict.get('orange'))    # 출력: None (기본값은 None)

my_dict = {'apple': 3, 'banana': 5}

print(my_dict.get('apple', 0))     # 출력: 3
print(my_dict.get('orange', 0))    # 출력: 0

📌 #27 stack

후입선출(Last-In-First-Out, LIFO) 구조의 자료구조 가장 마지막에 들어간 데이터가 가장 먼저 나온다

push(X): X를 스택에 넣음

pop(): 스택에서 가장 위에 있는 값을 제거하고 반환없으면 오류(-1).

top(): 스택의 가장 위에 있는 값을 단순히 반환 (pop과 달리 제거하지 않음)

size(): 스택에 있는 원소의 개수를 반환

empty(): 스택이 비어 있으면 1, 아니면 0을 반환

📌 #28 queue

선입선출(Fist-In-First-Out, FIFO) 구조의 자료구조 가장 먼저 들어간 데이터가 가장 먼저 나온다

enqueue(): 큐의 뒤쪽(back)에 데이터를 추가

dequeue(): 큐의 앞쪽(front)에서 데이터를 꺼냄

front(): 큐의 가장 앞에 있는 데이터 확인 (제거는 안 함)

back(): 큐의 가장 뒤에 있는 데이터 확인

empty(): 큐가 비어 있는지 확인

size(): 큐에 있는 데이터 개수 확인

from collections import deque

q = deque()

q.append(1)     # enqueue
q.append(2)

print(q.popleft())  # dequeue → 1
print(q.popleft())  # dequeue → 2

print(len(q))       # size
print(not q)        # empty (True면 큐가 비어있음)

📌 #29 dequeue

"double-ended queue" (양쪽 끝이 열려 있는 큐)

즉, 데이터를 앞(front)에서도 뒤(back)에서도 빠르게 추가하거나 제거할 수 있는 자료구조

from collections import deque

append(x) 오른쪽(뒤)에 x 추가

appendleft(x) 왼쪽(앞)에 x 추가

pop() 오른쪽(뒤)에서 제거해서 반환

popleft() 왼쪽(앞)에서 제거해서 반환

extend(iterable) 여러 개를 오른쪽(뒤)에 추가

extendleft(iterable) 여러 개를 왼쪽(앞)에 추가 (순서 반대로 들어감)

clear() 모든 요소 제거

rotate(n) 양수면 오른쪽으로 회전, 음수면 왼쪽으로 회전

from collections import deque

dq = deque()

dq.append(1)        # [1]
dq.append(2)        # [1, 2]
dq.appendleft(0)    # [0, 1, 2]

print(dq.pop())     # 2  → [0, 1]
print(dq.popleft()) # 0  → [1]

print(dq)           # deque([1])

📌 #30 startswith()

문자열이 특정 문자열로 시작하는지 확인하는 메서드 ✔ 결과는 True 또는 False (논리형)으로 반환

str.startswith(prefix[, start[, end]])

prefix: 시작을 확인할 문자열 또는 튜플 (ex: "push", ("a", "b")) start (선택): 검사 시작 인덱스 end (선택): 검사 종료 인덱스

s = "hello world"

print(s.startswith("world", 6))      # True → 인덱스 6부터 검사
print(s.startswith("hello", 6))      # False

📌 #31 endswith()

📌 #32 deque.rotate(n)

deque의 원소들을 n만큼 회전시키는 함수

양수 n: 오른쪽으로 n칸 회전 음수 n: 왼쪽으로 n칸 회전

from collections import deque

dq = deque([1, 2, 3, 4, 5])

dq.rotate(1)
print(dq)  # 출력: deque([5, 1, 2, 3, 4])

dq.rotate(-2)
print(dq)  # 출력: deque([2, 3, 4, 5, 1])

오름차순 정렬

num.sort()

내림차순 정렬

num.sort(reverse = True)

📌 #24 combinations

from itertools import combinations

combinations(iterable, r)

iterable: 조합을 만들고자 하는 iterable 객체 (list, tuple) r: 만들고자 하는 조합의 크기 (길이)

numbers = [1, 2, 3]
result = combinations(numbers, 2)

for comb in result:
    print(comb)

--> (1, 2), (1, 3), (2, 3)

📌 #25 sort(key=lambda x: ...)

key = 함수

리스트의 각 요소에 함수를 적용해서 그 결과 기준으로 정렬

words = ['apple', 'banana', 'kiwi']
words.sort(key=len)  # 문자열 길이 기준으로 정렬
print(words)  

--> ['kiwi', 'apple', 'banana']

lambda

이름 없는 함수를 만드는 방법

lambda x: x[0]

sort(key=lambda x: ...)

members = [(21, 'Junkyu'), (21, 'Dohyun'), (20, 'Sunyoung')]
members.sort(key=lambda x: x[0])

x[0] 즉 나이만 기준으로 정렬 

• 여러 기준

  words = ['apple', 'banana', 'kiwi', 'pear']
  words.sort(key=lambda x: (len(x), x))
  print(words)
  # ['kiwi', 'pear', 'apple', 'banana']
  

(길이, 알파벳순) 튜플 기준 정렬

### 📌 #26 in enumerate

반복 가능한(iterable) 객체를 순회할 때, 인덱스와 값을 함께 얻고 싶을 때 사용

for index, value in enumerate(반복가능한객체):

students = ['철수', '영희', '민수'] for i, student in enumerate(students): print(i, student)

0 철수
1 영희
2 민수

만약 1부터 시작하고 싶으면 

for i, student in enumerate(students, start=1): print(i, student)

1 철수
2 영희
3 민수

```

📌 #16 list 안의 정수에다가 계산하기

A = list(map(int, input().split()))
C = [(B / M) * 100 for B in A]

📌 #17 아스키 코드

ord(A)

📌 #18 find

S.find(char)

find(char)는 문자열 S에서 문자 char가 처음 등장하는 위치(인덱스)를 반환한다. 만약 char가 S에 존재하지 않으면 -1을 반환한다.

alphabet = 'abcd'
result = []

for char in alphabet:
    result.append(str(S.find(char)))

📌 #19 strip()

문자열 양쪽의 공백을 제거

input().strip()

📌 #20 split()

공백을 기준으로 문자열을 나누어 단어 리스트 생성 연속된 공백은 자동으로 제거

input().split()

📌 #21 reverse 랑 [::-1] 의 차이

✅ reverse

• list 에서만 사용 가능, 문자열에서는 사용 불가능

  my_list.reverse()

✅ [::-1]

문자열을 포함한 모든 iterable 객체에서 사용 가능

my_list[::-1]

📌 #22 여러 줄 한꺼번에 입력

import sys
print(sys.stdin.read(), end="")

join()을 사용할 때 리스트의 모든 요소는 문자열이어야 한다.

"구분자".join(리스트)

words = ["Hello", "World", "Python"]
result = " ".join(words)  # 각 단어를 공백으로 연결
print(result)

-> Hello World Python

📌 #10 x개의 숫자 입력

numbers = [int(input()) for _ in range(x)]

📌 #11 index

list.index(value, start, end)

value: 찾고자 하는 값. 이 값이 리스트에 있으면 그 위치를 반환한다. start (옵션): 검색을 시작할 인덱스를 지정. 기본값은 0 end (옵션): 검색을 종료할 인덱스를 지정. 기본값은 리스트의 끝.

numbers = [10, 20, 30, 40, 50]

index_of_30 = numbers.index(30)  # 30이 있는 위치를 반환
print(index_of_30)  

-> 2

📌 #12 길이가 N인 list 생성

👉 한 개의 숫자로 N 길이의 list 생성

N = 5
list1 = [0] * N  #길이가 N인 리스트를 생성, 모든 원소를 0으로 초기화
print(list)1

-> [0, 0, 0, 0, 0]

👉 1부터 N까지의 숫자로 N 길이의 list 생성

list2 = list(range(1, N + 1))

📌 #13 list를 string으로

print(" ".join(map(str, list)))

-> 1 2 1 1 0

print(list)

-> [1, 2, 1, 1, 0]

📌 #14 list & set 조작 메서드 비교

range (start, stop, step)

start: 시작값 
stop: 종료값 (포함되지 않음)
step: 지정하지 않으면 1 (step 만큼 증가)

📌 #6 += -=

x += y 
x = x + y

x -= y
x = x - y


    n = int(input())
    total = 0

    for i in range (1, 1+n):
        total += i 
    print (total)

📌 #7 sys.stdin.readline

input은 여러 줄 입력받으면 시간이 오래 걸린다. 그에 비해 sys.stdin.readline은 입력을 더 빠르게 받는다.

한 줄에 여러 개 입력받아 저장 

    import sys
    a,b = map(int, sys.stdin.readline().split())

n 줄 입력받아 저장 

    import sys
    n = int(sys.stdin.readline())
    data = [sys.stdin.readline().strip() for i in range(n)]

n 줄에서 여러 개 입력받아 저장 

    import sys
    n = int(sys.stdin.readline())
    for i in range(n):
        a, b = map(int, sys.stdin.readline().split())
        print (a+b)

📌 #8 무한 루프 while True

while True:
    a, b = map(int, input().split()) 
    if a == 0 and b == 0:  # 입력이 "0 0"이면 종료
        break
    print(a + b)  # A + B 출력

👉 break 조건이 없으면 무한루프가 되기 때문에 try except 사용

while True:
    try:
        a, b = map(int, input().split())  
        print(a + b)  
    except EOFError:  # 입력이 끝나면 루프 종료
        break

H, M = map(int, input().split())

2 5 를 입력했다면 2가 H, 5가 M에 입력된다.

    H, M = input().split()
    H = int(H)
    M = int(M)
    # map 없이도 사용 가능 

📌 #2 / , // , %

👉 1. / (나눗셈, 실수 반환)

• 항상 실수 (float) 결과를 반환
• 소수점 이하까지 계산

  print(10 / 3) -> 3.3333333333333335

👉 2. // (몫 연산, 정수 또는 실수 몫 반환)

• 결과는 정수 또는 실수
• 소수점 이하 버림

  print(10 // 3)  -> 3

👉 3. % (나머지 연산)

• 나눗셈 후 나머지 반환
• 부호는 피제수를 따름

  print(10 % 3)  -> 1

📌 #3 prefix

👉 1. f (f-string) 문자열 안에 변수 삽입

    name = "Alice"
    age = 25

    print(f"이름: {name}, 나이: {age}")

• ✅f-string 형식

  f"{변수명:형식}"
  

✅ 소수점 자리수 고정 출력

f"{변수명:.nf}"

num = 3.1415926535 print(f"{num:.2f}") # 소수점 2자리

-> 3.14

👉 2. r (raw string) 이스케이프 문자 무시 

print(r"Hello\nWorld")  # \n이 그대로 출력됨
-> Hello\nWorld

path = r"C:\Users\jy\Desktop\file.txt"
print(path)

👉 3. rf 같이 사용 가능 

name = "jy"
path = rf"C:\Users\{name}\Documents"
print(path)

### 📌 #4 map 함수 

여러 개의 데이터를 한 번에 원하는 형식으로 변환

map(변환함수, 반복 가능한 데이터)

numbers = ["1", "2", "3", "4"]
int_numbers = list(map(int, numbers))  # 문자열 -> 정수