Jay's Develop Note

💡정렬이란?

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열 하는것 이다. 알고리즘 문제를 풀어본 사람이라면 정렬에 대해 수도 없이 많이 들어봤을텐데, 오늘은 이 정렬에 대해서 짚고 넘어가 보자. 상황에 적절하지 못한 정렬 알고리즘을 사용하면 필요 이상으로 시간을 많이 소요하게 되는데, 이것 때문에 정렬 알고리즘을 공부하는 이유이기도 하다. 다음은 여러가지 정렬 알고리즘에 대한 설명이다. 내림차순 정렬은 기본으로 파이썬에서 제공되는 정렬 라이브러리를 이용해 오름차순 정리를 한 후, 문자열을 뒤집는 메서드를 활용하여 내림차순 정렬을 할 수 있다. 이 뒤집는 연산은 O(N)이기 때문에, 여기서는 오름차순 정렬만 다루도록 하겠다.

📌 선택 정렬(Selection Sort)

컴퓨터가 데이터를 정렬할때 어떻게 할지 생각해보자. 이 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하면 어떨까? 이 방법은 가장 원시적인 정렬 방법으로, 선택 정렬(selection sort)라고 부른다. 이해를 돕기 위해 예시와 함께 보자.

정렬 알고리즘에서는 정렬할 데이터의 갯수를 N으로 칭한다. 다음 예제에서는 N = 10인 경우를 가정한다. 또한, 다음 그림에서 회색 카드는 '현재 정렬되지 않은 데이터중 최솟값'을 의미하며, 하늘색 카드는 '이미 정렬된' 데이터를 의미한다.

다음은 파이썬으로 구현한 선택정렬 코드이다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i  # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]  # 스와프

print(array)

여기서 스와프(swap)란 특정한 리스트가 주어졌을때 두 변수의 위치를 변경하는 작업을 의미한다. 파이썬에서는 간단히 리스트 내의 두 원소의 위치를 변경 할 수 있다.

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

  📊 선택 정렬의 시간 복잡도

그렇다면, 선택 정렬의 시간 복잡도는 어떨까? 사실 위에서 언급한 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하면 어떨까? 여기서 알고리즘을 공부 해 본사람이라면 눈치를 챌 수 있듯, 너무 연산의 횟수가 많다. 이유는 매 반복문마다 리스트를 차례로 검사하며 가장 작은 값을 찾아야 하기 때문이다.

선택 정렬은 N -1 번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 선택 정렬의 시간 복잡도는 O(N^2)로, 효율이 좋지 않은 정렬 알고리즘이다. 직관적으로 이해하자면, 소스코드상의 for반복문이 2중으로 겹쳐 있기 때문이다. 만약, 정렬해야 할 데이터의 갯수가 100배로 늘어나면, 이론적으로 수행시간은 10,000배가 늘어난다. 그렇다면, 이러한 시간 복잡도를 가지는 선택 정렬이 얼마나 효율적일까?

위의 표에서 볼 수 있듯, 선택 정렬은 효율적인 알고리즘은 아니다. 하지만 코딩 테스트에서 가장 작은 값을 찾는 일이 잦으므로 항상 기억해두자.

📌 삽입 정렬(Selection Sort)

비효율적인 선택 정렬 대신 다른 알고리즘은 없을까? "데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?" 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을때' 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다.

삽입 정렬은 특정한 위치에 데이터를 '삽입'한다는 의미에서 삽입 정렬 이라고 부른다. 더불어 삽입 정렬은 특정 데이터가 삽입되기 전에 그 앞까지의 데이터는 이미 정렬 되어있다고 가정한다. 다음과 같이 초기 데이터가 구성되어 있다고 가정 해보자. 삽입 정렬은 두번째 데이터부터 시작한다. 왜냐하면 첫번째 데이터는 그 자체로 정렬 되어 있다고 판단하기 때문이다. 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):  # 인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j] < array[j - 1]:  # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else:  # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

여기서 range에 대해 잠깐 짚고 넘어갈 부분이 있는데,

for i in range(5, 0, -1):
    print(i, end=' ')  # 출력: 5 4 3 2 1

삽입 정렬의 시간 복잡도는 선택 정렬과 같이 O(N^2)이다. 하지만, 여기서 꼭 기억 해야할 내용은 삽입 정렬은 현재 데이터가 정렬된 상태라면 매우 빠르게 동작 한다는 점이다. 가장 효율적인 정렬 알고리즘으로 알려진 퀵 정렬 조차도 정렬이 거의 되어있는 상황에서는 삽입 정렬이 더 빠르게 동작한다.

다음에는 퀵 정렬에 대해서 설명하겠다.

