[묘공단] 코딩테스트 스터디 9주차
[묘공단] 코딩테스트 스터디 9주차
2024.01.27이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 12장 문제풀이입니다 백트래킹 백트래킹과 백트래킹 알고리즘 개념 깊이 우선 탐색, 너비 우선 탐색은 데이터를 전부 확인하는 방법이며 이를 완전 탐색이라고 함 완전 탐색은 모든 경우의 수를 탐색하는 방법이므로 비효율적 따라서 탐색을 하다가 가능성이 없다면 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘을 백트래킹이라고 한다 백트래킹 알고리즘의 핵심은 '해가 될 가능성을 판단하는 것'이며 그것을 유망함수라는 것을 정의하여 판단함 유효한 해의 집합을 정의 위 단계에서 정의한 집합을 그래프로 표현 유망 함수를 정의 백트래킹 알고리즘을 활용해서 해를 찾음 예를 들어 1, 2, 3, 4 중 2개의 숫자를 뽑아서 6보다 큰 조합을 찾을 때 백트래킹을 활용한다면..