코테 공부정리 (Python)

1. DFS
2. BFS
3. DFS vs BFS
4. Dynamic Programming
5. 이분매칭
6. deque
7. heapq

📚DFS

✔️ 설명

DFS(Depth-First Search, 깊이 우선 탐색)는 그래프나 트리의 모든 노드를 탐색할 때 사용하는 알고리즘입니다. DFS는 한 경로로 최대한 깊이 탐색한 후, 더 이상 갈 곳이 없으면 이전 정점으로 돌아가 다른 경로를 탐색하는 방식으로 작동합니다.

✔️ 특징

• 스택(Stack) 자료 구조를 기반으로 동작합니다. 이를 구현할 때 실제 스택을 사용할 수도 있지만, 재귀 호출 시 내부적으로 스택이 사용됩니다.
• 그래프 또는 트리의 모든 노드를 방문하는데 적합합니다.
• 깊이를 우선적으로 탐색하므로 특정 경로의 끝까지 도달한 후, 그 경로가 완료되면 다시 돌아가서 다른 경로를 탐색합니다.
• 방문한 노드를 기억하는 방문 배열(visited)을 사용하여 한 번 방문한 노드를 다시 방문하지 않도록 방지합니다.

✔️ 재귀방식 vs 스택방식

1. 재귀 방식
   • 재귀 호출을 통해 스택의 역할을 대신하며, 파이썬의 함수 호출 스택을 사용합니다.
   • ‼️중요‼️ 하지만 재귀 깊이가 깊어질 경우 스택 오버플로우가 발생할 수 있습니다. 따라서 탐색 깊이가 깊어지면 sys.setrecursionlimit()을 사용하여 재귀 한도를 늘리기도 합니다.
   • 코드는 간결하지만, 큰 그래프나 깊은 탐색에서는 위험할 수 있습니다.
2. 스택 방식
   • 명시적인 스택 자료 구조를 사용하여 스택 오버플로우 문제를 해결합니다.
   • 재귀 호출 없이도 구현 가능하며, 메모리 관리에 있어서 좀 더 효율적일 수 있습니다.
   • 코드가 조금 더 복잡해질 수 있지만, 재귀를 피할 수 있는 장점이 있습니다.

✔️ 활용 예시 (재귀) 문제: 유기농 배추

direction = [(0, -1), (0, 1), (-1, 0), (1, 0)] # 좌우 상하
m, n, k = 10, 8, 17 # 농장의 (가로, 세로, 배추 갯수)