지난 포스팅에선 DFS에 대해 설명하였다. 그럼 이번 포스팅에서는 BFS에 대해 알아보자.

📌BFS

너비 우선 탐색 알고리즘은, 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선 탐색한다는 방식이였다면, BFS는 그 반대이다. BFS를 구현 할 때에는 선입선출 방식인 큐를 이용하는것이 정석이다. 인접한 노드들을 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온것이 먼저 나가게 되며, 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 로직은 다음과 같다.

1. 탐색 시작 노드를 큐에 넣고 방문 처리한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드중, 방문하지 않은 노드들을 모두 큐에 삽입후 방문 처리를 한다.

3. 2번의 과정을 더 이상 반복 할 수 없을 때까지 반복한다.

너비 우선 탐색 알고리즘은 큐 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현함에 있어 deque라이브러리를 이용하는것이 좋으며, 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 일반적인 경우 실제 수행 시간은 DFS보다 좋다는 것만 기억하자. 

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

실행결과 : 1 2 3 8 7 4 5 6

이제 DFS/BFS에 대해 간단히 알고 넘어갔으므로 다음은 예제들을 보며 더 깊게 이해해 보자.

📚예제 1) 음료수 얼려 먹기(DFS)

이 문제는 dfs로 해결 할 수 있다. 앞에서 배운대로 얼음을 얼릴 수 있는 공간이 상 하 좌 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 예를들어 다음과 같이 3x3크기의 얼음 틀이 있다고 가정 해보자.

001

010

101

다음 그래프와 같이 모델링 될 수 있다. DFS를 사용하는 로직은 다음과 같다.

1. 특정한 지점의 주변 상,하,좌,우를 살핀 뒤, 주변 값중 값이 '0'이면서 아직 방문하지 않은 노드를 방문한다.

2. 방문한 지점에서 다시 상,하,좌,우를 살피면서 방문을 진행하면, 연결된 모든 지점을 방문 할 수 있다.

3. 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 0:
        # 해당 노드 방문 처리
        graph[x][y] = 1
        # 상, 하, 좌, 우의 위치도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True
    return False

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result)  # 정답 출력

📚예제 2) 미로 탈출(BFS) - 최단경로 탐색

이 문제는 BFS를 이용했을때 시작 노드부터 가장 인접한 노드들을 탐색하므로 매우 효과적이다. 그러므로 (1,1)을 기점으로 BFS를 실행하여 모든 노드의 값을 거리 정보로 넣어주면 된다. 특정 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. 예를들어 다음과 같은 3x3의 미로가 주어졌다고 가정해보자.

110

010

011

from collections import deque

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

# 이동할 네 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 네 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

# BFS를 수행한 결과 출력
print(bfs(0, 0))

앞선 1장에서 설명했듯, DFS/BFS는 각각 탐색 알고리즘이다. 이 탐색 알고리즘을 이해하기 위해 요구되는 선행지식은 재귀, 스택, 큐 정도이다. 만약 이 선행지식을 모르고 있다면 이전 포스팅을 참고하면 좋을 것 같다.

2024.06.29 - [LeetCode + 알고리즘] - [Algorithm] DFS/BFS(1) - DFS/BFS를 이해하기 위한 자료구조

📌 DFS

DFS(Deapth First Search)는 깊이 탐색 알고리즘이라 불리우며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 이를 이해하려면 먼저 '그래프' 자료구조에 대해 알고 있어야 한다. '그래프'는 노드(node)와 간선(edge)로 구성되며, 이때 노드를 정점(vertex)라고도 한다. 그래프 탐색이란 하나의 노드에서 시작하여 다수의 노드를 방문 하는것을 말한다. 여기서 노드와 노드 사이가 간선으로 연결되어 있다면, 두 노드는 인접해있다 라고 말할 수 있다.

CS에서 그래프는 두가지 방식으로 표현 될 수 있다.

• 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

먼저, 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같은 2차원 행렬 그래프를 파이썬에서는 2차원 배열로 구현 할 수 있다. 연결이 되지 않는 노드끼리는 무한의 비용이라고 표현한다. 실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값중 99999999와 같이 초기화를 하는 경우가 많다.

INF = 99999999999999

#2차원 리스트를 이용해 인접 행렬 표현
graph = [
	[0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
    ]
    
print(graph)

출력 결과 : [[0, 7, 5], [7, 0, 9999999999], [5, 999999999999, 0]]

• 인접 리스트(Adjacency List) : 인접 리스트 방식에서는 다음 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

인접 리스트는 연결 리스트(LinkedList)를 활용하여 구현하는데, 파이썬은 기본 자료형인 리스트 자료형이 append()와 같은 메소드를 제공하므로, 배열과 연결 리스트의 기능을 동시에 제공한다. 파이썬으로 인접 리스트를 구현 할 때에도 단순히 2차원 리스트를 이용하면 된다는 것을 기억하자.

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))

