목표 : 스택 , 큐 개념과 기본 구현 코드에 대해 알아보자.

✏️백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
완전 탐색을 하는 도중, 현재 탐색이 무의미한 경우 되돌아가는 알고리즘

왼 : 완전 탐색 진행하는 깊이 우선탐색(DFS)/ 오 : 무의미한 탐색을 건너뛰는 가지치기 방법(백트래킹)

유망함수❓

해가 될 가능성을 판단하기 위해 유망함수를 정의함.

• 유망함수 예시

{1,2,3,4,5} 중 2개의 숫자를 뽑아서 합이 8을 초과하는 경우 알아내는 백트래킹 알고리즘을 알아보자. 뽑는 순서가 다르면 다른 경우의 수로 간주하자.

01 단계 : 유효한 해의 집합 정의.
[1,2] [1,3] [1,4] [1,5] [2,1] [2,3] [2,4] [2,5] [3,1] [3,2] [3,4] [3,5] [4,1] [4,2] [4,3] [4,5] [5,1] [5,2] [5,3] [5,4]

02 단계 : 정의한 해의 집합을 그래프로 표현.

03단계 : 처음 뽑은 숫자가 4미만이면 백트래킹한다 - 전략 사용.

04 단계 : 이와같이 나머지도 탐색

---

• 구현 코드

def 백트래킹(n):
    if 정답이면 :
        출력 or 저장
    else :
        for 모든 자식 노드에 대해 :
            if 유망한지확인(m) :
                자식노드로 이동
                백트래킹(n+1)
                부모노드로 이동

def 유망한지확인(m):
    if 조건에 안맞으면 :
        return False
    return True
출처: https://edder773.tistory.com/75 [개발하는 차리의 학습 일기:티스토리]

(https://www.youtube.com/watch?v=KNysNGNp5t4 강의, 골든레빗 블로그 [코딩테스트 합격자 되기] 백트래킹- 백트래킹과 백트래킹 알고리즘 개념을 이용하여 개념을 익혀보았다.)