farm = [
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [0, 0, 1, 1, 0, 0, 0, 1, 1, 1], 
    [0, 0, 0, 0, 1, 0, 0, 1, 1, 1], 
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
visited = [[False] * m for _ in range(n)]  
answer = 0

def dfs(x, y, farm, visited):
    visited[y][x] = True
    
    for dy, dx in direction:
        nx, ny = dx + x, dy + y
        
        if 0 <= nx < m and 0 <= ny < n:
            if farm[ny][nx] == 1 and not visited[ny][nx]:
                dfs(nx, ny, farm, visited)

for y in range(n):
    for x in range(m):
        if not visited[y][x] and farm[y][x] == 1:
            dfs(x, y, farm, visited)
            answer += 1

print(answer) # 5

✔️ 활용 예시 (스택) 문제: 유기농 배추

direction = [(0, -1), (0, 1), (-1, 0), (1, 0)] # 좌우 상하
m, n, k = 10, 8, 17 # 농장의 (가로, 세로, 배추 갯수)

farm = [
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [0, 0, 1, 1, 0, 0, 0, 1, 1, 1], 
    [0, 0, 0, 0, 1, 0, 0, 1, 1, 1], 
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
visited = [[False] * m for _ in range(n)]  
answer = 0

def dfs(x, y): 
    stack = [(x, y)]
    visited[y][x] = True

    while stack:
        cx, cy = stack.pop()
        for dy, dx in direction:
            nx, ny = dx + cx, dy + cy
            if 0 <= nx < m and 0 <= ny < n:
                if not visited[ny][nx] and farm[ny][nx] == 1:
                    visited[ny][nx] = True
                    stack.append((nx, ny))

for y in range(n):
    for x in range(m):
        if not visited[y][x] and farm[y][x] == 1:
            dfs(x, y)
            answer += 1

print(answer) # 5

📚BFS

✔️ 설명

BFS(Breadth-First Search)는 그래프 또는 트리에서의 탐색 알고리즘 중 하나로, 너비 우선 탐색 방법을 사용합니다. BFS는 먼저 시작 노드에서 가까운 노드를 탐색한 후 점차 멀리 있는 노드로 이동합니다. 이를 위해 큐(Queue)를 사용하여 현재 탐색 중인 노드의 이웃을 차례대로 저장하고 탐색합니다.

✔️ 특징

• 최단 경로 탐색: BFS는 가중치가 없는 그래프에서 두 노드 간의 최단 경로를 보장합니다.
• FIFO 큐 사용: 방문할 노드를 큐에 저장하고, 먼저 들어온 노드를 먼저 탐색합니다.

✔️ 동작순서

1. 시작 노드를 큐에 삽입합니다.
2. 큐에서 노드를 하나 꺼내고 해당 노드를 방문합니다.
3. 방문한 노드에 연결된 인접 노드를 모두 큐에 삽입합니다.
4. 큐가 빌 때까지 이 과정을 반복합니다.

✔️ 활용 예시 문제: 숨바꼭질

from collections import deque

 # 현재 위치, 목표 도달 위치
N, K = 5, 17
visited = [False] * 100001  
visited[N] = True  

def bfs():
    q = deque([(N, 0)])
    while q:
        n, sec = q.popleft()
        if n == K:
            # 목표 도달시 출력 후 종료
            print(sec) 
            break
        # 현재 위치에서 (-1, +1, *2) 3가지 가능성이 있는 케이스를 계산한다.
        for next in (n - 1, n + 1, n * 2):
            # 방문처리와 재방문 방지
            if 0 <= next <= 100000 and not visited[next]:
                visited[next] = True  
                q.append((next, sec + 1)) 

bfs()

📚DFS vs BFS

✔️ 탐색 방식의 차이

DFS는 하나의 경로를 끝까지 탐색한 후 다시 돌아와서 다른 경로를 탐색합니다. 즉, 깊이 우선으로 탐색을 진행합니다. 이를 위해 스택(Stack) 자료 구조나 재귀 함수 호출을 사용합니다. 먼저 깊이(depth)를 우선으로 탐색하므로, 한 노드에서 갈 수 있는 경로를 모두 탐색한 뒤에야 다른 경로로 돌아옵니다.

BFS는 먼저 시작 노드에서 가까운 노드를 탐색하고, 그 다음으로 멀리 있는 노드를 탐색합니다. 즉, 너비 우선으로 탐색을 진행합니다. 이를 위해 큐(Queue) 자료 구조를 사용합니다. 먼저 동일한 레벨(level)의 모든 노드를 탐색한 후, 다음 레벨로 이동합니다.

✔️ 자료 구조

DFS는 주로 스택(재귀 호출 시 시스템 스택)을 사용하여 가장 최근에 방문한 노드를 기준으로 다음 탐색을 진행합니다.
BFS는 주로 큐를 사용하여 먼저 들어온 노드부터 차례로 탐색합니다.

✔️ 사용 예시

1. DFS 사용 예시

   • 경로 탐색: 특정 노드에서 특정 노드로 가는 경로를 찾거나, 미로 탐색 등의 문제에 적합합니다.
   • 백트래킹: 가능한 모든 경우를 시도해야 할 때 사용됩니다. 예를 들어, 퍼즐 문제, 조합/순열 문제 등에서 DFS가 유용합니다.
   • 사이클 탐지: DFS는 그래프에서 사이클이 존재하는지를 확인하는 데 적합합니다.

2. BFS 사용 예시

   • 최단 경로 탐색: 가중치가 없는 그래프에서 두 노드 간의 최단 경로를 찾는 데 적합합니다.
   • 계층 탐색: 한 레벨씩 순차적으로 탐색해야 하는 문제에 유용합니다. 예를 들어, 소셜 네트워크에서 친구 관계를 탐색할 때 같은 레벨의 사람들부터 차례로 탐색하는 것이 유리합니다.
   • 레벨 탐색: 트리의 각 레벨에서 노드를 순차적으로 탐색하는 경우 BFS가 적합합니다.

📚 Dynamic Programming

✔️ 설명

동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 기법은 최적화 문제를 해결하기 위해 사용되며, 주어진 문제를 잘 정의된 하위 문제로 나누고, 이 하위 문제의 결과를 저장하여 중복 계산을 피하는 방식으로 작동합니다. DP는 주로 최적화 문제, 경로 탐색 문제 및 조합 문제에 적용됩니다.

✔️ 특징

• 최적 부분 구조: 문제의 최적 해결책이 하위 문제의 최적 해결책으로 구성될 수 있습니다. 즉, 큰 문제를 해결하기 위해 작은 문제를 해결하고 그 결과를 결합하여 최적 해를 도출합니다.
• 중복 하위 문제: 동일한 하위 문제가 여러 번 발생합니다. 이를 메모이제이션 또는 테이블을 사용하여 해결함으로써 효율성을 높입니다.
• 메모이제이션: 계산한 결과를 저장하여 동일한 계산을 반복하지 않도록 합니다. 재귀적 방법과 함께 사용되는 경우가 많습니다.
• 탑다운 또는 바텀업 접근: DP는 하위 문제를 해결하는 순서에 따라 두 가지 접근 방식으로 나뉩니다.
• 탑다운: 재귀적으로 문제를 해결하고, 이미 계산된 결과를 저장하여 필요할 때 재사용합니다.
• 바텀업: 가장 작은 하위 문제부터 차근차근 해결해 나가면서 큰 문제의 해결책을 만들어 나갑니다.

✔️ 예시

• 피보나치 수열: n번째 항을 계산하는 문제를 DP로 해결할 수 있습니다. 각 항은 이전 두 항의 합으로 정의되며, 중복 계산을 피하기 위해 이미 계산된 값을 저장합니다.
• 0-1 배낭 문제: 주어진 물건들의 가치와 무게를 기반으로 최대 가치를 얻기 위해 제한된 용량의 배낭에 어떤 물건을 담아야 하는지를 결정하는 문제입니다. DP를 사용하여 각 물건을 포함하거나 포함하지 않을 경우의 최대 가치를 계산합니다.
• RGB 거리 문제: 이 문제는 N개의 집을 빨강, 초록, 파랑으로 색칠할 때의 최소 비용을 계산합니다. 각 집은 인접한 집과 같은 색으로 칠할 수 없는 제약이 있으며, DP를 통해 각 집의 색칠 비용을 최소화합니다.

📚이분매칭

✔️ 설명

이분 그래프에서 두 개의 독립된 집합 사이에서 가능한 최대 매칭을 찾는 문제입니다. 이분 그래프는 두 개의 집합으로 정점들이 나뉘어 있으며, 각 간선은 서로 다른 집합의 정점 사이에서만 연결됩니다.

✔️ 특징

• 매칭(Matching): 이분 매칭에서 "매칭"은 간선의 부분집합으로, 각 정점이 최대 하나의 간선에만 포함되도록 선택됩니다. 즉, 각 정점이 한 번만 매칭에 참여할 수 있습니다.
• 최대 매칭(Maximum Matching): 가능한 한 최대한 많은 간선을 선택하여 매칭을 구성하는 것을 말합니다. 최대 매칭을 구하는 것이 이분 매칭 문제의 핵심입니다.
• DFS와 BFS의 활용: 이분 매칭을 해결하는 일반적인 방식은 깊이 우선 탐색(DFS)을 사용해 교환 경로를 탐색하는 것입니다. 경우에 따라 BFS(너비 우선 탐색)도 보조적으로 사용됩니다.

✔️ 예시

• 구인/구직 매칭: 두 집합 중 하나를 구직자, 다른 하나를 일자리로 설정하여 각각의 구직자와 일자리가 연결된 경우, 가능한 최적의 매칭을 찾을 수 있습니다.
• 작업 할당 문제: 작업을 수행할 수 있는 기계나 사람과 각 작업 간의 최적 할당을 찾는 데 사용됩니다.
• 대학 입시, 파티 구성: 학생-전공 매칭, 파티나 그룹을 구성하는 등의 문제에도 이분 매칭 알고리즘이 사용됩니다.

✔️ 예시 열혈강호

import sys

sys.setrecursionlimit(100000)

# 작업자, 작업
N, M = map(int, input().split()) 

tasks = {}
assigned = [None] * (M + 1) # 매칭 상태를 기록

for i in range(1, N + 1):
    line = list(map(int, input().split()))
    tasks[i] = line[1:]

# 매칭을 수행
def assign(staff, visited): 
    for task in tasks[staff]:
        if visited[task]:  
            continue
        visited[task] = True
        # 작업자가 할당되어 있지 않거나 이미 할당되어있다면 해당 작업자가 다른 작업으로 양보할 수 있는지 확인한다.
        if assigned[task] is None or assign(assigned[task], visited): 
            assigned[task] = staff 
            return True
    return False

for i in range(1, N + 1):
    # 작업자를 순화할때 마다 작업 visited를 초기화한다.
    visited = [False] * (M + 1) 
    assign(i, visited)

print(sum(1 for a in assigned if a != None))

📚deque

✔️ 설명

deque는 Python의 collections 모듈에서 제공하는 양방향 큐로, 리스트와 유사하지만 양쪽 끝에서 빠르고 효율적으로 요소를 추가하거나 제거할 수 있는 자료 구조입니다. deque는 Double-Ended Queue의 약자로, 큐의 양쪽 끝에서 요소를 추가하거나 제거하는 작업을 O(1) 시간 안에 수행할 수 있어, 리스트보다 효율적입니다.

✔️ 특징

• 양방향으로 삽입과 삭제가 가능합니다.
• 앞쪽에서 추가/삭제, 뒤쪽에서 추가/삭제 모두 지원합니다.
• 리스트는 양쪽 끝에서 요소를 추가하거나 삭제하는 데 O(n) 시간이 걸릴 수 있지만, deque는 O(1)의 시간 복잡도를 보장합니다.
• 큐, 스택, 덱 등 다양한 방식으로 활용 가능합니다.

✔️ 간단 사용방법

from collections import deque

l = [1,2,3,4]

dq = deque(l) # deque([1, 2, 3, 4])
dq.append(5) # deque([1, 2, 3, 4, 5])
dq.appendleft(6) # deque([6, 1, 2, 3, 4, 5])
first = dq.popleft() # 6
last = dq.pop() # 5
print(dq) # deque([1, 2, 3, 4])

📚heapq

✔️ 설명

heapq는 Python에서 힙 큐(우선순위 큐)를 효율적으로 사용할 수 있도록 지원하는 모듈입니다. 힙은 이진 트리 기반의 자료 구조로, 최소값이나 최대값을 빠르게 찾아내기 위한 우선순위 큐를 구현할 때 유용합니다. heapq 모듈은 기본적으로 최소 힙(min-heap)을 제공합니다.

✔️ 예시

import heapq

ints = [40, 50, 20]

heapq.heapify(ints) # [20, 50, 40]
min = heapq.heappop(ints) # 20
heapq.heappush(ints, 100) # [40, 50, 100]