print(graph)

#출력결과 : [[(1,7), (2, 5)], [(0, 7)], [(0, 5)]]

아래는 리스트 컴프리헨션에 관한 내용이다.

📎 위의 두 방식에는 어떤 차이가 있을까?

메모리 측면에서 살펴본다면, 인접 행렬 방식은 모든 관계를 저장하므로 노드 갯수가 많을수록 메모리가 불필요하게 낭비된다. 반면, 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 이와 같은 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 인접 리스트 방식에서는 연결된 데이터를 하나하나 확인해야 하기 때문이다. 

예를들어, 노드 1과 7이 연결되어 있는지 확인할때, 인접 행렬 방식에서는 graph[1][7]만 확인하면 된다. 반면 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 순회해야 한다. 그러므로, 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 낭비가 적다.

📎DFS는 어떤 방식으로 동작할까?

DFS는 우선 깊이 탐색 알고리즘 이라고 했다. 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며 구체적인 동작은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

다음과 같은 그래프를 생각 해보자. 노드 1을 시작으로 DFS를 이용해 탐색을 한다면 이름에 걸맞게 단순히 가장 깊이 있는 노드를 탐색 할때까지 탐색하면 된다. 또한 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러개 있으면 번호가 낮은 순서부터 처리한다.

다음은 DFS가 실행되는 로직을 도식화 한 것이다.

깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며, 탐색을 수행함에 있어 데이터의 갯수가 N개인 경우 O(N)의 시간이 소요 된다는 특징이 있다. 또한, DFS는 스택을 이용하는  알고리즘이기 때문에 실제 구현은 재귀 함수를 이용하면 훨씬 간단하게 구현 가능하다. 다음은 예제 코드이다.

# DFS 예제 함수
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

# 실행결과 : 1 2 7 6 8 3 4 5

이 유형은 코딩 테스트에서 거의 필수적으로 출제되는 유형이다. 저번에 코테를 봤을때도 DFS/BFS는 무조건 한 문제씩은 출제 되었으며, 이 문제는 어려운 난이도에 속해 합격 여부를 판가름 하는 중요한 유형이다.

DFS/BFS는 알고리즘을 한번이라도 공부 해 본 사람은 알겠지만 각각 차례로 깊이 우선 탐색 / 너비 우선 탐색 이다. 먼저 곧바로 깊이/너비 우선 탐색을 공부하기 전에, 꼭 필요한 자료구조 기초부터 알아보자.

📚 꼭 필요한 자료구조 기초

• 탐색(Search)이란 많은 양의 데이터 중, 원하는 데이터를 찾는 과정을 말한다. 대표적인 탐색 알고리즘으로 DFS/BFS를 꼽을 수 있는데, 이 알고리즘을 이해하려면 먼저 기본 자료구조인 스택과 큐에 대해 알고 있어야 한다.
  
  우선, 스택과 큐는 다음 두개의 핵심적인 함수들로 동작한다.
  - 삽입(Push) : 데이터를 삽입한다.
  - 삭제(Pop) : 데이터를 삭제한다.
  
  
• 📍스택(Stack)
  스택은 이름부터 직관적인 자료구조이다. 접시 쌓기를 생각하면 이해하기 더 쉬울 것이다. 넓은 접시를 정리해 찬장에 도로 넣는 상황을 생각 해 보자. 접시를 아래서부터 위로 쌓아야 한다. 그리고 접시를 꺼낼때는 위에 있는 접시부터 차례로 꺼낸다. 여기서 스택 자료구조의 특징인 '선입후출'이 등장한다. 즉, 먼저 스택에 들어간 요소는 가장 나중에 나온다. 라고 이해 할 수 있다. 생각을 해 보자. 맨 아래부터 10개의 접시를 차례대로 쌓았다고 생각해 보자. 이때, 맨 아래에 있는 1번 접시를 빼려면 10번 접시부터 차례로 10번을 빼야 비로소 1번 접시를 뺄 수 있다. 아래는 스택의 연산을 도식화 한 것이다. 초기 단계에서 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()를 수행하는 연산이다.
  

파이썬은 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop()을 이용하면 스택 자료구조와 동일하게 동작한다.

