코딩테스트 - 패스트캠퍼스 챌린지 22일차

수강한 강의
Chapter 21 백 트래킹
- 백 트래킹 알고리즘 이해

학습 후기
백트래킹(Backtracking)
백트래킹 또는 퇴각 검색으로 불리며 제약 조건 만족 문제에서 해를 찾기 위한 전략이다.
모든 조합을 시도해서 문제의 해를 찾으며 퇴각 검색을 통해 많은 부분의 조합들을 배제하기에 풀이 시간이 단축된다.
모든 조합을 DFS방식으로 확인하며 조건이 맞지 않으면 포기하고 바로 해가 될만한 곳으로 넘어가서 탐색
용어
Promising: 조건에 맞는지 검사하는 것
Pruning: 가지치기로 조건에 맞지 않으면 포기하고 바로 다음 탐색할 곳으로 옮겨 시간을 절약하는 기법

대표적인 문제: N Queen
대표적인 백트래킹 문제로 NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제로 퀸은 수직, 수평, 대각선에 있는 말을 공격 가능함으로 배치된 퀸끼리 서로 공격할 수 없는 위치에 배치해야 한다.

N Queen 문제에서의 백트래킹

Promising: 퀸이 서로 공격 가능한 상황인지 확인 - 같은 row에 있는지, 같은 col에 있는지, 대각선에 있는지

Pruning: 맨 위에부터 배치하며 Promising으로 조건을 확인하고 더 이상 진행이 어려울 경우 다른 경우를 체크함.

Promising에서 한 행에는 하나의 퀸 밖에 위치할 수 없으니 따로 처리 안 한다.

한 열에 하나의 퀸만 위치하는 걸 체크하는 방법은 좌표의 y 값을 확인한다.

대각선을 확인하는 방법은 해당 퀸의 좌표가 (ax, ay)이고 비교하려는 퀸의 좌표가 (bx, by)이면

Math.abs(bx - ax)와 by - ay의 크기가 같은지 확인하면 된다.

N Queen 문제 해를 찾는 과정

https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C#N_%ED%80%B8_%EB%AC%B8%EC%A0%9C

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전

백트래킹은 전체 탐색보다는 가지치기를 함으로써 시간 복잡도에서 이점을 가지고 온다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.