알고리즘에서 '백트래킹(Backtracking)'이란?

보통 freeCodeCamp

보기 및 정답

A 이전 단계에서 작성한 코드의 오류를 되돌려 수정하는 디버깅 기법으로, 소스 코드의 버전을 관리하는 시스템에서 주로 활용된다

B 해를 찾기 위해 가능한 경우를 탐색하다가 조건에 맞지 않으면 이전 단계로 돌아가 다른 경로를 시도하는 알고리즘 기법이다

C 배열의 마지막 인덱스부터 첫 번째 인덱스까지 역순으로 순회하면서 각 원소에 순차 접근하는 방법이다

D 정렬된 데이터 집합에서 끝 부분부터 시작하여 역방향으로 원소를 탐색하면서 목표 값을 찾는 것이다

백트래킹은 탐색 공간에서 유망하지 않은 경로를 조기에 포기(가지치기, pruning)하고 이전 상태로 되돌아가 다른 선택지를 시도합니다. N-Queen, 수독, 조합·순열 생성, 미로 탐색 등의 문제에서 모든 경우를 시도하는 완전 탐색보다 효율적입니다.

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

로그인