- nQueens Sprint
- BFS & DFS
- Back Tracking
@@ 오늘은 대망의 악명 높다고 여러번 들은 n Queens 문제를 푸는 날이었다.
아래는 오늘 전략 토론 때 백트래킹을 찾아보면서 정리한 내용이다. 블로깅을 참조했는데 해당 스프린트에 대한 전략을 짜기전에 팀에서 해당 주제를 나눠서 조사하는 시간을 가졌다.
트리구조로 돼있는 설명을 보고 나도 해당 스프린트를 트리 구조로 이해했는데, 전략 회의때 엔지니어분 설명을 들으니 트리구조로 짜기엔 적합하지 않다(?)는 답변을 받았다.
생각해보니 이론적으론 트리가 이해하기 쉽지만 코드로 구현하기에 해당 루트를 잡는 문제도 그렇고 말씀해주셨듯 노드의 중복을 거르기에도 적합하지 않겠다는 생각이 들었다. (사실.. 가능할 것 같기도 한데, 아닌것 같기도 하고 아직은 명확하게 판단이 안선다. 한번 맨땅에 헤딩하듯 해볼까 싶기도 하고...근데 아무리 생각해도 해당 트리를 객체로 구현하기엔 무리가 있는 것은 맞는 것 같다.)
트리구조로 백트래킹을 이해했기 때문에 해당 스프린트에서 백트래킹을 어떻게 활용하는 것인지, 헬퍼 코드들을 오늘 완성해서 테스트를 패스했는데 이 헬퍼코드들은 또 어떻게 활용할 수 있을지 아직은 감도 안오고 어렵기만 하다.
내일까지 한번 마지막 퀸즈 메소드들 통과를 위해 고민해봐야겠다.
-
DFS
하나의 정점으로 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법. 어떠한 방향으로 쭉 뻗어진 것을 끝까지 탐색 후 더는 길이 없다고 생각하면 다음으로 넘어간다. (모든 노드를 돌아보고 싶을 때 이 방법을 택한다) 단순 검색은 너비우선 탐색보단 느리지만 조금 더 간단하다는 장점이있다. -
BFS
깊이 우선 탐색 방법과 반대 개념으로 하나의 정점으로 싲가해서 그 정점과 맞닿아있는 가지들을 우선적으로 본 후 , 그 다음줄에있는 가지들, 그 다음줄에 있는 가지들을 차례로 보는 방법을 말한다.
두 노드 사이의 최단 경로, 혹은 임의의 경로를 찾고싶을 때 이 방법을 사용한다. -
튜플 자료형
여러개의 자료를 하나의 변수로 관리할 때 사용. 리스트와 거의 같지만 데이터를 변경할 수 없다.
조회하는 메소드만 거의 사용한다. (자바스크립트에는 없는 자료형) -
백트래킹
-
모든 경우의 수를 전부 고려하는 알고리즘.
-
모든 조합의 수를 살펴보는 것을 의미(단 조건이 만족할 때만)
-
해를 찾아가는 도중 지금의 경로가 해가 될것 같지 않으면 그 경로를 더 이상 가지 않고, 다시는 이 후보군을 체크하지 않을 것을 표기한 뒤 이전 부모로 되돌아 가고 다음 자식 노드로 가는 식으로 결국 최적의 해를 찾는 기법. (반복문의 횟수를 줄일 수 있으므로 효율적). 가지치기라고도 불린다.
*해: 노드의 유망성.
-
상태공간을 트리로 나타낼 수 있을 때 적합한 방식
- 상태공간 트리 : 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리
-
일종의 트리 탐색 알고리즘
-
방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다.
-
일반적으로 DFS가 더 편리하지만 트리의 깊이가 무한대가 될 경우엔 사용해선 안된다.
-
분기점 없이 길이만 길 경우엔 스택 오버플로우가 발생할 수 있다.
-
CSP(Constrain Satisfaction Problems)을 해결하기 위해 쓰인다.
- CSP: 조건만족 문제
-
Promising : 해당 루트가 조건에 맞는지를 검사하는 기법
-
Pruning (가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법.
-
-
백트래킹의 적용
-
n을 리스트 길이라고 했을 때 특정 숫자를 찾는 시간 복잡도는 O(n), 이 경우엔 백 트래킹은 의미가 없다.
-
N-Quuens 의 문제 경우, N*N 체스판에 최대한 퀸을 많이 올려놓고 싶은데 서로 공격을 하지 못하게 올려놓아야 하므로, 시간 복잡도는 O (N^N)을 갖게 된다.
-
체스판 왼쪽부터 퀸을 차례대로 두면 한 컬럼에 하나의 퀸밖에 둘 수 없다는 걸 알 수 있다.
-
이 때 백트래킹을 이용하면 시간 복잡도를 줄일 수 있다.
- 한 컬럼에 Queen을 두었으면 오른쪽 컬럼에 가능한 자리에 Queen을 둔다. 또 다시 오른쪽 컬럼 중에서 가능한 자리에 Queen을 둔다. 이 과정을 반복한다. 만약에 N개의 Queen을 두었다면 카운트를 증가 시킨다. 이제부터가 중요한데, 성공하기 직전으로 상태를 되돌린다(back). 그리고 N번째 컬럼 중 다른 칸들을 시도한다. 만약에 없다면 N-1번째 컬럼에 있는 Queen을 들어서 다음으로 가능한 칸으로 옮긴다. 다시 N번째 컬럼에 Queen을 둘 수 있는 곳을 찾는다. N-1번째 컬럼의 모든 경우를 시도했다면, N-2번째로 되돌아가 다음으로 가능한 위치로 Queen을 옮긴다.
-
- N-Queens 문제는 서로 공격하지 않는 퀸을 최대한 많이 두는 모든 경우의 수를 찾는 것이다.
- 서로 공격하지 않아야 하므로 k 번째 컬럼에 넣는 퀸을 두려면 해당위치에서 왼쪽과 왼쪽위 대각선, 외쪽 아래 대각선엔 다른 퀸이 없어야 한다. 이 조건이 바로 한정 조건(CSP) 가 된다.
- 이 한정 조건으로 인하여 모든 경우의 수를 검색할 때보다 훨씬 적은 경우의 수를 얻게 된다.
참고:
https://medium.com/@jeongdowon/알고리즘-backtracking-이해하기-13492b18bfa1
