[Algorithm] 완전탐색

완전탐색

완전탐색 알고리즘은 문제는 해결하는 전략 중 하나로,

가능한 모든 경우의 수를 다 찾고, 그 중에서 답을 고르는 전략이다.

하지만, 가능한 모든 경우의 수를 다 나열해 보는것은 생각보다 어려운 일이다.

 

우리가 수학에서 배우는 단순한 경우의 수를 예로 들어보자.

1~4 까지의 숫자가 적힌 공들 중 임의의 두 공을 고르는 모든 경우의 수는 총 6가지이다. 

(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

수학적으로는 조합이라는 개념으로 이를 표현한다.

Combination(4, 2) = 6

 

이렇게 단순하게 모든 경우의수를 생각해낼 수 있는 문제도 물론 존재한다.

하지만 다음과 같은 문제는 어떨까?

 

Queen은 가로, 세로, 양쪽 대각선 모두 공격이 가능하다.

8 x 8 체스판 위에 8개의 Queen을 서로 공격할 수 없게 배치해야한다.

가능한 모든 경우의 수를 구하시오.

가능한 해 중 하나

이와 같은 문제는 수학에서 단순하게 공식처럼 배운 개념만으로는 모든 경우의 수를 나열하기 어렵다.

단순한 순서쌍과 같은 형태라기보다는 어떤 상황 자체를 나열해야한다.

그러므로 모든 경우의 수를 표현해내기 위해서는 굉장히 다양한 방법들이 활용될 수 있고,

같은 완전탐색 문제라도 형태나 난이도가 상당히 달라질 수 있다. 이 점을 주의해야한다.

 

 

정규화

특정 형태의 답만 고려할 수 있다면?

 

순서의 강제

순서를 강제시킬 수 있다면?

 

 

 

무차별 대입법

algorfati.tistory.com/129

무차별 대입법

 

순열, 조합

algorfati.tistory.com/130

순열, 조합

 

비트마스크

algorfati.tistory.com/128

비트마스크

 

상태 공간 탐색

 

https://algorfati.tistory.com/132

상태 공간 탐색