[24.05.29] 99클럽 코테 스터디 10일차 TIL - 완전 탐색 알고리즘

1. 완전 탐색 알고리즘

가능한 모든 경우의 수를 체크해서 정답을 찾는방법으로, Brute Force라고 부르기도 한다. 이 방법은 다음과 같은 절차를 따른다.

1. 모든 가능한 경우의 수 생성 : 문제의 가능한 모든 상태를 생성한다.
2. 각 경우의 수 평가 : 각 경우의 수에 대해 문제를 해결
3. 최적해 선택 : 평가한 결과 중 최적의 해를 선택

완전 탐색에 사용되는 주요 기법에는 아래와 같은 방법 등이 있다.

1. Brute Force 기법 : 반복, 조건문을 활용해 모두 테스트
2. 순열 : n개의 원소 중 r개의 원소를 순서를 고려한 모든 조합을 생성
3. 조합 : 순서를 고려하지 않고 가능한 모든 조합 생성
4. 부분집한 생성 : 집합의 모든 부분집합을 생성
5. 재귀 

---

1.1 Brute Force 기법

반복문과 조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 의미한다. 

 

1.2 순열(Permutation)

순열은 주어진 요소들의 순서를 바꿔가며 가능한 모든 경우를 생성하는 방법이다.

사용 예

• 문자열이나 배열의 요소들을 재배열하는 문제
• 최단 경로 문제

import itertools

arr = [1, 2, 3]
permutations = list(itertools.permutations(arr))
print(permutations)

# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

 

1.3 조합 생성(Combinations)

조합은 주어진 요소들 중에서 순서를 고려하지 않고 선택하는 방법이다. n개의 요소 중 k개를 선택하는 경우 nCk만큼의 조합이 생긴다.

사용 예

• 부분 집합 문제
• 선택 문제 (ex. 팀 구성)

import itertools

arr = [1, 2, 3]
combinations = list(itertools.combinations(arr, 2))
print(combinations)

# [(1, 2), (1, 3), (2, 3)]

 

1.4 부분 집합 생성 (Subsets)

부분 집합 생성은 주어진 집합의 모든 부분 집합을 생성하는 방법이다. n개의 요소가 주어졌을 때, 총 2^n개의 부분집합이 존재한다.

# 비트마스크를 활용한 예제
def generate_subsets(arr):
    n = len(arr)
    subsets = []
    
    for i in range(1 << n):  # 1<<n은 2의 n제곱을 의미 
        subset = []
        for j in range(n): # 각 요소의 포함 여부를 결정하기 위해 마스크의 각 비트 확인
            if i & (1 << j): # 비트연산으로 mask의 i번째 비트가 1인지 확인
                subset.append(arr[j])
        subsets.append(subset)
    
    return subsets

arr = [1, 2, 3]
subsets = generate_subsets(arr)
print(subsets)

# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

 

1.5 재귀

재귀는 자기 자신을 호출하는 함수를 활용하여 코드를 짧게 줄이는 방법이다. 

재귀를 구현하기 위해선 아래의 조건들을 고려해야한다.

• 재귀를 탈출하기 위한 탈출 조건
  무한 루프, 배열 범위 초과 오류 등을 방지하기 위한 탈출문이 필요하다.
• 상태변화 
  재귀 호출 시 입력 값 또는 상태가 변경되어 재귀를 탈출 할 수 있게 되어야 한다.

# 피보나치 수열 예제
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2) # 재귀적으로 함수를 호출