시간 제한을 통과하도록 가지치기하기
개선할 수 없는 가지를 제거합니다
시간 제한을 통과하도록 가지치기하기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
가지치기가 중요한 이유
그대로 백트래킹하면 너무 많은 분기를 탐색하여 시간 제한에 걸릴 수 있습니다. 가지치기는 가능성이 없는 분기를 일찍 잘라 내어 빠르게 실행되도록 합니다. ✂️
가지치기란 무엇일까요
가지치기는 어떤 분기가 유효한 답이나 더 나은 답에 도달할 수 없다는 것을 증명할 수 있는 순간 해당 분기를 중단하는 것입니다. 그 분기는 아예 탐색하지 않습니다.
실행 가능성에 따른 가지치기
현재의 부분 선택이 이미 규칙을 어겼다면 즉시 반환합니다. 이 실행 가능성 확인으로 잘못된 상태를 바탕으로 계속 확장하는 일을 막을 수 있습니다.
if violates(cur):
return상한에 따른 가지치기
지금까지 찾은 최선의 답을 추적합니다. 어떤 분기가 도달할 수 있는 최선의 결과조차 현재 답보다 나쁘다면 그 분기를 잘라 냅니다. 이것이 분기에 대한 상한입니다.
코드에서 가지치기하기
여기서는 낙관적으로 추정해도 현재 최선의 답을 이길 수 없을 때 상한이 해당 분기를 중단합니다.
if cur_cost + best_possible <= best:
return선택 순서를 현명하게 정하기
가장 가능성이 높은 선택을 먼저 시도하면 더 빨리 좋은 답을 찾을 수 있습니다. 그러면 상한이 높아져 이후의 분기를 더 많이 잘라 낼 수 있습니다.
제약 전파
선택을 한 뒤에는 이후 단계에서 할 수 있는 일을 좁힙니다. 불가능한 선택지를 미리 제거하는 것이 제약 전파이며, 탐색 트리의 크기를 줄여 줍니다.
대칭 깨기
두 분기가 서로 대칭이라면 하나만 탐색합니다. 대칭 깨기를 사용하면 답을 잃지 않고 작업량을 절반 이하로 줄일 수 있습니다.
겹치는 상태 메모이제이션하기
같은 부분 상태가 다시 나타나면 그 결과를 저장해 둡니다. 메모이제이션을 사용하면 반복되는 하위 트리를 한 번의 빠른 조회로 처리할 수 있습니다.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...늦지 않게 일찍 가지치기하기
가지치기 조건은 재귀 호출 후가 아니라 호출 전에 확인해야 합니다. 조기 가지치기는 가능성이 없는 분기를 확장하는 낭비를 막습니다.
실행 전에 추정하기
최악의 경우의 분기 수를 항상 제약 조건과 비교하여 점검해야 합니다. 너무 많다면 더 강한 가지치기나 새로운 접근법이 필요합니다.
빠른 확인
백트래킹에서 가지치기의 목적은 무엇일까요?
복습: 막다른 분기 잘라 내기
실행 가능성 확인과 상한 확인, 현명한 순서 정하기, 대칭 깨기, 메모이제이션을 사용해 가지치기하는 방법을 배웠습니다. 이를 통해 시간 제한을 넘길 수 있습니다. 🎯
자주 묻는 질문
“시간 제한을 통과하도록 가지치기하기” 강의는 무료인가요?
네 — “시간 제한을 통과하도록 가지치기하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“시간 제한을 통과하도록 가지치기하기”에서 뭘 배우나요?
개선할 수 없는 가지를 제거합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“시간 제한을 통과하도록 가지치기하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 재귀적으로 사고하기: 기본과 재귀 호출
- 모든 부분집합 생성하기
- 순열과 N-Queens 발상
- 시간 제한을 통과하도록 가지치기하기