• 📍큐(Queue)
  큐는 은행의 손님 대기열과 같다고 생각하면 편하다. 예를 들어보자. 은행에 도착을 했는데 이미 앞에 5명의 사람들이 대기중이였다. 여기서 내가 대기 번호표를 뽑으면 나는 큐의 6번째 자리에 위치 하고있고, 1번 손님이 불려 나간다면 2번 손님이 1번으로 가고, 3번이 2번... 이렇게 해서 내가 1등이 될 때까지 기다려야 한다. 이는 위에서 언급한 스택과는 반대되는 개념인 '선입선출'이 등장한다. 즉, 큐에서는 먼저 큐에 들어간 사람이 먼저 나오며, 스택과 같이 뒤에서부터 큐가 쌓인다.
  
  다음은 큐의 연산을 도식화 한 것이다. 연산의 순서는 [삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()] 이러하다.

아래는 위의 과정들을 소스코드로 표현한 것이다.

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)        # 먼저 들어온 순서대로 출력
queue.reverse()     # 다음 출력을 위해 역순으로 바꾸기
print(queue)        # 나중에 들어온 원소부터 출력

파이썬에서 큐를 구현 할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. deque는 스택과 큐의 장점을 모두 채택한 것인데, 삽입, 삭제에 탁월하며, queue 라이브러리를 이용하는 것보다 더 간편하다.

• 📍재귀 함수(Recursion)
  자료구조, 알고리즘을 공부하다 보면 여러 학생들의 고통을 불러 일으킨다는 재귀 함수이다. 나도 강의에서 처음 재귀를 접했을때 머리가 어지러웠다. 이해도 안 되었고, 재귀문이 깊어지면 깊어 질수록 내 머리를 더 아프게 했다.
  
  거두절미 하고, 재귀 함수란 자기 자신을 여러번 호출하는 함수이다. 가장 간단한 재귀 함수는 다음과 같다.

def recursion():
	print("RECURSION")
    	recursion()

이 함수를 실행하면 끊임없이 "RECURSION"이 출력 될 것이다.

이 재귀 함수에서는 꼭 포함 되어야 할 것이  있다.

종료 조건문(base case)

 - 이 종료 조건문은 재귀 함수가 종료되어야 할 조건이며, 이 조건에 부합하면 더이상 재귀 함수를 호출하지 않고 끝내야 한다. 이 종료 조건  문이 필수인 이유는 무한대로 재귀 함수를 호출하지 않기 위해서 이다. 위의 소스코드를 예로 들어보자. 위에서 언급했듯 저 함수를 호출 하면 너무 재귀문의 깊이가 깊어(무한대) 오류가 발생 할 것이다. 이때, 재귀문이 종료 될 조건을 포함 시켜 주어야 한다. 아래 예시를 보자.

def recursion(count=0):
    if count >= 10:
        return
    print("RECURSION")
    recursion(count + 1)

recursion()

 여기서는 if count >= 10 이 종료 조건이다. 카운트를 하나씩 늘려가며 함수를 호출하지만, 10번의 카운트가 끝나면 더이상 호출되지 않고 return 문을 통해 함수가 끝나야 한다. 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용한다. 따라서 스택 자료구조를 활용해야 하는 상당수의 알고리즘은 재귀 함수를 이용해서 간단히 구현 할 수 있다. DFS가 대표적인 예 이다.

아래 코드를 살펴보자. 재귀를 배울때 가장 많이 등장하는 factorial함수를 재귀적, 비재귀적으로 구현한 코드이다.

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# 두가지 방식으로 구현한 n! 출력 (n = 5)
print('반복적으로 구한:', factorial_iterative(5))
print('재귀적으로 구한:', factorial_recursive(5))

위 코드의 결과는 똑같이 120이 찍힐 것이다. 그렇다면 반복문 대신 재귀 함수를 사용 했을때의 장점은 무엇일까? 먼저, 코드의 길이가 더 짧다. 간결한 코드는 좋은 코드를 쓰기 위함의 일부이며, 개발자들은 최대한 코드를 간결하고 깨끗하게 유지하는 습관을 길러야 한다. 이렇게 간결해진 이유는 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다. 수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수의 관계로 표현한 것을 의미한다. 이 개념은 추후에 DP와 이어지기 때문에 중요하다.

팩토리얼을 수학적 점화식으로 표현하면 다음과 같다.

- n이 0 혹은 1일 때: factorial(n) = 1

- n이 1보다 클 때: factorial(n) = n * factorial(n-1)

일반적으로 우리는 수학적 점화식에서 재귀 함수의 종료 조건을 쉽게 찾을 수 있다. 여기서는 1번이 종료 조건이다. 여기서 n이 1 이하의 경우를 생각 해내지 못하면 재귀 함수가 무한히 반복 될 것이므로 종료 조건을 파악하는 과정은 중요한 대목이다. 이 점화식과 위의 소스 코드를 비교해 보면, 점화식과 소스 코드는 닮아 있다는 것을 알 수 있다.


