체대출신 코더의 개발자 성장기
극악의 알고리즘 N-queens 본문
화,수,목 3일동안 N-Queens 라는 알고리즘 스프린트를 진행했다.
게임 룰은 다음과 같다.
1) N * N 의 체스판에 N개의 룩을 놓아야 한다.
2) N* N 의 체스판에 N개의 퀸을 놓아야 한다.
룩은 수평,수직으로만 움직일 수 있고
퀸은 수평,수직,대각선으로 이동이 가능하다.
1번과 2번의 경우의 수를 각 각 모두 구해야 하는데 룩과 퀸의 이동범위가 달라 꽤 애를 먹었다.
어렵기로 유명한 알고리즘 문제이지만, 그동안 꼬아서 푸는 문제를 푸는데 재미가 붙어서 '나 혼자 엄청 독창적인 생각을 하고 말거야' 라는 생각을 가지고 스프린트에 임했던 것 같다.
처음에 알고리즘을 풀기전 주어진 메소드들을 페어와 직접 작성해보는 시간이 있었는데, 우리는 처음 속도는 남들보다 느렸지만,,
디버깅을 꼼꼼히 그리고 천천히 진행하여 동기 팀들 중 가장 빨리 메소드 작성을 끝냈다!!!
우리가 작성하게 된 메소드는 여러가지가 있었는데, 어떤 룩을 체스판위에 놓았을 때 그 룩이 다른 룩과 충돌하는지를 확인하는 메소드였고,
다른 것은 퀸의 충돌에 대한 것 이었다.
충돌에 대한 계산은 컴퓨터가 모두 해주도록 만들었으니 나는 배열만 넘겨주면 된다!! 라고 생각한것이 큰 오만이었다..
이번 문제를 풀면서 나온 알고리즘은 총 2가지였는데, 한가지는 내 아이디어였고, 나머지 한가지는 내 아이디어의 구현이 너무 되지 않아 조언을 받아 엔지니어분께 받은 힌트로 만든 알고리즘이었다.
둘다 결국 구현은 하지 못했지만..
위의 알고리즘을 실행하기 위해서는 준비물이 필요한데
(n이 4라고 가정한다.)
1) 0으로 가득찬 n길이의 빈배열
arr = [0,0,0,0]2) 1번을 토대로 만들어진 빈 체스판(체스판은 2중배열로 만들어진다.)
[[0,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]3) 1번을 토대로 만들어진 한 행에서의 룩의 모든 움직임을 구현한 배열
[[1,0,0,0],
[0,1,0,0],
[0,0,1,0],
[0,0,0,1]]1. 3의 배열을 빈체스판의 첫번째 줄부터 차례대로 바꿔준다.
충돌이 있는지 없는지 확인한다.
충돌이 있다면 버리고, 충돌이 없다면 퀸 혹은 룩의 수를 하나 줄여주고(마킹을 햇다는 의미로) 다음단계로 넘어간다.
[[1,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,1,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,0,1,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,0,0,1],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
3. 다음단계는 줄만 다음줄로 넘어가고 똑같이 충돌을 확인한다.
충돌이 있다면 버리고, 충돌이 없다면 퀸 혹은 룩의 수를 하나 줄여주고(마킹을 햇다는 의미로) 다음단계로 넘어간다.
// 2번에서 1번째의 경우만 보도록 한다.
[[1,0,0,0],
[1,0,0,0]
[0,0,0,0],
[0,0,0,0]] ==> 룩 : x , 퀸 : x
[[1,0,0,0],
[0,1,0,0],
[0,0,0,0],
[0,0,0,0]] ==> 룩 : o, : x
[[1,0,0,0],
[0,0,1,0],
[0,0,0,0],
[0,0,0,0]] ==> 룩 : o, 퀸 : o
[[1,0,0,0],
[0,0,0,1],
[0,0,0,0],
[0,0,0,0]] ==>룩 : o, 퀸 : o
4. 이런식으로 반복하다 마지막 줄에 다다랐을때
충돌이 없고, 룩과 퀸을 모두 소진했다면 그 결과값을 출력해준다.
룩과 퀸의 갯수가 하나라도 남아있다면, 조건을 만족하지 못했기 때문에 버린다.
5. 모든 과정을 거치면 거칠수록 트리구조의 형식처럼 충돌이 없는 경우가 가지를 뻗어나가 모든 경우의 수를 만족하는 체스판을 얻을 수 있다.
이방법의 경우는 2번과 3번의 경우처럼 배열들을 바꿔주는게 마음대로 되지가 않아서.. 남들이 다끝낼 시간에 포기를 하고 말았다.
배열의 경우에는 왜인지 모르겠지만, 위처럼 순차적으로 배열들이 담기지 않고 계속, 다음 값들로 배열이 담겨서 컨트롤이 되지 않았다.
[[1,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,1,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,0,1,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,0,0,1],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]] //이렇게 담겨야하는데
[[0,0,0,1], //이렇게 담김
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,0,0,1],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,0,0,1],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
[[0,0,0,1],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
결론은 앞서 말했다시피 배열을 컨트롤하는데 있어서 너무 많은 시간을 보내버려서 .. 대 실패 였다.
다행히도 나말고 다른팀도 못풀긴했지만.. 뭔가 자존심이 상하기도하고 내 의견을 믿고 따라와준 페어분한테 정말 죄송했다.
또한 엔지니어분의 피드백을 수용하고, 그것에 대해 내 아이디어에서 변환하는 과정을 거치면서 이해가 안가는 부분이 많아 페어 분과 이야기를 많이했는데, 주로 내가 말귀를 못알아먹어서... 페어분을 힘들게 했던 것 같다.
이번 스프린트를 거치며 느낀점...
1) 알고리즘은 내가 생각한 것보다 훨씬 극악의 난이도이다.
2) 주소값을 참조하는 배열의 삽입,교환,삭제등에 대해 컨트롤하는것에 대해 다시한번 공부해보고 되새김질 할 필요가 있다.
3) 혼자 생각하지 말고, 같이 생각하려하자.. 혼자 생각하는 시간이 많아지면 고집이 생겨 상대방의 의견에 많이 경청을 할 수 없게 된다.
4) 알고리즘은 자세하고 구체적이게 적어줘야한다.(설계와의 연관성)
과제 구현율이 평균보다 많이 떨어지는 것 같다.. 또한 유독 내가 속한 팀이 그러다보니 소위 현타가 많이 오고 있다.
앞으로의 과정 잘 따라갈수있을지.. 걱정된다ㅜ 화이팅!!