Algorithm: 인간은 망각의 동물이다

학생들을 가르치다 보면 나를 지치게 하는 것 중 하나가 지난 시간에 가르쳐준 내용을 기억하지 못하는 것이다. 그런데 돌이켜 보면 "나는 예전에 한번 배운걸 모두 기억하고 있었나?" 하는 생각이 든다.

인간을 약속할 수 있는 존재로 만드는 것. 이것을 니체는 인간에게 부여된 '역설적' 과제이자, 인간에 관한 '본래적인' 문제로 이해한다. 약속할 수 있는 존재란 그 자신의 사고와 행위가 일정정도 산정 가능한 존재다. 즉 그 자신의 사고와 행위를 예측할 수 있고, 그것들을 일정정도 규칙적이며 필연적인 것으로 이해하는 존재다. 이런 존재가 되기 위해서 인간은 자신에게 있는 자연적인 힘, 즉 망각의 힘을 제거해야 한다. 즉 자신의 사고와 행위를 기억할 필요가 있는 것이다.

인간은 본성상 망각하는 동물인 것이다. 망각은 결코 이성능력의 부족이나 타성력이 아니라, 삶에 필요하고 삶을 가능하게 하는 힘이다. 그것이 의식 이전에 발생하는 욕구나 충동들의 모순과 대립의 과정들에 대한 정보를 차단할 뿐만 아니라, 프로이트가 억압(Verdrängung)이라는 단어로 말했던 것처럼 고통스러운 기억을 밀어내어 정신적 질서와 안정을 찾게 하는 기능을 하기 때문이다. 이 장치에 의해 인간은 행복감과 건강함을 느끼게 된다. 이러한 자연적이고도 동물적인 망각의 힘은 '의지의 기억'에 의해 제거된다.

• 망각 (니체 『도덕의 계보』 (해제), 2005., 백승영)

1. DFS (Depth-First Search)

def dfs(graph, v, visited):
    visited[v] = True
    for nv in graph[v]:
        if not visited[nv]:
            dfs(graph, nv, visited)

• 팁: 방문 체크는 함수 진입 직후
• 실수: 종료 조건 누락, visited 복원 안 함(백트래킹 시)
• 예시: 백준 2667(단지번호붙이기), 프로그래머스 네트워크

2. BFS (Breadth-First Search)

from collections import deque
def bfs(graph, start):
    visited = [False]*len(graph)
    q = deque([start])
    visited[start] = True
    while q:
        v = q.popleft()
        for nv in graph[v]:
            if not visited[nv]:
                visited[nv] = True
                q.append(nv)

• 팁: visited는 큐에 넣을 때 체크
• 실수: 거리 계산 시 for문 없이 while만 사용
• 예시: 백준 7576(토마토), 1697(숨바꼭질)

3. 이분 탐색 (Binary Search)

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

• 팁: left <= right 종료 조건, mid 계산 주의
• 실수: left/right 값 변화 안 해서 무한 루프
• 예시: 백준 2110(공유기 설치), 프로그래머스 입국심사

4. 다익스트라 (Dijkstra)

import heapq
def dijkstra(graph, start):
    dist = [float('inf')]*len(graph)
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, now = heapq.heappop(heap)
        if d > dist[now]:
            continue
        for cost, nxt in graph[now]:
            nd = d + cost
            if nd < dist[nxt]:
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))

• 팁: if d > dist[now]: continue 필수
• 실수: 인접 노드 갱신 조건 빼먹음
• 예시: 백준 1753(최단경로)

5. 유니온 파인드 (Union-Find)

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra < rb:
        parent[rb] = ra
    else:
        parent[ra] = rb

• 팁: find 시 경로 압축 꼭 하기
• 실수: 루트 아닌 노드끼리 연결
• 예시: 백준 1717(집합의 표현)

6. DP (Dynamic Programming)

dp = [0]*(n+1)
dp[0] = 초기값
for i in range(1, n+1):
    dp[i] = min(dp[i-1]+cost, ...)

• 팁: 작은 문제부터 점화식으로 쌓기
• 실수: 초기값 설정 누락, 점화식 틀림
• 예시: 백준 2579(계단 오르기), 프로그래머스 정수 삼각형

7. 슬라이딩 윈도우 / 투 포인터

left = 0
s = 0
for right in range(n):
    s += arr[right]
    while s > target:
        s -= arr[left]
        left += 1

• 팁: right 확장 → 조건 초과 시 left 수축
• 실수: 빠지는 값 반영 안 함
• 예시: 백준 2003(수들의 합 2)

8. 누적합 (Prefix Sum)

prefix = [0]
for num in arr:
    prefix.append(prefix[-1]+num)

# 구간 합
res = prefix[r]-prefix[l-1]

• 팁: 누적합 배열 한 칸 크게 만들기
• 실수: 인덱스 헷갈려서 오프셋 오류
• 예시: 백준 11659(구간 합 구하기 4)

9. 우선순위 큐 (Heap)

import heapq
min_heap = []
heapq.heappush(min_heap, x)
heapq.heappop(min_heap)

# 최대 힙
heapq.heappush(min_heap, -x)
val = -heapq.heappop(min_heap)

• 팁: 최대 힙은 음수 변환
• 실수: heapq는 기본 최소힙
• 예시: 프로그래머스 더 맵게

10. 백트래킹

def backtrack(path):
    if 조건:
        결과저장
        return
    for i in range(시작, 끝):
        if not visited[i]:
            visited[i] = True
            path.append(i)
            backtrack(path)
            path.pop()
            visited[i] = False

• 팁: 선택 → 재귀 → 복원 순서
• 실수: visited 복원 안 함, 가지치기 조건 누락
• 예시: 백준 9663(N-Queen)

11. 위상 정렬 (Topological Sort)

from collections import deque
def topology_sort(graph, indegree):
    q = deque()
    for i in range(len(indegree)):
        if indegree[i] == 0:
            q.append(i)
    while q:
        now = q.popleft()
        for nxt in graph[now]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

• 팁: 진입 차수 0부터 시작, 차수 줄이기 필수
• 실수: 중복 큐 삽입, DAG 아닌데 사용
• 예시: 백준 2252(줄 세우기)

12. 트리 순회

def preorder(v):
    print(v)
    preorder(left[v])
    preorder(right[v])

• 전위: 루 → 왼 → 오
• 중위: 왼 → 루 → 오
• 후위: 왼 → 오 → 루
• 실수: 순서 헷갈림
• 예시: 백준 1991(트리 순회)