이처럼 DFS/BFS를 이해하기 전에 필요한 자료구조, 알고리즘을 알아 보았다. 다음 포스팅에는 실제로 DFS/BFS가 뭔지 자세하게 알아 보도록 하겠다.

알고리즘 문제를 풀다 보면 이 "구현"에 관련된 내용을 자주 접했을 것이다. 나도 올 여름 LG 코딩테스트에서 구현,DFS, 최단경로 등등의 문제가 나왔지만 알고리즘에 무지했던터라 어떤 문제가 "구현" 문제인지 알아내지 못했다. 하지만 리서치를 해보니, 대부분의 기업에서 가장 많이 출제하는 유형은 대부분 DFS / 구현 / 최단경로 / 완전탐색 이였다. 그래서 오늘은 도대체 이 "구현"이 뭔지 알고 넘어가 보도록 하겠다.

• 구현(Implementation)이란 무엇일까?
  
  먼저, 프로그래밍적 관점에서 '구현' 이란 단순히 머릿속에 있는 알고리즘을 코드로 작성하는 것이다. 어떤 문제이건 간에 머릿속의 아이디어를 소스코드로 바꾸는 과정은 필수이므로 구현 문제의 유형은 포괄적인 개념이다.흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 

 그렇다면, 어떤 문제를 '구현하기 어렵다' 라고 할 수 있을까? 알고리즘은 간단한데 코드가 지나치게 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등이 까다로운 구현 유형의 문제라고 할 수 있다. 또한 프로그래밍 문법을 제대로 모르거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀때 불리하다. 

• 구현 시 고려해야 할 메모리 제약 사항
  • C / C++에서 정수의 표현범위
    전통적으로 프로그래밍 언어에서 정수형(int)를 표현할 때는 int 자료형을 주로 사용하며, 이 자료형의 크기는 4바이트 이다. 자바의 int의 표현 범위는 -2,147,483,648 ~ 2,147,483,648이며, 이 범위 바깥의 숫자는 int로 표현 할 수 없고, long 자료형을 써야한다. 
  • 파이썬의 자료형과 리스트 크기
    반면, 파이썬에서는 프로그래머가 직접 자료형을 지정 할 필요가 없으며, 매우 큰 수의 연산도 기본적으로 지원한다.
    이제, 리스트 크기의 제약에 대해 알아보자. 파이썬에서 리스트를 사용 할 때 고려해야 할 사항이 있다. 바로 코딩 테스트의 메모리 제한이다. 대체로 코딩 테스트에서는 128~512MB의 메모리 제한을 두는데, 이럴 때는 메모리 제한을 염두에 두고 코드를 작성 해야한다. 파이썬에서는 정수를 사용할때 자바의 int와 같이 자료형을 명시 해줄 필요가 없지만, 내부적으로는 다음 표에서 보이는 것 만큼 메모리를 차지한다.
    
    
   

• 구현 문제에 접근하는 방법
  보통 구현 유형의 문제는 사소한 입력 조건들을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 문제의 길이를 보고 지레 겁 먹기 보단, 문법에 익숙하다면 구현 문제도 손쉽게 풀어 낼 수 있다. 파이썬은 자바/C 와 달리 문자열 처리가 훨씬 간결하다. 기본적인 문법만 잘 알고 있어도 상대적으로 구현 문제를 쉽게 해결 할 수 있다. 이제 구현 문제의 대표적인 두 문제를 보고 이런게 구현 문제구나 하고 넘어가 보자.
  
  • 예제 1) 상하좌우
   

이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례한다(O(n)). 코딩 테스트에서 가장 난이도가 낮은 1 ~ 2번 문제는 대부분 그리디 알고리즘이나 구현 문제이다. 이 두 유형이 논리적 사고력을 확인 할 수 있는 가장 기본 난이도의 문제로 적합하기 때문이다.

# N을 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

n을 입력받아 공간의 크기를 지정한다.
초기 위치 x, y는 (1, 1)로 설정된다.
이동 계획 plans는 공백을 기준으로 나눠서 리스트로 저장된다.

이동 방향 설정:
dx와 dy 리스트는 각 방향으로 이동할 때 x와 y 좌표의 변화를 나타낸다.
move_types 리스트는 이동 방향을 나타내는 문자열을 저장한다.

이동 계획 실행:
for plan in plans 루프를 통해 각 이동 계획을 하나씩 확인한다.
for i in range(len(move_types)) 루프를 통해 이동 방향과 매칭되는 경우 새로운 좌표 nx, ny를 계산한다.
계산된 좌표가 공간을 벗어나는 경우 (nx < 1 or ny < 1 or nx > n or ny > n) 해당 이동을 무시하고, 그렇지 않은 경우 이동을 수행한다.

