[SWEA] 완전 검색(Brute-force search)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYDrI61lYDFAVT# 

SW Expert Academy

 

완전 검색(Brute-force search, 브루트 포스 서치)

목차

01 완전 검색 기법

02 조합적 문제

 

 

01 완전 검색 기법

---

완전 검색(Brute-force search)이란?

문제의 해(Solution)를 얻기 위해 가능한 모든 경우들을 나열해 보고 확인하는 기법

• 고지식한 방법(Brute-force), 생성 및 테스트(Generate and test)
• Brute-force의 force의 의미는 사람(지능)보다는 컴퓨터의 힘(force, 계산능력)을 의미

문제를 해결하기 위한 간단하고 쉬운 접근 방법으로, 상대적으로 빠른 시간에 문제 해결이 (알고리즘 설계) 가능하며, 대부분의 문제에 적용 가능함

문제에 포함된 자료(요소, 인스턴스)의 크기가 작을 경우 유용

• 단, 문제의 크기가 커지면 시간복잡도가 매우 크게 증가함
• 이러한 문제점으로 그리디 기법이나 동적 계획법을 이용한 효율적인 알고리즘으로 발전함

 

 

고지식한 검색(순차 검색, Sequential Search)

자료들의 리스트에서 키 값을 찾기 위해 첫 번째 자료부터 비교하면서 진행

결과는 탐색 성공/실패로 나뉨

순차 검색에서 리스트에 키 값이 존재하지 않는다는 것을 확신하기 위해서는 모든 자료들에 대해 키 값과 비교 작업 수행

- 예시 코드(Python)

def sequentialSearch(arr, n, key):
    i = 0
    while i < n and arr[i] != key:
    	i += 1
    if i < n: # success
    	return i
    else: # fail
    	return -1

 

예시 문제: 베이비 진(Baby-Gin)

문제 설명은 아래를 참고해주세요

풀이 코드(Python)

import sys
from itertools import permutations
input = sys.stdin.readline

def is_Run(arr): 
    n = int(arr[0]) 
    for i in range(1,len(arr)):
        if n+1 != int(arr[i]): 
            return False
        n = int(arr[i])
    return True

def is_Triplet(arr): 
    n = arr[0]
    if arr.count(n) == len(arr):
        return True
    return False

nums = input().strip()
perms = list(set(list(permutations(nums,6))))

for perm in perms:
    front = ''.join(perm[:3])
    back = ''.join(perm[3:])
    if is_Run(front) or is_Triplet(front):
        if is_Run(back) or is_Triplet(back):
            print("Yes")
            exit(0)

print("No")

 

02 조합적 문제

---

완전 검색과 조합적 문제

많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 검색으로,

순열(Permutation), 조합(Combination), 부분집합(Subset)과 같은 조합적 문제들(Combinatorial Problems)과 관련되며 완전검색은 조합적 문제에 대한 고지식한 방법(Brute-force)이다

 

순열(Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열 표현 $nPr$
• $nPr$의 식 성립: $nPr = n*(n-1)*(n-2)*\cdots*(n-r+1)$
• $nPn=n!$이라고 표기하며 n Factorial이라고 부른다

 

순열(Permutation)관련 알고리즘 문제

순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련되며, 대표적인 문제로 순회 외판원 문제가 있음

* 순회 와판원 문제(Traveling Salesman Problem)

• 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어짐
• 출발 도시에서 시작해서 다른 모든 도시들을 단 한번만 방문하고 출발
• 도시로 돌아오는 최소 비용의 이동경로를 구하는 문제
• 방문할 도시들을 순서대로 나열하면 하나의 경로가 됨

* N개의 요소들에 대해서 n! 개의 순열들이 존재

순환 외판원 문제에서 거쳐가야 할 도시가 n개라면 가능한 모든 경로는 n!만큼 존재

 

구현 방법

1. 사전식 순서(Lexicographic-Order)

- 요소들이 오름차순으로 나열된 형태가 시작하는 하나의 순열

2. 최소 변경을 통한 방법(Minimum-exchange requirement)

- 각각의 순열들은 이전의 상태에서 단지 두 개의 요소들 교환을 통해 생성

- Johnson-Trotter 알고리즘

 

부분집합

집합에 포함된 원소들을 선택하는 것

다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것

*배낭 짐싸기(Knapsack problem) 문제

• 배낭과 물건들의 집합이 주어지며, 배낭은 무게가 있고 아이템들은 각각 무게와 가치가 있음
• 배낭에 담는 무게의 총합 < 배낭의 무게
• 물건의 총합이 배낭의 무게를 초과하지 않으면서 가치의 합이 최대가 되는 물건을 선택하는 문제

N개의 원소를 포함한 집합

*자기 자신과 공집합 포함한 모든 부분집합(Power set)의 개수는 $2^n$개

 

구현 방법

바이너리 카운팅을 통한 사전적 순서(Lexicographic-Order)

- 부분집합을 생성하기 위한 가장 자연스럽고 간단한 방법

- 바이너리 카운팅(Binary Counting)은 사전적 순서로 생성하기 위한 가장 간단한 방법

*바이너리 카운팅(Binary Counting)

- 원소 수에 해당하는 N개의 비트 열을 이용

- i 번째 비트 값이 1이면 i 번째 원소가 포함되었음을 의미