Skip to content

Latest commit

 

History

History
139 lines (92 loc) · 4.3 KB

01_Brute-Force.md

File metadata and controls

139 lines (92 loc) · 4.3 KB

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