SW사관학교 정글 개발일지 - 완전탐색

완전탐색(브루트 포스)

컴퓨터의 빠른 계산을 이용해서 가능한 모든 경우의 수를 일일이 나열하면서
답을 찾는 방법으로 고등학교때 수학 모의고사의 주관식 문제중에 모든 경우의 수를
전부다 구해서 문제를 노가다(실력) 로 풀었던 것과 같다고 할 수 있습니다.
이것을 브루트 포스 공격, 키 전수조사, 무차별 대입 공격 등으로도 불리며
주로 암호학이나 알고리즘 분야에서 사용 됩니다.

완전 탐색 기법

완전 탐색 방법을 이용하기 위해서 주로 이용되는 기법 입니다.

• 단순 브루트포스
• 순열, 조합
• 재귀함수
• BFS / DFS
• 비트마스크(2진수 표현 기법을 활용하는 방법)

순열과 조합

순열 (순열 공식 : nPr = n!/(n-r)!)

n개의 원소를 사용해서 순서를 정하여 r개의 배열로 나타내는 것
순열은 순서가 있기 때문에 원소의 종류가 같아도
순서가 다르면 다른배열이 된다.

조합 (조합 공식 : nCr=nPr/r!)

n개의 원소를 사용해서 순서의 관계없이 r개의 배열로 나타내는 것
조합은 순서가 없어서 원소의 종류가 같으면 같은 배열로 나타낸다.

Python에서 permutation, combination 사용

from itertools import permutations, combination
a = [1,2,3]
# 순열
permute = permutations(a,2)
print(list(permute)) # [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)] - 6가지

# 조합
combi = combinations(a,2)
print(list(combi)) # [(1,2),(1,3),(2,3)] - 3가지