[TIL] 20210618 - 항해 12일차

Jihyun·2021년 6월 18일
0

항해99

목록 보기
8/46

알고리즘 마라톤 5일차

오늘 공부한 것

BAEKJOON ONLINE JUDGE(BOJ)

오늘의 알고리즘 코드 깃허브 링크

  • 2108 통계학
  • 2630 색종이 만들기
  • 15650 N과 M(2)
  • 9663 N-Queen
  • 2579 계단 오르기

알고리즘을 풀며 느낀 점 & 생각

  1. 오늘은 N-Queen을 푼 것으로 다 했다.
    사실 15650 N과 M(2)를 풀면서 백트래킹을 처음 접했다.
    백트래킹을 구글에 검색하면 맨 윗줄에 이런 설명이 나온다.

    백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

    백트래킹이 뭔지도 알겠고, 이 문제를 손으로는 어떻게 풀어야 하는지도 알겠는데 코드로 구현이 너무 어려웠다.

    결국 파이썬 코드를 찾아 자바스크립트로 변환했고 하나하나 뜯어보면서 재귀를 어떻게 사용했는지, for문은 어떻게 사용했는지 확인했다.

    겨우 이해했다고 생각한 뒤 만난게 N-Queen이다.
    (N-Queen의 백준 문제 링크)

    N개의 퀸을 NxN의 체스판에 서로를 공격할 수 없도록 놓는 경우의 수를 찾는 문제다.

    일단 퀸이 어떻게 움직이는 지도 몰라서 찾아봤는데, 안 가는 곳이 없다.

사실 손으로 그리면 (0,0)에서 (0, N-1)까지 한 번씩 퀸을 두면서 다른 칸들을 지워나가면 된다.

그걸 코드로 구현하려니 이런 의문점이 생겼다.

  1. 예를들어 (0,0)에 퀸을 두고 (1, 2)에 퀸을 두었다고 하면, (0, 1)은 (0,0)에 퀸을 두면서 이미 false(퀸을 둘 수 없는 상태)일 것이다.
  2. 그래서 (1, 2)에 퀸을 두며 가로에 위치한 (0,1)을 false로 바꾸려고 하지만 이미 false인 상태이다.
  3. 백트래킹을 위해 (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 이다.

사실 만족스러운 코드는 아니지만 이해하고 구현한 것에 일단 의의를 두고 싶다.

무엇보다 한 번에 통과해서 너무 기쁘다. (성능은... 😅)

  1. trim() 확인하자...
    이번 주 내내 말하게되는 주제가 백준 알고리즘 입출력이다.
    긴 말 필요없이 trim() 확인하자.
    너무 쉬운 문제를 trim()을 써주지 않아 4시간을 날렸다.
    trim()으로 그만 삽질하기🙅🏻‍♀️🙅🏻‍♀️🙅🏻‍♀️
profile
Don't dream it, be it.

0개의 댓글