728x90
완전 탐색(Exhaustive Search)이란?
- 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
1. Brute-force 혹은 Generate-and-Test 기법이라고도 불린다.
2. 모든 경우의 수를 테스트한 후 , 최종 해법을 도출한다.
3. 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
4. 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.
5. 주어진 문제를 풀 때, 우선 완전 탐색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.
Baby-gin Game
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을때, 3장의 카드가 연속적인 번호를 갖으면 run이라 하고,
3장의 카드가 동일한 번호를 갖으면 triplete이라고 한다.
이때, 6장의 카드가 run과 triplete로만 구성된 경우를 Baby-gin으로 부른다.
입력 예시
| 667767 → 두 개의 triplete(666,777)이므로 Baby-gin |
| 054060 → 한 개의 run(456)과 한 개의 triplete(000)이므로 Baby-gin |
| 101123 → 한 개의 triplete(111)이 존재하지만, 023이 run이나 triplete이 아니므로 Baby-gin이 아니다 |
6자리의 숫자를 입력 받아 Baby-gin 여부 찾기
- 고려할 수 있는 모든 경우의 수 생성
6개의 숫자로 만들 수 있는 모든 숫자를 나열한다.(중복 포함) - 해답 테스트
앞의 3자리와 뒤의 3자리를 잘라, run과 triplete의 여부를 테스트하여 Baby-gin을 판단한다.
순열이란?
- 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것
1. 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현
nPr
2. nPr은 다음과 같은 식이 성립
nPr = n * (n-1) * (n-2) * .... * (n-r+1)
3. nPn = n! 이라고 표기하며 팩토리얼(Factorial)이라 부름
n! = n * (n-1) * (n-2) * .... * 2 * 1
728x90
'알고리즘' 카테고리의 다른 글
| [알고리즘]배열(Array)이란? (0) | 2022.06.24 |
|---|---|
| [알고리즘]알고리즘(Algorithm)이란? (0) | 2022.06.24 |
