무식하게 풀기(brute-force) (1)

• 이번 글부터는 여러 알고리즘 패러다임을 다뤄보며 알고리즘 문제에서 어떤 식으로 이 패러다임을 사용하는지 알아보도록 하겠습니다.
• 브루트포스 알고리즘에 대한 접근법이나 더 많은 문제를 원하시면 하단 포스팅을 보셔도 도움이 될 것 같습니다! 👍🏻

꼭 알아야하는 코딩 테스트 유형: 7) #Bruteforcing

 

개요

• 프로그래밍 대회에서 참가자들은 종종 복잡하고도 우아한 해결책을 찾으려 하지만, 실제로는 더 간단하고 명확한 방법이 존재할 때가 많습니다.
• 이러한 상황에서 '완전 탐색(exhaustive search)'이라는 알고리즘이 중요해집니다. 완전 탐색은 모든 가능한 경우를 탐색해 최적의 해결책을 찾는 방법입니다.
• 컴퓨터의 빠른 계산 능력을 활용해 다양한 상황을 신속하게 확인할 수 있기 때문에, 복잡하게 생각할 필요 없이 효과적인 해결책을 제시할 수 있습니다.

 

• 예를 들어, 열 명의 학생을 줄 세우는 문제에서 서로 사이가 나쁜 학생들을 분리하는 것을 생각해 보겠습니다.
• 이 경우, 열 명을 나열할 수 있는 모든 경우의 수를 컴퓨터로 빠르게 계산하여 간단하게 해결할 수 있습니다. 이러한 방법은 사람이 직접 계산하기에는 복잡하지만, 컴퓨터에게는 쉽고 빠른 작업입니다.
• 따라서, 프로그래밍 대회에서는 복잡한 문제에 대해 간단하고 직관적인 해결책을 찾는 연습이 중요합니다.
• 완전 탐색은 이러한 연습에 있어 기본이 되며, 때로는 이보다 더 빠른 알고리즘을 개발하는 기반으로도 작용합니다.

 

재귀 호출과 완전 탐색

• 재귀 호출은 프로그래밍에서 복잡한 문제를 간단한 조각으로 나누어 해결하는 방법입니다.
• 이 방식은 작업을 유사한 형태의 여러 부분으로 나누고, 각 부분을 순차적으로 해결함으로써 전체 문제를 해결합니다. 재귀 함수는 자기 자신을 호출하여 이러한 분할을 수행합니다.
• 중요한 부분은 '기저 사례(base case)를 어떻게 설정하느냐'입니다.
• 기저 사례는 재귀 호출이 더 이상 진행되지 않고 결과를 바로 반환하는 작업의 최소 단위입니다. 이를 통해 무한 루프를 방지하고, 재귀 호출이 효율적으로 작동하게 합니다.

 

• 예를 들어, 숫자들의 합을 구하는 문제에서 재귀 호출을 사용할 수 있습니다. 이때, 각 단계에서 하나의 숫자를 더하고, 남은 숫자들을 더하는 작업을 재귀적으로 처리합니다.

# 1부터 n까지의 합을 계산하는 반복 함수와 재귀 함수

# 필수 조건: n >= 1
# 결과: 1부터 n까지의 합을 반환합니다.
def sum(n: int) -> int:
    result = 0
    for i in range(1, n+1):
        result += i
    return result
  
# 재귀 함수
def recursive_sum(n: int) -> int:
    if n == 1:
        # 더이상 쪼개지지 않을 때
        return 1
    return n + recursive_sum(n-1)

• 특히, 원소들의 조합을 찾거나 순열을 생성하는 문제에서 재귀 호출은 강력한 방법입니다!
• 재귀 호출을 통해 중첩된 반복문을 대체하여 코드를 더 간결하고 유연하게 만들어줄 수 있게 됩니다.

 

# n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

