N-Queens 스프린트를 진행했다.
n-queens는 n*n의 체스판에 n개의 여왕을 둘 수 있는 모든 경우의 수를 탐색하는 알고리즘이다.
이번 스프린트를 하기 위해서 필요한 개념은 recursion, tree, backtracking, DFS (BFS) 개념이다.
스프린트를 진행하기 앞서 무슨 개념인지 살펴보자.
1. 재귀 recursion.
어떤 문제를 해결하기 위해서 문제를 나눌 수 있을 때까지 작게 나눈 후, 작아진 문제부터 풀어나가는 알고리즘을 말한다.
재귀하면 인셉션이 생각난다. 꿈속에 꿈속에 꿈속에 꿈속.....
재귀 알고리즘은 다음과 같은 상황에서 사용하기 적합하다.
1. 주어진 문제가 작은 문제로 나누어질 수 있는 경우 (2^3을 생각해보면 2*(2*2)라고 생각할 수 있다.)
2. 중첩된 루프가 많거나 루프의 깊이를 알 수 없을 때. (가위바위보를 3판 했을 경우 나올 수 있는 모든 경우의 수)
복잡한 자료구조 알고리즘은 ,,재귀적으로 생각해야 한다.
재귀적 사고.. 나눌 수 있을 때까지 작게 나눈다. 나눈 문제들을 푼다.
[재귀 알고리즘은 커다란 루프라고 생각하면 될 것 같다. 반복문으로 풀 수 있는 문제는 재귀로도 풀 수 있다.]
2. Tree 자료 구조
이번 n-queens 스프린트에서는 모든 경우의 수들을 tree형 자료구조로 생각한다.
tree형 구조는 노드가 부모와 자식의 관계를 갖는다.
tree형의 자료구조를 이해하고 문제를 해결한다.
3. Backtracking
트리형 자료구조에서 backtracking이라는 개념을 이용한다.
backtracking은 단어의 느낌 그대로 뒤로 간다는 말이다.
단순하게 루트를 기점으로 트리의 모든 노드들을 순회한다면 시간 복잡도가 매우 높아진다.
하지만 트리구조는 부모 노드와 자식 노드로 나뉘어 있다!
부모 노드가 조건에 맞지 않는다면 우린 굳이 자식 노드의 경우의 수까지 접근할 필요가 없다.
집에서 핸드폰을 잊어버렸다.. 이때 우리가 할 수 있는 방법은?
A. 모든 방을 순회한다.
1. 내 방을 확인한다.
1.1 핸드폰이 있으면 종료
1.2 없다면 2번으로.
2. 안방을 확인한다.
2.1 핸드폰이 있으면 종료
2.2 없다면 3번으로
3. 서재를 확인한다.
3.1 핸드폰이 있으면 종료
3.2 없다면 4번으로
4. ......
5. ....
찾을 때까지 모든 계속 행위를 반복할 것 이다.B. 소리가 나는 공간을 순회한다.
[집에 A라는 사람이 있고 핸드폰은 진동,소리가 켜져 있는 상태]
1. A에게 전화를 걸어달라고 부탁한다.
2. 진동이나 벨이 들리는지 확인한다.
3. 내 방을 확인한다. (소리가 나는지)
3.1 소리가 난다면 그 공간을 위주로 찾는다.
3.2 안난다면 4번으로
4. 안방을 확인한다. (소리가 나는지)
4.1 소리가 난다면 그 공간을 위주로 찾는다.
4.2 안난다면 5번으로.
소리가 나지 않는 공간은 찾아볼 필요가 없다.
이 때 우리는 집 안의 방들을 다 찾아보는 방법도 있겠지만
가족에게 핸드폰에 전화 좀 해달라고 하면 벨이나 진동이 울리는 곳 위주로 찾으면 되기 때문에 더 빠르게 찾을 수 있다.
이 때 벨이나 진동이 들리는 공간은 조건에 부합하는 공간!
그 외 나머지 공간은 굳이 보지 않아도 된다.
부모 노드에서 조건이 부합한 지 확인하고 없다면 그다음 형제 노드를 탐색하는 방식을 backtracking이라 한다.
4.Depth-First Search 깊이 우선 탐색과 Breadth-frist-search 너비 우선 탐색
말 그대로 노드의 방향을 정하고 그 노드의 방향으로 조건이 부합하는 노드가 나올 때까지 탐색하는 방법이며,
리프가 나왔을 때 (더 이상 자식 노드가 없는 노드가 나올 때까지)까지도 조건에 부합하는 노드가 없다면
해당 부모 노드의 자식노드가 있다면 그 곳을 탐색하고 자식노드가 없다면 부모노드의 부모노드의 자식 노드를 탐색하는 방식이다.
(자식 노드의 자식 노드들을 차례대로 탐색한다.)
장점
- 경로상의 노드들만을 기억하기 때문에 요구하는 저장 공간의 크기가 비교적 적다.
- 목표 노드가 깊은 단계에 있을 경우, 해를 빨리 구할 수 있다.
단점
- 해가 없는 경로에 깊이 빠질 가능성이 있다. (backtracking을 사용해서 단점 보완)
- 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
너비 우선 탐색은 루트의 자식 노드의 모든 형제들을 순회하며 탐색한다.
자식노드의 형제 노드들을 탐색한 후 또 그 형제 노드들의 자식 노드들을 순회한다.
(형제 노드들을 차례대로 탐색한다.)
장점
- 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.
단점
- 경로가 매우 길 경우(형제 노드가 많을 경우)에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
- 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
- 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.
https://www.quora.com/What-are-some-real-life-examples-of-Breadth-and-Depth-First-Search
댓글