[묘공단] 코딩 테스트 합격자 되기 6주차

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다.

 

12. 백트래킹

 

백트래킹이란?

• 어떤 가능성이 없는 곳을 알아보고 되돌아가는 것

 

 

백트래킹 알고리즘이란?

 

• 가능성이 없는 곳에서는 되돌아가고 가능성이 있는 곳을 탐색하는 알고리즘 이다
  답을 찾는 과정에서 가능성이 없는 곳에서 백트래킹
• 백트래킹을 통해 해가 될 가능성이 없는 탐색 대상을 배제할 수 있으므로 탐색 효율이 단순히 완전 탐색하는 방법보다 백트래킹이 효율적이다

 

유망 함수란?

 

• 백트래킹 알고리즘의 핵심, 해가 될 가능성을 판단하는 것이다
• 가능성은 유망 함수라는 것을 정의하여 판단한다

 

과정

1. 유효한 해의 집합 정의
2. 위 단계에서 정의한 집함을 그래프로 표현
3. 유망함수를 정의
4. 백트래킹 알고리즘을 활용해서 해를 찾음
   
   
   

 

관련 문제 모음

 

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/92345

프로그래머스

출처

 

https://goldenrabbit.co.kr/product/javapass/

[되기] 코딩 테스트 합격자 되기(자바 편) - 골든래빗