본문 바로가기

Programming/Algorithm

[Algorithm]BackTracking

백트래킹 알고리즘은 일어날수 있는 모든 경우의 수를 고려해,

각 경우의 수별로 조건에 만족하는지 찾아 해가 될수 있는지 없는지 판별하는 알고리즘이다.

일어날 수 있는 경우의수를 다 검색 하기 때문에 해는 반드시 존재한다는 특성을 지니고 있다.


:: Bit-pattern

두 정수 n , k 를 입력으로 받아 k 개의 1 을 가진 n 자리 이진 패턴을 출력하는 프로그램을 작성 하세요.

입력

두 정수 n , k 가 입력으로 주어진다. (0 < n <= 30 , 0 <= k < 8 , n >= k)

출력

결과를 내림차순으로 출력한다.

입출력 예

입력 2 1 출력 10 01 입력 2 0 출력 00 입력 3 2 출력 110

101

011

[출처] www.dovelet.com 


위 문제로 예를 들면 모든 경우의 수는 아래의 그림과 같다.


N=3,K=2일때 위 그림에서 해는 110,101,011이다.

백트래킹 알고리즘은 위의 그림처럼 나타낼수 있는 모든 경우의 수를 조사하여 내가 찾고자 하는 해를 만족하는 조건을 설정하여 주면 된다.

모든 조건을 탐색한다는 것은 트리구조에서의 깊이 우선 검색과 비슷한 모양을 띄고 있다.


:: Bit-pattern, Using Array

:: Bit-pattern, Using bit



'Programming > Algorithm' 카테고리의 다른 글

[Algorithm] 징검다리 건너기  (0) 2013.02.13