# n: 전체 원소의 수
# picked: 지금까지 고른 원소들의 번호
# to_pick: 더 고를 원소의 수
# 일 때, 앞으로 to_pick개의 원소를 고르는 모든 방법을 출력합니다.
def pick(n: int, picked: list, to_pick: int) -> None:
    # 기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력합니다.
    if to_pick == 0:
        print_picked(picked)
        return
    # 고를 수 있는 가장 작은 번호를 계산합니다.
    smallest = 0 if not picked else picked[-1] + 1
    # 이 단계에서 원소 하나를 고릅니다.
    for next in range(smallest, n):
        picked.append(next)
        pick(n, picked, to_pick-1)
        picked.pop()

 

예제: 보글 게임

• 보글 게임은 5x5 알파벳 격자에서 상하좌우 및 대각선으로 인접한 칸을 이어 단어를 찾는 게임입니다. 여기서 중요한 문제는 주어진 시작점에서 특정 단어를 찾을 수 있는지 확인하는 것입니다.
• 이를 해결하기 위한 좋은 방법은 완전 탐색을 사용하는 것입니다! 모든 인접한 칸을 시험해 보면서 단어를 찾는 것이죠.

• 문제 해결의 핵심은 hasWord$(y, x, word)$ 함수로, 이 함수는 주어진 위치에서 시작해 단어를 찾을 수 있는지를 반환합니다.
• 먼저 시작 위치의 글자가 단어의 첫 글자와 다르면 바로 false를 반환하고, 단어가 한 글자면 성공입니다.
• 그렇지 않으면 단어의 첫 글자를 제외한 나머지 부분을 찾기 위해 주변 칸을 모두 탐색합니다.
• 이 과정에서 효율적인 코드 작성을 위한 중요한 팁은, 잘못된 입력이나 범위를 벗어난 경우를 기저 사례로 처리하는 것입니다.

 

• 완전 탐색 알고리즘의 시간 복잡도를 계산하는 것은 비교적 간단합니다.
• 완전 탐색은 가능한 모든 답 후보들을 만들어 보기 때문에 후보의 최대 수를 계산하면 되는데, 위 경우에는 최대 $O(8^N)$입니다.
• 단어의 길이가 길어질 경우, 다른 설계 패러다임을 고려해야 할 수도 있습니다.

 

• 완전 탐색을 이용하는 일반적인 절차는 다음과 같습니다.

1. 최대 크기의 입력을 가정했을 때 답의 개수를 계산합니다.
2. 가능한 모든 답 후보를 만드는 과정을 여러 개의 선택으로 나눕니다.
3. 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답은 재귀 호출로 완성합니다.
4. 조각이 하나도 남지 않으면 답을 생성한 것이므로, 이것을 기저 사례로 선택합니다.

# 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘
dx = [-1, -1, -1, 1, 1, 1, 0, 0]
dy = [-1, 0, 1, -1, 0, 1, -1, 1]

# 5x5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환합니다.
def has_word(y: int, x: int, word: string) -> None:
    # 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
    if not in_range(y, x):
        return False
    # 기저 사례 2: 첫 글자가 일치하지 않으면 실패
    if board[y][x] != word[0]:
        return False
    # 기저 사례 3: 단어 길이가 1이면 성공
    if len(word) == 1:
        return True
    # 인접한 여덟 칸을 검사합니다.
    for direction in range(8):
        ny, nx = y + dy[direction], x + dx[direction]
        # 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없습니다.
        if has_word(ny, nx, word[1:]):
            return True
    return False

 

문제: 소풍

• 안드로메다 유치원 익스프레스반의 선생님은 공원으로 가는 소풍에서 학생들을 서로 친구인 학생들끼리 짝을 지으려고 합니다.
• 이때, 서로 친구가 아닌 학생들을 짝지으면 문제가 생길 수 있으므로, 반드시 친구 사이에서만 짝을 지어야 합니다.
• 이 문제의 목표는 주어진 친구 관계를 바탕으로 가능한 모든 친구를 짝 지을 수 있는 방법의 수를 계산하는 것입니다.
• 예를 들어, 태연, 제시카, 써니, 티파니, 효연, 유리가 있고 모두 서로 친구라면, 다음과 같이 여러 가지 방법으로 짝을 지을 수 있습니다.

