오늘은 백트래킹 알고리즘에 대하여 알아보려고 한다.
프로그래머스 코딩테스트 연습문제를 풀어보던 중 N-Queen 이라는 문제가 있다. 체스판에 가로 세로 대각선을 움직일 수 있는 퀸을 체스판의 행의 수만큼 배치할 때에, 서로 공격할 수 없게 배치하는 방법의 가지수는 몇 개인가? 라는 문제이다.
공학에서 되게 유명한 문제라고 하는데 비전공자이고 알고리즘 공부를 해보지 않아서 처음에 어떻게 문제를 접근해야되는지 조차 어려웠다. 그래서 서치를 하다보니, 백트레킹 기법을 통해 해결할 수 있다는 걸 알았고, 어떠한 알고리즘인지 알아보도록 하겠다.
\
백트래킹 (Back-Tracking)
상태공간트리를 깊이우선기법(DFS)로 탐색하는 것이다.
방문 중인 노드에서 하위노드로 가도 해답이 없을 경우, 해당 노드의 하위노드를 방문하지 않고, 부모노드로 되돌아가는 기법이다. (back-traking) 이런 기법을 통해서 효율적으로 문제를 해결할 수 있다.
예를 들어, 0은 길이고, 1은 벽으로 구성된 미로가 있다고 가정하자.
상하좌우로만 움직일 수 있다고 가정했을 때 노란 배경이 분기점이 될 것이다. 첫 번째 분기점에서 오른쪽으로 올라가게 된다면 벽을 만나기 때문에 다시 분기점으로 돌아가서 다른 하위 노드로 움직이게 된다.
가지치기 (Pruning)
결국 DFS로 탐색하게 된다면, 모든 노드를 다 방문하도록 하는건데 퍼포먼스가 부족하지 않을까? 특정 노드로 갔을 때 답이 보이지 않는다면 굳이 하위노드를 방문할 필요가 있을까? 이런 문제점을 해결하기 위해 가지치기를 하면된다. 특정 노드에서 이미 정답이 아니라고 판단할 수 있다면 그 하위의 노드들은 모두 방문할 필요가 없기 때문에 퍼포먼스가 향상될 수 있을 것이다.
TIL
오늘은 처음으로 알고리즘을 배워보는 것 같은데, 머신러닝이나 딥러닝 분야 뿐만아니라, 웹 개발에서도 효율을 높이기 위해 여러 알고리즘이 사용될 수도 있을 것 같다. 그리고 가장 중요한 것은 이런 알고리즘을 알기만한다고 효율을 증대시키는건 아니고, 여러가지 문제상황에 대입할 수 있을정도로 사고력을 많이 키워야할 것 같다 파이팅 🤯