결과 출력:
최종 좌표 (x, y)를 출력한다.

예제 2)

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

• 예제 2) 왕실의 나이트 - 가장 잘 알려진 기본적인 구현 문제이다.

- 이 문제의 접근 방식은 내가 지금까지 생각 해내지 못했던 방법이다. 우선 문제를 잘 살펴보면, 나이트는 두가지 경로로 움직일 수 있다고 한다. 그렇다면, 주어진 좌표에서 나이트가 이동 할 수 있는 경우의 수를 구하려면, 나이트의 이동 경로를 steps라는 변수에 넣어준다. steps 변수는 다음과 같이 초기화 될 수 있다.

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

현재 값을 기준으로 아래쪽과 오른쪽은 양수의 값을, 위쪽과 왼쪽은 음수의 값을 대입했다. 이렇게 미리 steps를 정해 놓으면(즉 이 steps리스트 안에 담긴 각각의 튜플들은 주어진 위치에서 뻗어 나갈 수 있는 모든 경우의 수 이며, 반복문을 통해 이 steps의 step들이 유효한지 검사하면 간단할 일이다.)

내가 생각해낸 pseudo code는 대략 다음과 같다.

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

#여기서 주어진 (x,y)좌표는 'coord'라고 칭하겠음
#기존 8x8의 프레임 사이즈는 'frame'이라고 칭하겠음

count = 0

for step in steps:
	if (coord + step) >= frame:
    	count += 1

return count

아래는 해설집에 나온 소스코드이다.

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

예제 3)

이 문제는 전형적인 시뮬레이션 문제이다. 별도의 알고리즘이 필요하다기 보다는 문제에서 요구하는 내용을 오류없이 성실하게 구현한다면 풀 수 있다는 특징이 있다. 하지만 문제가 길고 문제를 소스코드로 옮기는 과정이 쉽지 않다. 따라서 이러한 문제들은 반복된 연습을 통해 익숙해 지는 연습을 하는것이 가장 중요하다.

- 문제 풀이를 위해 다시 설명하자면, 일반적으로 방향을 설정하여 이동하는 문제라면 dx, dy라는 별도의 리스트를 만들어 방향을 정하는것이 효과적이다. 예를들어 다음의 답안 코드 예시는 현재 캐릭터가 북쪽을 바라보고 있을때는 북쪽으로 이동하기 위해 x와 y 좌표를 각각 dx[0], dy[0] 만큼 더한다. 다시 말해, 현재 위치에서 (-1, 0) 만큼 이동 시키는 것이다. 이처럼 위치들을 리스트에 미리 설정해놓고 반복문을 이용하면 모든 방향을 차례대로 확인 할 수 있다는 장점이 있다.

- 그리고 답안 코드를 보면 리스트 컴프리헨션을 사용해 2차원 리스트를 초기화 했다. 파이썬에서 2차원 리스트를 선언할때는 리스트 컴프레션이 효과적이라는것을 기억해 두자.

그렇다면, 리스트 컴프리헨션이란 무엇인가?

even_numbers = []
for i in range(1, 11):
    if i % 2 == 0:
        even_numbers.append(i)

even_numbers = [i for i in range(1, 11) if i % 2 == 0]

matrix = []
for _ in range(3):
    row = []
    for _ in range(3):
        row.append(0)
    matrix.append(row)

matrix = [[0 for _ in range(3)] for _ in range(3)]

아래는 예제 3의 소스 코드이다.

n, m = map(int, input().split())

d = [[0] * m for _ in range(n)]

x, y, direction = map(int, input().split())
d[x][y] = 1

array = []
for i in range(n):
    array.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3

count = 1
turn_time = 0
while True:
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    else:
        turn_time += 1
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        if array[nx][ny] == 0:
            x = nx
            y = ny
        else:
            break
        turn_time = 0

print(count)

그래서 "구현"은 단순히 알고리즘을 코드로 변환하는 과정을 의미한다. 이 과정은 필수적이기 때문에 다양한 문제 유형에 적용될 수 있다. '구현' 문제는 문제를 해결하는 알고리즘이 비교적 간단하지만, 이를 정확하게 코드로 옮기는 과정에서 많은 주의가 필요하다. 특히 디버깅과 테스트가 중요한데, 이는 코드가 올바르게 작동하도록 하기 위해 필수적이다. '구현' 유형의 문제를 많이 풀어보면서 다양한 문제에 익숙해지는 것이 중요하다.

