패스트캠퍼스 챌린지 17일차

백트래킹 (Backtracking, 퇴각 검색)

 - 제약 조건 만족 문제에서 해를 찾기 위한 전략

   - 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크 하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단

     되는 즉시 이 후보군은 체크를 하지 않는다는 표기를 하고, 다른 후보군으로 넘어가 최적의 해를 찾는 방법

  - 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)을 상태 공간트리를 통해 표현

    - 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 넘어가 탐색

     • Promising : 해당 루트가 조건에 맞는지를 검사하는 기법

     • Pruning(가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법

 

대표 문제

 • N Queen 문제

   - N * N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제

   - 퀸은 수직,수평,대각선 만 이동 가능

 

 • Promising N Queen (N Quenn 조건 검사)

  - 퀸의 이동할 수 없는 위치가 있는지 판별

    -> 수직 체크 : y값이 같은지만 확인하면 됨

    -> 대각선 체크 : abs(퀸 y, - 현재 y) = 1. (현재 x - 퀸 x) = 1 조건이 만족할 경우 대각선 

 • pruning N Queen 문제 (N Queen 가지치기)

  - 한 행에는 하나의 퀸만 위치할 수 있다

  - 맨 위에 있는 행부터 퀸을 배치하고, 다음 행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치(Promising)

  - 다음행에 해당 퀸을 배치할 수 없는 경우에는 퀸을 배치하지 않고 이전 행의 퀸의 배치를 바꾼다.

 

import java.util.ArrayList;

public class NQueen {
    
    private boolean isAvailable(ArrayList<Integer> candidate, Integer currentCol) {
        Integer currentRow = candidate.size();
        for (int index = 0; index < currentRow; index++) {
            if ((candidate.get(index) == currentCol) || (Math.abs(candidate.get(index) - currentCol) == currentRow - index) ) {
                return false;
            }
        }
        return true;
    }
    
    public void dfsFunc(Integer N, Integer currentRow, ArrayList<Integer> currentCandidate) {
        if (currentRow == N) {
            System.out.println(currentCandidate);
            return ;
        }
        
        for (int index = 0; index < N; index++) {
            if (isAvailable(currentCandidate, index) == true) {
                currentCandidate.add(index);
                
                // 재귀를 사용하여 반복하여 체크한다.
                this.dfsFunc(N, currentRow + 1, currentCandidate);
                currentCandidate.remove(currentCandidate.size() - 1);
            }
        }
    }   
}

 

백트래킹 알고리즘까지해서 알고리즘 이론에 대해 강의를 다 들었다 초반에 이해가되며 어렵지 않을것이라고 느껴졌지만 추가 문제들을 보여 쉽지 않다는걸 다시 한번 깨닫게 되었다.

한번만 들을것이 아니라 암기수준으로 외워야 할듯하다..

 

 

 

17일차 인증

 

 

 

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

https://bit.ly/37BpXiC

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