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

• 이번에는 코딩 테스트에서 중요한 유형인 'Brute Forcing(브루트포스)'에 대해 알아보겠습니다. 브루트포스는 가능한 모든 경우의 수를 탐색하여 정답을 찾는 방법입니다. 즉, 모든 가능성을 일일이 시도해보는 방식으로 문제를 해결합니다.

 

브루트포스 알고리즘의 개념

 

• 브루트포스 알고리즘은 가능한 모든 경우의 수를 직접 확인하며 최적의 해를 찾아내는 방식입니다. 이는 다른 방식으로 최적해를 찾기 어려운 경우에 효과적인 방법일 수 있으나, 경우의 수가 많은 경우에는 시간이 매우 오래 걸릴 수 있습니다.

 

브루트포스 문제 접근법

 

1. 문제 이해와 제약 사항 파악: 주어진 문제를 정확하게 이해하고, 입력 크기와 제약 사항을 파악해야 합니다.
2. 가능한 모든 조합 생성: 주어진 입력 범위 내에서 가능한 모든 조합을 생성합니다.
3. 조건 체크와 정답 판별: 각각의 조합에 대해서 주어진 제약 조건을 체크하고, 정답 여부를 판별합니다.
4. 시간 복잡도 분석: 가능한 모든 경우의 수를 탐색하는 브루트포스 알고리즘은 경우에 따라 시간 복잡도가 매우 크게 증가할 수 있습니다. 따라서, 문제의 입력 크기와 제약 사항을 고려하여 최적화된 구현 방법을 선택해야 합니다.
5. 예외 처리와 최적화: 입력 범위나 조건에 따라 일부 경우를 예외 처리하거나, 중복되는 계산을 피하기 위한 최적화 기법을 적용할 수 있습니다.
6. 출력 형식과 결과 확인: 문제에서 요구하는 출력 형식에 맞게 결과를 출력하고, 정답 여부를 확인합니다.
7. 테스트 케이스 작성과 검증: 주어진 예제나 추가적인 테스트 케이스를 작성하여 구현한 코드의 정확성을 검증합니다.
8. 문제의 특성에 따른 접근 방법: 브루트포스는 모든 경우를 탐색하는 방식이기 때문에, 문제의 특성에 따라 적합한 접근 방법을 선택해야 합니다. 예를 들어, 순열을 생성하는 문제인 경우 백트래킹(Backtracking)을 활용하여 중복을 제거하면서 조합을 생성할 수 있습니다.
9. 비트마스크(Bitmask): 비트 연산을 활용하여 가능한 모든 조합을 표현하고 처리할 수 있는 비트마스크 기법을 사용할 수 있습니다.
10. 메모이제이션(Memoization): 이전에 계산한 결과를 저장해두고 재활용함으로써 중복 계산을 피하는 메모이제이션 기법을 활용할 수 있습니다.

 

10974번: 모든 순열

  문제  

 

• N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

 

  해결 방법  
 

• 이 문제는 주어진 숫자로 만들 수 있는 모든 순열을 찾는 문제입니다. 브루트포스 방식으로 가능한 모든 경우의 수를 생성하고 출력하면 됩니다. 
• 파이썬에 내장된 itertools 모듈의 permutations 함수를 이용하면 쉽게 이 작업을 수행할 수 있습니다.

from itertools import permutations

n = int(input())
for p in permutations(range(1, n+1)): print(*p)

 

16637번: 괄호 추가하기

  문제  
 

• 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.
• 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.
• 수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

  해결 방법  
 

• 이 문제는 주어진 수식에 괄호를 추가해서 구할 수 있는 값들 중 최댓값을 찾아내는 문제입니다. 일부 연산자에 괄호를 추가할지 안 할지 결정하여 가능한 모든 경우를 만들어낸 후, 각 경우에 대한 값을 계산해서 최댓값을 찾아내야 합니다. 이를 위해 깊이 우선 탐색(DFS)를 사용하여 재귀적으로 문제를 해결할 수 있습니다.
• dfs 함수를 이용해 현재 인덱스와 계산 결과를 인자로 넘겨주며 깊이 우선 탐색을 진행합니다. 각 연산자에 대해 괄호를 추가하지 않은 경우와 추가한 경우를 구분하여 연산을 수행하고, 다음 인덱스와 그에 따른 결과를 재귀 호출로 넘겨줍니다.
• 최종적으로 모든 연산자를 처리한 경우에는 전역 변수 max_val에 현재 계산 결과와 현재까지의 최댓값을 비교하여 더 큰 값을 저장합니다. 마지막에 max_val을 출력하면 해결된 문제의 정답을 얻을 수 있습니다.

def calculate(x, y, op):
    if op == '+': return x + y
    elif op == '-': return x - y
    else: return x * y
    
def dfs(idx, ans):
    global max_val

    if idx == len(ops):
        max_val = max(max_val, ans)
        return

    cur_val = calculate(ans, nums[idx+1], ops[idx])
    dfs(idx+1, cur_val)
    
    if idx + 1 < len(ops):
        bracket = calculate(nums[idx+1], nums[idx+2], ops[idx+1])
        cur_bracket = calculate(ans, bracket, ops[idx])
        dfs(idx+2, cur_bracket)
        
n = int(input())
exp = input()
nums = list(map(int, exp[::2]))
ops = list(exp[1::2])

max_val = float('-inf')
dfs(0, nums[0])
print(max_val)

 

• 브루트포스 알고리즘은 가능한 모든 경우의 수를 검토하여 문제를 해결하는 방식이며, 이는 경우의 수가 그리 많지 않을 때 유용한 방식입니다. 하지만 경우의 수가 매우 많은 경우에는 실행 시간이 매우 길어지기 때문에 다른 방법을 시도해보는 것이 좋습니다.
• 이 외에도 브루트포스 알고리즘과 함께 재귀, 백트래킹 등 다양한 기법을 조합하여 문제를 해결할 수 있습니다. 문제를 해결하는데 필요한 알고리즘과 자료구조를 잘 이해하고 사용하는 것이 코딩 테스트에서 좋은 결과를 얻기 위해 중요합니다.