SLENDER ANKLES's 개발블로그

반복하는데 귀신인 컴퓨터에 적당한 방법이다. 가능한 경우를 모두 검사(exhaustive search)하는 무식한(?)방법이다.

답 내는 것이 문제가 아니라 얼마 만큼의 빠른 시간에 작업을 끝낼수 있는 가를 고민해야 되는 파트.

가능성이 없는 것은 미리 잘라버리는 것이 관건이다. 예를 들어, 3 번의 시합에서 2 번 우승하면 이기는 게임에서 미리 2 번 이기면 나머지 한 번은 할 필요가 없다. 이런 가능성을 생각해서 미리 많이 잘라버리면 그 만 큼의 실행시간이 빨라진다.

가능한 경우를 모두 검사하는 방법에는 보통 두 가지 유형의 문제로 나뉠수가 있다.

• 부분집합형 백트래킹
• 팩토리얼형 백트래킹

예를 들어 , 주머니 속에 7 개의 공이 있고 , 각 공에는 번호가 부여되어 있다.

부분집합형

주머니에서 몇 개의 공을 꺼내어 합이 13 이 공들을 찾는 경우에는 2^7 가지의 부분집합을 모두 검사해야 한다.

한 개 뽑는 경우

• 6
• 2
• 9
• ..

두 개 뽑는 경우

• 6 , 2
• 6 , 9
• 6 , 8
• ...

세 개 뽑는 경우

• 6 , 2 , 9
• 6 , 2 , 8
• ...

...

7 개 모두 뽑는 경우

• 6, 2, 9 , 8 , 3 , 4 , 7

팩토리얼 형

7 개의 공을 임의로 나열했을 때 인접한 수의 곱이 최대 인 경우는 어떤 경우인가를 알고자 할 때 7! 가지의 모든 경우를 생각해야 하므로 이는 팩토리얼 형 문제라고 생각할 수 있다.

• 6 2 9 8 3 4 7
• 6 2 9 8 3 7 4
• ...

(문제) sum of subset 

6 , 1 , 9 , 8 , 3 , 4 , 7

총 합은 38 , 합은 반은 19 이다.

이 수들을 적절히 뽑아 19 를 만들 수 있는 방법의 수를 구하는 문제.

부분 집합형 문제의 기본 틀

첫째 원소, 둘째 원소 2 개 있을 때 부분집합의 수는 4 개이다.

• 2 가지 모두 포함하는 경우 (o o)
• 첫 원소 포함 , 둘째 원소 포함하지 않는 경우 (o x)
• 첫 원소 포함하지 않고 , 둘째 원소 포함하는 경우(x o)
• 2 가지 모두 포함하지 않는 경우 (x x)

o 를 1 로 x 를 0 으로 놓으면 ,

• 1 , 1
• 1 , 0
• 0 , 1
• 0 , 0

원소의 수가 2 개 일 때

이를 구현하기 위해 배열(배열명을 include[] 라 하자)을 사용하여

원소의 수가 3 개일 때

(샘플 문제)수의 부분합 문제로 조금씩 실행 속도를 높여 보기로 하자. 문제는 전제 합의 반 50 이되는 원소를 골라내는 문제이다. 
주어지는 데이터는 40 20 30 10 (수의 부분합 풀이)

12시 3시 6시 9시만 가르킬 수 있는 시계들이 9개 있다.

각 시계를 90도 회전 할 수 있는 9개의 버튼을 선택적으로 눌러서 모든 시계들이 12시를 가르킬 때

의 경우의 수 중에 사전 순으로 가장 빠른 것을 찾아라.

많이 헤맸지만 몇 가지 힌트를 듣고 풀 수 있게 되었다. 

시계는 많이 돌릴 필요도 없고 4번을 돌리면 제 자리로 돌아온다.

그대로 놔두던지, 1번, 2번, 3번, 4번(다시제자리로)

버튼에 대한 동작 5개만 있으면 된다. 

이 버튼을 누르는 경우의 한해서 완전탐색을 해주면 답이 나온다. 

for문을 9개써서 시간 안에 답이 나올 수 있는지에 대한 의문이 드는데, 

직접 몇 개 계산을 해보면 된다. 

5의 9승 => 1953125번

최악의 경우 2천만번 정도 순회하면 완전 탐색을 모두 수행 할 수 있다. 

사전 순으로 앞에 것을 출력하라고 했으므로 실제로 다 돌 필요도 없다. 

나와 같은 경우 맨 처음에 스위치의 ABCD를 string으로 표현해서 인덱스에 접근했는데, 

이렇게 하면 시간 안에 답이 안나온다.....

한 번 스트링을 인트형으로 표현해볼까 해서 해봤는데

시간 안에 답이 나온다. 물론 2.xxx초가 걸리는 무지막지한 코드이지만 시간안에 답만 나오면 되므로 문제는 없다.