(태연, 제시카) (써니, 티파니) (효연, 유리)
(태연, 제시카) (써니, 유리) (효연, 티파니)

• 입력은 테스트 케이스의 수 $C$, 학생 수 $n$, 친구 쌍의 수 $m$, 그리고 친구 쌍의 번호로 구성됩니다.
• 각 학생은 0부터 n-1까지의 번호로 표시되며, 학생 수는 짝수입니다.

3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

 

• 출력은 각 테스트 케이스에 대해 가능한 짝 지을 수 있는 방법의 수입니다.

1
3
4

 

풀이: 소풍

• 위 문제는 완전 탐색과 재귀 호출을 이용해 해결할 수 있습니다.
• 이 문제의 핵심은 각 답변을 여러 조각으로 나누어서, 각 조각에서 두 학생을 짝지어 주는 것입니다.
• 여기서는 '아직 짝을 찾지 못한 학생들의 명단'이 주어질 때, 친구끼리 짝지어주는 모든 경우의 수를 계산하는 것이 목표입니다.

# 소풍 문제를 해결하는 (잘못된) 재귀 호출 코드

n = 0
are_friends = [[False] * 10 for _ in range(10)]
# taken[i] = i번째 학생이 짝을 이미 찾았으면 True, 아니면 False
def count_pairings(taken: list) -> int:
    global n, are_friends
    # 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료합니다.
    finished = True
    for i in range(n):
        if not taken[i]:
            finished = False
            break
    if finished:
        return 1
    result = 0
    # 서로 친구인 두 학생을 찾아 짝을 지어줍니다.
    for i in range(n):
        for j in range(n):
            if not taken[i] and not taken[j] and are_friends[i][j]:
                taken[i] = taken[j] = True
                result += count_pairings(taken)
                taken[i] = taken[j] = False
    return result

 

• 위 풀이에서는 같은 학생 쌍을 중복하여 계산하거나, 짝을 이루는 순서만 다른 경우를 별개로 계산하는 문제가 있었습니다. 예를 들어, (0, 1)과 (1, 0)을 별도로 세는 식입니다.
• 이를 해결하기 위한 방법으로, 사전순으로 가장 먼저 오는 답만을 세는 전략을 사용합니다.
• 이는 남은 학생들 중 가장 번호가 빠른 학생의 짝을 먼저 찾도록 하여 구현할 수 있습니다.

# 소풍 문제를 해결하는 재귀 호출 코드

n = 0
are_friends = [[False] * 10 for _ in range(10)]
# taken[i] = i번째 학생이 짝을 이미 찾았으면 True, 아니면 False
def count_pairings(taken: list) -> int:
    # 남은 학생들 중 가장 번호가 빠른 학생을 찾습니다.
    first_free = -1
    for i in range(n):
        if not taken[i]:
            first_free = i
            break
    # 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료합니다.
    if first_free == -1:
        return 1
    result = 0
    # 이 학생과 짝지을 학생을 결정합니다.
    for pair_with in range(first_free+1, n+1):
        if not taken[pair_with] and are_friends[first_free][pair_with]:
            taken[first_free] = taken[pair_with] = True
            result += count_pairings(taken)
            taken[first_free] = taken[pair_with] = False
    return result

 

• 위 알고리즘은 답의 개수에 비례하는 시간이 소요됩니다.
• 예를 들어, 열 명의 학생이 모두 서로 친구인 경우, 최대 답의 개수는 945개가 됩니다. 이는 각 단계에서 선택할 수 있는 짝의 수가 줄어들기 때문입니다.
• 브루트포스(완전 탐색) 관련 추가적인 문제와 최적화에 관한 내용은 다음 포스팅에 이어서 작성하겠습니다!