5.3. 파이썬 고급 알고리즘

파이썬은 다양한 알고리즘을 구현하기에 적합한 언어로, 특히 고급 알고리즘을 다루는 데 유용합니다. 이 글에서는 파이썬 고급 알고리즘에 대한 주요 개념을 다루고, 재귀와 동적 프로그래밍, 그래프 탐색(DFS, BFS), 그리고 해시 테이블 활용에 대해 자세히 설명하겠습니다.

1. 재귀와 동적 프로그래밍

1.1 재귀

재귀는 함수가 자기 자신을 호출하는 방식으로, 이는 문제를 작은 부분으로 나누어 해결하는 데 유용합니다. 파이썬에서 재귀를 사용하는 방법은 다음과 같습니다:

• 재귀 함수 정의: 재귀 함수는 일반 함수와 유사하지만, 함수 내부에서 자기 자신을 호출하는 특징이 있습니다.
• 재귀 호출: 함수가 자기 자신을 호출할 때, 호출 스택에 함수의 매개 변수와 반환 값이 저장됩니다.
• 재귀 종료: 재귀 함수는 종료 조건이 있어야 합니다. 종료 조건이 없으면 함수 호출이 무한히 반복되어 스택 오버플로가 발생할 수 있습니다.

1.2 동적 프로그래밍

동적 프로그래밍은 문제를 작은 부분으로 나누어 해결하고, 이전에 계산한 결과를 저장하여 중복 계산을 피하는 기법입니다. 파이썬에서 동적 프로그래밍을 사용하는 방법은 다음과 같습니다:

• 메모이제이션: 이전에 계산한 결과를 저장하여 중복 계산을 피합니다.
• DP 테이블: 문제를 해결하는 데 필요한 데이터를 저장하는 테이블을 사용합니다.

예시: 피보나치 수열

피보나치 수열은 재귀와 동적 프로그래밍을 사용하여 구현할 수 있습니다.

재귀로 구현

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

동적 프로그래밍으로 구현

def fibonacci(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]

2. 그래프 탐색(DFS, BFS)

그래프 탐색은 그래프의 노드들을 탐색하는 알고리즘입니다. 파이썬에서 DFS와 BFS를 사용하는 방법은 다음과 같습니다:

2.1 DFS(깊이 우선 탐색)

DFS는 그래프의 깊이 우선으로 탐색하는 알고리즘입니다. 파이썬에서 DFS를 구현하는 방법은 다음과 같습니다:

• 스택 사용: 스택을 사용하여 노드를 방문한 후, 방문하지 않은 노드를 스택에 추가합니다.
• 재귀 사용: 재귀를 사용하여 노드를 방문한 후, 방문하지 않은 노드를 재귀적으로 호출합니다.

예시: DFS로 단지번호 붙이기

from collections import deque

def dfs(graph, x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]) and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = 0
                cnt += 1
    return cnt

def solution(graph):
    result = []
    for i in range(len(graph)):
        for j in range(len(graph[0])):
            if graph[i][j] == 1:
                result.append(dfs(graph, i, j))
    return result

2.2 BFS(너비 우선 탐색)

BFS는 그래프의 너비 우선으로 탐색하는 알고리즘입니다. 파이썬에서 BFS를 구현하는 방법은 다음과 같습니다:

• 큐 사용: 큐를 사용하여 노드를 방문한 후, 방문하지 않은 노드를 큐에 추가합니다.
• 반복문 사용: 반복문을 사용하여 큐에 있는 노드를 방문합니다.

예시: BFS로 단지번호 붙이기

from collections import deque

def bfs(graph, x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0
    cnt = 1
    while queue:
        x, y = queue.popleft()
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]) and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = 0
                cnt += 1
    return cnt

def solution(graph):
    result = []
    for i in range(len(graph)):
        for j in range(len(graph[0])):
            if graph[i][j] == 1:
                result.append(bfs(graph, i, j))
    return result

3. 해시 테이블 활용

해시 테이블은 키-값 쌍을 저장하는 자료구조로, 빠른 검색과 삽입을 지원합니다. 파이썬에서 해시 테이블을 사용하는 방법은 다음과 같습니다:

• dict 사용: 파이썬의 built-in dict 자료구조를 사용하여 해시 테이블을 구현합니다.
• hashlib 사용: 파이썬의 hashlib 모듈을 사용하여 해시 함수를 구현합니다.

예시: 해시 테이블로 단어 카운트

from collections import Counter

def word_count(words):
    word_count = Counter(words)
    return dict(word_count)

words = ['apple', 'banana', 'apple', 'orange', 'banana', 'banana']
print(word_count(words))  # {'apple': 2, 'banana': 3, 'orange': 1}

파이썬 고급 알고리즘은 다양한 문제를 해결하기 위해 재귀, 동적 프로그래밍, 그래프 탐색, 그리고 해시 테이블 활용과 같은 기법을 사용합니다. 이 글에서 설명한 방법들은 파이썬을 사용하여 고급 알고리즘을 구현하는 데 유용한 도구들입니다. 파이썬의 강력한 라이브러리와 자료구조를 활용하여 복잡한 문제를 해결할 수 있습니다.