결론적으로, '구현' 문제는 알고리즘 문제를 풀기 위한 기본적인 단계이며, 이를 통해 프로그래밍 실력을 향상시킬 수 있다. 반복적인 연습과 다양한 문제를 풀어보는 것이 '구현' 문제에 능숙해지는 지름길이다. 꾸준한 연습을 통해 다양한 문제를 해결하는 능력을 키워나가자.

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬

저번학기 Data Algo & Analysis 수업에서 처음으로 Greedy 알고리즘에 대해 들어보았다. 가장 유명한 그리디 문제는 거스름돈 문제이다. Greedy라는 단어를 한국어로 직역하면 "탐욕적인" 이다. 그렇다면, 알고리즘에서 탐욕적이란것은 어떤것을 의미할까? 여기서 "탐욕적이다" 라는 말은, "현재 상황에서 최적의 해를 선택한다" 라는 말과 비슷하게 여겨진다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는(최적해)것을 선택하며, 현재의 선택이 나중에 영향을 미칠것은 생각하지 않는다.

그리디 알고리즘은 기준에 따라 좋은것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시 해 준다. 대체로 이 기준은 '정렬'을 이용했을때 손쉽게 풀리므로, 그리디 알고리즘은 자주 정렬 문제와 짝을 이룬다.

이제 위에서 언급한 "거스름돈" 문제를 통해 그리디 알고리즘이 뭔지 더 자세히 알아보자.

첫번째 문제 : 

이 문제의 핵심 접근법은 "가장 큰 화폐 단위부터"돈을 거슬러 주는것이다. N원을 거슬러 줘야 할 때, 가장 큰 단위의 돈인 500원으로 거슬러 줄 수 있을만큼 거슬러 주는 것이다. 그 다음, 거슬러 줄 수 있는 범위 안에서 100원 - 50원 - 10원 순서대로 돈을 거슬러 주면 최소한의 동전으로 거스름돈을 줄 수 있다.

예를들어 , 우리가 거슬러 줘야 할 돈 N의 값이 1,260원 이라면, 최소한의 동전 갯수로 거슬러 줄 수 있는 경우는 다음과 같다.

(500 x 2) + (100 x 2) + (50 x 1) + (10 x 1)

위의 과정을 파이썬으로 구현한 코드는 다음과 같다.

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin
    	n %= coin
    
return count

대표적인 그리디 문제라 코드도 간결하고 간단하다. 그런데 사실 여기까지 풀고도 대략적인 감만 올 뿐, 문제가 좀 더 복잡하다면 훨씬 더 어려워 질 것 같은 느낌이다.

두번째 문제 : 

아마 이 문제를 리트코드나 백준에서 봤다면 난 "그리디"를 떠올리진 못했을 것이다. 여기서 "그리디"를 떠올릴 수 있도록 문제를 해석 해 보자.

이 문제는 기본적으로 리스트가 인자로 주어지고, 추가적으로 변수 K, M이 주어진다. 이때, 이 리스트에서 M번의 횟수만큼 덧셈을 하여 최댓값을 구하여라. 단, 같은 인덱스에 있는 숫자는 K회 반복할 수 있다. 위의 문제를 예로 들어, 리스트가 [2,4,5,4,6], M = 8, K = 3과 같이 주어진다면, 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 가 이 문제에서 원하는 결과를 도출 할 수 있다.

- 문제가 원하는건 ? == 배열 안의 수를 M번 더했을때의 최댓값. 작은 값은 필요가 없다. 우리는 가장 큰 값과 두번째로 큰 값만 알고 있으면 된다. 그렇다면, 리스트를 정렬하면 맨 뒤의 숫자가 가장 큰 숫자일것이고, 이 숫자를 K번 까지만 연속으로 더할 수 있다. 그 다음은 맨 뒤 바로앞의 값을 1회만 더하고, 다시 가장 큰 값을 K번까지 반복하여 더해준다(M을 넘지 않는 선에서).  

아래는 위 문제의 파이썬 코드이다.

nums.sort()
firstMax = nums[-1]
secondMax = nums[-2]

result  = 0

for i in range(k):
	if m == 0:
    	break
    result += first
    m -= 1
if m == 0:
	break
result += second
m -= 1

return result

하지만 여기서 문제가 있다. 위의 예시에선 M이 10,000 이하이므로 이 방식으로 코드를 제출해도 통과를 하겠지만, M의 크기가 10,000 이상으로 커진다면 시간 초과 판정을 받을 것이다. 그렇다면, 더 효율적인 방법은 없을까?

아래는 간단한 수학적 아이디어를 포함한 설명이다.

