알고리즘 마라톤 5일차
오늘 공부한 것
BAEKJOON ONLINE JUDGE(BOJ)
- 2108 통계학
- 2630 색종이 만들기
- 15650 N과 M(2)
- 9663 N-Queen
- 2579 계단 오르기
알고리즘을 풀며 느낀 점 & 생각
-
오늘은 N-Queen을 푼 것으로 다 했다.
사실 15650 N과 M(2)를 풀면서 백트래킹을 처음 접했다.
백트래킹을 구글에 검색하면 맨 윗줄에 이런 설명이 나온다.백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.
백트래킹이 뭔지도 알겠고, 이 문제를 손으로는 어떻게 풀어야 하는지도 알겠는데 코드로 구현이 너무 어려웠다.
결국 파이썬 코드를 찾아 자바스크립트로 변환했고 하나하나 뜯어보면서 재귀를 어떻게 사용했는지, for문은 어떻게 사용했는지 확인했다.
겨우 이해했다고 생각한 뒤 만난게 N-Queen이다.
(N-Queen의 백준 문제 링크)N개의 퀸을 NxN의 체스판에 서로를 공격할 수 없도록 놓는 경우의 수를 찾는 문제다.
일단 퀸이 어떻게 움직이는 지도 몰라서 찾아봤는데, 안 가는 곳이 없다.
사실 손으로 그리면 (0,0)에서 (0, N-1)까지 한 번씩 퀸을 두면서 다른 칸들을 지워나가면 된다.
그걸 코드로 구현하려니 이런 의문점이 생겼다.
- 예를들어 (0,0)에 퀸을 두고 (1, 2)에 퀸을 두었다고 하면, (0, 1)은 (0,0)에 퀸을 두면서 이미 false(퀸을 둘 수 없는 상태)일 것이다.
- 그래서 (1, 2)에 퀸을 두며 가로에 위치한 (0,1)을 false로 바꾸려고 하지만 이미 false인 상태이다.
- 백트래킹을 위해 (1,2)에 퀸을 두었던 것을 취소(?) 하면서 false 상태도 되돌려야 하는데 (0, 1)을 true로 바꾸면 (0, 0)에 있는 퀸의 규칙에 어긋난다.
1차원에서는 잘 사용했던 true/false를 버리고 다른 방법을 모색했다.
처음에는 객체{false: 0} 이런 식으로 사용해볼까도 생각했는데, 너무 과하다는 느낌이 들었다.
그래서 만든 것이 아래의 코드다.
let graph = Array.from(new Array(N), () => new Array(N).fill(0));
아주 단순하게 0으로 채워놓았고 0이 1차원에서의 true와 마찬가지의 의미였다.
여기에서 퀸에 의해 false가 되는 칸들은 -1을 해주었고, 백트래킹을 할 때는 다시 +1을 해주는 방식이었다.
그러다 보면 제 때 0(true)로 돌아오는 것을 확인했다.
그렇게 만든 코드가 N-Queen 이다.
사실 만족스러운 코드는 아니지만 이해하고 구현한 것에 일단 의의를 두고 싶다.
무엇보다 한 번에 통과해서 너무 기쁘다. (성능은... 😅)
- trim() 확인하자...
이번 주 내내 말하게되는 주제가 백준 알고리즘 입출력이다.
긴 말 필요없이 trim() 확인하자.
너무 쉬운 문제를 trim()을 써주지 않아 4시간을 날렸다.
trim()으로 그만 삽질하기🙅🏻♀️🙅🏻♀️🙅🏻♀️
