[SWEA]파이썬 SW문제해결 기본 - LIST 1 : Exhaustive Search(완전 탐색)

---

파이썬 SW문제해결 기본 - LIST 1

03 Exhaustive Search(완전 탐색)

---

이미지를 클릭하시면 SW Expert Academy의 해당 강좌로 이동합니다

03. Exhaustive Search

    ① 완전 검색 소개

        ▣ 완전 검색(Exhaustive Search)

            - 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법

            - 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다.

            - 일반적으로 경우의 수가 적을 때 유용하다.

            - 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리다.

            - 그러나 해답을 찾아내지 못할 확률이 낮다.

            - 우선 완전 검색으로 해답을 도출한 후 성능 개선을 위해 다른 알고리즘 사용

 

    ② Baby-gin Game

        ▣ Baby-gin 게임

            - 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때,
                1) 3장의 카드가 연속적인 번호 -> run

                2) 3장의 카드가 동일한 번호 -> triplete

            - 6장의 카드가 run과 triplete로만 구성된 경우를 'Baby-gin'으로 부른다.

            EX1) 667767 => 666,777 => 두 개의 triplete이므로 Baby-gin!
            EX2) 054060 => 456, 000 => 한 개의 run과 한 개의 triplete이므로 Baby-gin!
            EX3) 101123 => 111, 023 => 한 개의 triplete이 존재하나 023이 run이 아니므로 Not Baby-gin...
            (123,110으로 해도 run이 존재하나 triplete이 아니다)

        ▣ 6자리 숫자를 입력받아 Baby-gin 여부 찾기

            1) 고려할 수 있는 모든 경우의 수 생성하기
                6개의 숫자로 만들 수 있는 모든 숫자 나열(중복 포함)

                    Ex) 입력으로 [2, 3, 5, 7, 7, 7]을 받았을 경우, 다음과 같이 순열 생성

모든 경우의 수 나열

            2) 해답 테스트하기

                앞의 3자리와 뒤의 3자리를 잘라, run과 triplete 여부를 테스트 후 Baby-gin!을 판단

이 경우는 Baby-gin!이 아니다

            3) 이렇게 모든 순열을 순회하며 Baby-gin! 여부를 판단하면 된다.

 

        ▣ 순열(Permutation)

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

            - 서로 다른 n개 중 r개를 택하는 순열 => nPr

            - nPr은 다음과 같은 식이 성립 => nPr = n * (n-1) * (n-2) * ... * (n-r+1)

            - nPn = n!이라고 표기하며 Factorial이라 부름 => n! = n * (n-1) * (n-2) * ... * 2 * 1