백트래킹

백트래킹 역시 특정 알고리즘으로 정해져 있는 것이 아니다.

짜여진 코드에 불필요한 계산이 포함되어 있는지 확인하고 삭제함으로써 연산 속도를 줄여서 시간초과를 피하는 것이다.

 

대표적으로 n-queens문제가 있다.

 이런 체스판에 각 퀸이 서로를 공격하지 못하도록 퀸을 배치하는 것이다. 이때 가능한 경우의 수는 수백억이 넘는다. 하지만 실제 가능한 해는 92개? 정도 밖에 안된다. 92개를 찾으려고 수백억개를 계산할 필요가 있는가? 수백억은 컴퓨터로 계산해도 시간이 1분가까이 걸린다. 이런 문제점을 해결하기 위해서 사람들이 시간을 줄이려고 노력했고, 이런 과정자체가 하나의 백트래킹이 된 것이다.

  백트래킹은 다른 말로 가지치기라고도 한다. 하지만 퀸을 놓을때 상하좌우,대각선으로 겹치는 퀸이 있는지 확인하면 대부분의 경우에서 발생하기 때문에 연산이 현저히 줄어든다. 

하지만 주의할 점은 백트레킹이라고 만능이 아니다. 시간을 얼마정도 줄일 수 있는지 계산하기는 사실상 쉬운 일도 아니며 가지를 잘못치거나 칠 수 있는 가지를 다 쳐도 별로 유의미한 차이가 나지 않는 경우도 있기때문이다. 그렇기에 가지치기를 했는데도 시간초과가 난다고 이왜틀? 하면 안된다. 접근 방법이 애초에 잘못된 것일 수 있으니까 말이다.