Brute-Force

Brute-force

• brute-force는 문제를 해결하기 위한 간단하고 쉬운 접근법

  • Just-do-it

  • force의 의미는 사람(지능)보다는 컴퓨터의 force를 의미

• brute-force 방법은 대부분의 문제에 적용 가능

• 상대적으로 빠른 시간에 문제 해결(알고리즘 설계)을 할 수 있음

• 문제에 포함된 자료(요소, instance)의 크기가 작다면 유용

• 학술적 또는 교육적 목적을 위해 알고리즘의 효율성을 판단하기 위한 척도로 사용됨

Brute-force 탐색 (sequential search)

: 자료들의 list에서 key값을 찾기 위해 첫 번째 자료부터 비교하면서 진행

• 결과

  • 탐색 성공

  • 탐색 실패

• 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작음

  • 완전 검색은 입력의 크기를 작게 해서 간편하고 빠르게 답을 구하는 프로그램을 작성함

• 이를 기반으로 그리디 기법 이나 동적 계획법을 이용해서 효율적인 알고리즘을 찾을 수 있음

• 코딩테스트 등에서 문제를 풀 때, 우선 완점 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직함

Baby-gin Game

설명

• 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.

• 그리고, 6장의 카드가 run과 triplet으로만 구성된 경우를 baby-gin 으로 부른다

• 6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램을 작성하라.

완전 검색을 통한 Baby-gin 접근

1. 고려할 수 있는 모든 경우의 수 생성하기

   • 6개의 숫자로 만들 수 있는 모든 숫자 나열 (중복 포함)

2. 해답 테스트 하기

   • 앞의 3자리와 뒤의 3자리를 잘라, run과 triplet 여부를 테스트하고 최종적으로 baby-gin 판단

완전 검색

• 많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것

• 전형적으로 순열(permutation), 조합(combination), 그리고 부분 집합(subsets)과 같은 조합적 문제들 (Combinatorial Problems) 과 연관됨

• 완전 검색은 조합적 문제에 대한 brute-force 방법이다

순열 (Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

• 서로 다른 n개 중 r개를 택하는 순열은 nPr

• 다음과 같은 식이 성립함

  • nPr = n x (n-1) x (n-2) x ... x (n-r+1)

• nPn = n! 이라고 표기하며, Factorial 이라 부름

  • n! = n x (n-1) x (n-2) x ... 2x1

• 순열은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 있음

  • ex) TSP (Traveling Salesman Problem)

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

  • n >12 인 경우, 시간 복잡도 폭발!!! (지수승으로 올라가기 때문에...)

1. 재귀 호출을 통한 순열 생성 - 교환을 통해 생성

def perm(n,k):
    if k == n:
        #do something
 else:
        for i in range(k, n):
            swap(k,i)#swap!
            perm(n, k+1)
            swap(k,i) #다시 원상 복귀

Subsets (부분 집합)

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

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

  • ex) 배낭 짐싸기 (knapsack)

• N개의 원소를 포함한 집합

  • 자기 자신과 공집합 포함한 모든 멱 집합(power set)의 개수는 2^n개

  • 원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가

1. 단순하게 모든 부분 집합 생성하는 방법

• 4개 원소를 포함한 집합에 대한 power set 구하기

2. Binary Counting

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

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

Combination (조합)

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

• 조합의 수식

  • nCr = n-1 C r-1 +n-1 C r

  • nC0 = 1