- 위의 예시에서 가장 큰 수와 그 다음으로 큰 수는 6, 5 와 같다. 이 문제를 풀려면 먼저 "반복되는 수열"을 먼저 파악해야 한다. 가장 큰 수와 그 다음으로 큰 수가 더해질땐 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다. 위의 예시에서는 [5,5,5,6]이 된다( sum([5,5,5,6]) + sum([5,5,5,6]) == 46. 그렇다면 반복되는 수열의 길이는 어떻게 될까? 조금만 생각해보면  K + 1 이 된다는 것을 알 수 있다. 따라서 M을 수열의 길이 K + 1로 나눈것이 이 수열의 반복 횟수가 된다. 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다. 

- 이때 M이 K + 1로 나누어 떨어지지 않는 경우도 고려 해야한다. 그럴때는 M을 K + 1로 나눈 나머지 만큼 가장 큰 수가 추가로 더해지므로 이를 고려해야 한다. 즉, '가장 큰 숫자가 더해지는 횟수'는 다음과 같다.

int(M / (K + 1)) * K + M % (K + 1)

이를 토대로 작성한 파이썬 코드는 다음과 같다.

data.sort()  # 입력받은 수 정렬
first = data[n - 1]  # 가장 큰 수
second = data[n - 2]  # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) * first  # 가장 큰 수 더하기
result += (m - count) * second  # 두 번째로 큰 수 더하기

print(result)  # 최종 답안 출력

세번째 문제 : 

이 문제는 결국 "각 행마다 가장 작은 수를 찾은 뒤, 그 수들 중 가장 큰 수를 찾아내기" 정도로 해석된다. 입력 조건에서 들어오는 모든 수는 10,000 이하이므로 단순히 배열에서 가장 작은 값을 찾는 기본 문법을 이용하여 각 행에서 가장 작은 수를 찾은 다음 그 수들중 가장 큰 수를 찾는 방식으로 문제를 해결 할 수 있다. 다음은 위 문제를 파이썬 코드로 구현한 것이다.

1. min()함수를 이용

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = min(data)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result)  # 최종 답안 출력

2. 이중 반복문을 이용

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result)  # 최종 답안 출력

세번째 문제:

-내가 이 문제를 봤다면 Greedy를 생각 해내긴 어려웠을 것이다. 이 문제의 핵심 아이디어는 주어진 N에 대하여 '최대한 많이 나누기'를 수행하면 된다. 왜냐하면 어떠한 수가 있을때, '2 이상의 수로 나누는 것'이 '1을 빼는것' 보다 실행 횟수를 훨씬 많이 줄일 수 있기 때문(문제에서 요구하는 결과는 최소한의 실행횟수이므로)이다.(여기서 Greedy가 등장한다.) 문제에서는 K가 2 이상의 자연수 이므로, 가능하면 나누는 것이 1씩 빼는것 보다 훨씬 더 빠르게 계산 횟수를 줄일 수 있다.

예를들어, N이 9이고 K가 3이라면, 2번의 나눗셈으로 1을 만들 수 있다. 하지만, 여기서 나눗셈이 아니라 1씩 빼는 방법을 사용한다면, 8번의 계산을 해야 1이 된다. 4배나 많은 연산을 하는 셈이다.

다른 예를 들어보자. N이 25, K = 3일땐 다음과 같다.

1. N = 25(초기 상태)

2. N - 1 = 24

3. 24 // 3 = 8

4. 8 - 1 = 7

5. 7 - 1 = 6

6. 6 // 3 = 2

7. 2 - 1 = 1

6번의 과정으로 N = 1을 만들 수 있다. 그렇다면 위의 방법이 빠르게 동작하면서 그와 동시에 최적의 해를 보장한다는 것은 어떻게 알 수 있을까?

N = 27, K = 3일 때를 다시 생각해보자. 처음 3으로 나누었을 때는 27에서 18이 줄어들어 N = 9가 된다. 그다음에 3으로 나누었을 때는 9에서 6이 줄어들어 N = 3이 된다. 다시 말해 N이 클수록 K로 나누었을 때 줄어드는 양이 더 많다. N이 처음엔 큰 수라고 해도 나누기를 수행하면서 크기가 빠르게 줄어든다. 다시 말해 K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있으며, N이 결국 1에 도달한다는 것을 알 수 있다. 그러므로 K로 최대한 많이 나눌 수 있도록 하는 것이 최적의 해를 보장하는 것이다.

파이썬을 이용해 작성한 답안 예시는 다음과 같다.

result = 0

while n >= k:
	while n % k != 0:
    	n -= 1
        result += 1  
    n //= k
    result += 1
    
while n > 1:
	n -= 1
    result += 1
    
return result