내일배움캠프 61일차 - 자료구조 & 알고리즘 11주차 : 백트래킹

백트래킹 - "완전 탐색 + 가지치기"

완전 탐색을 하되, "답이 될 수 없는 방향"을 조기에 포기하고 되돌아가는 기법

완전 탐색: 재귀 트리의 모든 잎(leaf)까지 내려간다. - 무조건 끝까지.
백트래킹: 트리의 중간에서 "이 아래는 볼 필요 없다"고 판단하면 가지를 잘라낸다.

× = "답이 될 수 없다" → 이 아래 전체를 건너뛴다는 의미

백트래킹의 핵심 두 요소

1) 유망성 판단 (Promising)
 :"현재 상태에서 더 진행해도 답이 될 가능성이 있는가?"
 - 제약 조건을 검사하는 단계

2) 가지치기 (Pruning)
 :유망하지 않으면 그 가지 전체를 건너뜀
 - 아래로 더 내려가지 않는다.

= 백트래킹이란 가능성, 유망성을 보고 안되면 그 가지를 잘라내는 것이다.

부분합 문제 - 같은 문제, 더 똑똑하게.

문제: 배열 {3,7,1,8,4}에서 합이 11인 부분집합을 찾아라.

완전 탐색 방법: 부분집합 2^5 = 32개를 모두 만든 뒤 각각의 합을 확인 → 11인 것 찾기
백트래킹: 부분집합을 만드는 도중에 "이미 합이 11 초과"라면 → 가지치기

※ 합은 원소(양수)를 추가할 수록 커지기만 하므로 합이 목표를 넘으면 더 깊이 들어갈 필요가 없음

부분합 추적

회색: 탐색한 루트 / 녹색: 정답 루트 / 주황색: 오답 루트 / 희미한 색: 탐색하지 않은 루트

배열 {3,7,1,8,4}의 부분집합은 사진의 모든 구슬의 개수와 같다.
( 완전탐색 시 탐색횟수 2^5 = 32회)

백트래킹을 통해 부분합 11을 만족하는 부분집합을 구하기 위해 위에서부터 가지 아래로 내려가면서 만나는 숫자를 모두 합해서 11을 만족하면 결과에 포함하고, 11을 초과하면 그 아래의 탐색은 중단한다.
( 위 사진에서 백트래킹으로 탐색한 횟수 14 + 8 + 3 = 25회 )

정렬이 가지치기를 효율적으로 만든다

배열을 오름차순으로 정렬해두면 가지치기가 훨씬 빨라진다.

원본: 37184
정렬 후: 13478

정렬 후에는 "현재 합 + 다음 원소 >= 목표"가 되면 그 이후 모든 가지가 가망 없음을 한번에 판단 가능하다.
( 정렬된 백트래킹으로 탐색한 횟수 13 + 6 +3 = 22회(-3) )

N-Queen 문제

문제: N × X 체스판에 N개의 퀸을 서로 공격하지 못하게 배치하라.

8-Queen 완전 탐색 시: 64칸 중 8칸 선택 = C(64,8) = 약 44억번 → 불가능
※ 한 행에 퀸 하나씩만 배치하면 해도 8^8 = 1677만번

4-Queen 백트래킹 과정

다음 행 공격범위 내의 위치는 가지치기.
한 행이 모두 공격범위라면 되돌아가야 한다(Backtrack).

4-Queen 완전 탐색 시: 16칸 중 4칸 선택 = C(16,4) = 1820번
※ 한 행에 퀸 하나씩만 배치하면 4^4 = 256번

4-Queen 백트래킹으로 탐색한 횟수: 15 + 44(X개수) + 2 ≒ 60

 = 약 77% 절감! 그리고 N이 커질수록 절감률은 극적으로 높아진다.

N-Queen 가지치기 효과

N이 커질수록 가지치기 효과가 기하급수적으로 증가한다.

백트래킹의 최선의 경우: 가지치기가 잘 통하는 문제 → 완전 탐색 대비 99% 이상 절감.
최악의 경우: 가지치기 조건이 안 걸림 → 완전 탐색과 비슷한 시간

※ 백트래킹은 시간 복잡도를 보장하기 어렵다.
※ 그럼에도 대부분의 실제 문제에서 가지치기는 매우 효과적이므로 실전에서 자주 쓰인다.

백트래킹의 3단계 패턴

① 선택 → ② 검증 → ③ 재귀 → ④되돌림

완전 탐색 코드에서 ②번(검증)만 추가하면 백트래킹이 된다.

CS 돋보기

CSP(Constraint Satisfaction Problem, 제약 충족 문제)

말 그대로 '조건을 만족하는 답을 찾는 문제' 를 나타낸다.

변수(Variables): 결정해야 할 것들
도메인(Domain): 각 변수가 가질 수 있는 값들
제약(Constraints): 변수들 간의 조건

N-Queen: 변수 = 행 별 퀸 위치 / 도메인 = 1~N열 / 제약 = 같은 열·대각선 금지
스도쿠: 변수 = 빈 칸 / 도메인 = 1~9 / 제약 = 행·열·블록 중복 금지
시간표: 변수 = 각 교시 / 도메인 = 과목 / 제약 = 같은 날 같은 과목 연속 금지 등

게임 AI(알파-베타 가지치기)

체스·바둑 AI의 기초인 Minimax 알고리즘
 : "나는 최선의 수, 상대는 최악의 수"를 재귀적으로 탐색

※ 알파-베타 가지치기(Alpha-Beta Pruning) = 백트래킹의 게임 AI 버전.
※ 딥블루(1997 체스), 알파고(2016 바둑)도 근본적으로는 트리 탐색 + 가지치기의 확장이다.

실전에서는?

게임 개발

 - 체스·바둑·오목 AI: 백트래킹 + 알파-베타 가지치기로 가능성의 폭발을 통제

 - 턴 기반 AI: "내수 → 상대 수 → 내 수" 트리 탐색에서 불리한 가지 잘라내기

 - 퍼즐 생성기: 스도쿠·지뢰찾기의 유효한 퍼즐 자동 생성 - 무효하면 되돌아감

 - 레벨 생성: "이 방에 적 N마리, 막다른 길 없음" 같은 제약을 만족하는 맵 배치

 - NPC 경로 탐색: 적이 다닐 수 없는 길은 미리 가지치기

정규식 매칭도 - 백트래킹
에디터의 찾기, 셸의 grep, 텍스트 검색기 뒤에서 '정규 표현식 매칭 엔진'은 백트래킹을 쓴다.

웹,서버

 - 시간표 자동 생성: 교수·강의실·연속 수업 제한 등 수백 개 제약 만족

 - 회의실 / 직원 근무 스케줄: 가능한 배치 중 제약을 깨지 않는 것만 채택

 - 물류 / 배차 계획: 시간·차량·경로 제약을 동시에 만족

 - 웹 라우팅 매칭: 패턴 매칭 단계에서 백트래킹 사용

※ "조건을 만족하는 배정" 문제는 거의 항상 백트래킹이다.
※ 사람이 수작업으로 하던 "퍼즐 같은 작업"을 자동화 - 백트래킹의 대표 활용 영역.

일반 CS

 - SAT(논리식 충족): 변수 값 배정 + 절 제약 → DPLL 알고리즘(백트래킹 + 가지치기)

 - 그래픽 색칠 문제: 인접 노드는 다른 색 - 한 노드씩 색칠하다 막히면 되돌아감

 - 컴파일러: 정규식 매칭 / 피서의 일부 모드

 - 패스워드 크래킹: 보안 분야에서 무차별 대입의 가지치기 변형

※ 이론적으로 어려운 문제(NP)도 가지치기로 인해 실전에서 풀 수 있는 크기가 된다.

오늘의 핵심

 - 백트래킹 = 완전 탐색 + 가지치기: 모든 경우를 요약하되, "답이 될 수 없는 방향"은 조기에 포기.

 - 유망성 판단(Promising)이 핵심: "현재 상태에서 더 진행해도 답이 가능한가?"

 - 패턴: 선택 → 검증 →재귀 →되돌림. 10주차 순열/조합 코드에 검증 한 줄을 추가하면 백트래킹.

 - 가지치기 효과는 극적: N-Queen에서 N=8이면 99.9% 절감

 - 단, 보장은 없다: 최악의 경우 완전 탐색과 동일. "가지치기가 통하는 문제"에서 위력 발휘.

댓글

댓글 쓰기

이 블로그의 인기 게시물

내일배움캠프 사전캠프 - 사전캠프설 연휴 커피 파밍 이벤트 작품 [ EXTREMITY ]

이미지
  EXTREMITY - 홀로 사지 속으로 어떤 행성에서 벌어지는 일. 이 모든 일에 종지부를 짓기 위해 홀로 전장으로 강하한다. 상호작용 요소  : 자동문, 병사들의 경례, 눈보라 이펙트, 조준과 사격, 끝까지 쫓아오는 적, 사격에 반응해 무너지는 건물과 적들. 시시각각 변화하는 환경. 전체적인 맵구조  : 곳곳에 블루프린트로 이루어진 건물 Foliage들이 배치되어있으며, 이것들은 모두 사격 시의 Line Trace에 반응해 큰 충격을 일으켜 부서지며 날아간다. 부서지는 기능은 엔진 내의 Fracture기능을 사용.  : 공중에는 플레이어가 탑승하고 있는 수송기가 배회하고 있으며, 원형의 Spline을 따라 움직이도록 설계했다.  : 처음에는 높은 고도에 머물고있다는 느낌을 주기 위해 구름을 전체적으로 낮게 깔아주고 안개도 약간 짙게 설정하였다. 그리고 강하 시에는 캐릭터의 높이에 따라 점차 구름높이와 안개의 짙음이 변화하며, 착지 시에는 전체적으로 맑게 변한다. 조준 매커니즘  : 우클릭을 통해 조준을 하면 Spine본을 기준으로 상하로 다른 모션이 출력된다. (레이어 본 블렌딩)  : 상반신은 Anim Montage에 따라 총을 겨누고 쏘는 모션이 재생되고 바라보는 상하각도에 따라 상반신와 팔의 각도 또한 조절된다. (트랜스폼 본)  : 하반신은 StateMachine에 따라 이동입력에 반응하여 발걸음이 달라지며, 2차원 BlendSpace를 사용하여 정면을 바라보면서 전후좌우로 움직일 수 있게 된다. 사격 매커니즘  : 각각 총구 와 카메라 에서 카메라 정면으로 나아가는 두 개의 LineTrace를 사용하였다. 총구 에서 나가는 LineTrace는 보기에는 자연스럽지만 우리는 총구에서 옆비스듬하게 바라보기 때문에 정확도가 떨어진다. 따라서 카메라 에서 발사되는 LineTrace를 하나 더 만들어 둘 중 하나라도 적중하면 명중하도록 설계하였다.  : 눈앞에 있는 적을...
자세한 내용 보기

내일배움캠프 29일차 - 커리어데이 2일차 : 클라이언트 프로그래머로서 포트폴리오, 입사준비팁

이미지
커리어데이 2일차: 포트폴리오, 입사준비 팁 클라이언트 프로그래머 클라이언트란?   - 직접 플레이하며 눈에 보이는 것들을 작업하는 것.    : UI, 애니메이션, 리소스 관리, 전투시스템 등등 준비해야할 것  - 못하면 안됨 : 포트폴리오 , C++  - 잘해야 됨 : 회사마다의 코딩테스트 , CS , 알고리즘  - 잘하면 좋음 : 디자인패턴 , 그래픽스 , 네트워크 , 이거 해야되나? 생각되는 것들 가장 열심히 해야하는 것  - 게임 완성도있게 만들기  - 포트폴리오 눈에 띄게 만들기: 자잘한 것 여럿보다 엄청난 것 하나 만드는 것이 낫다.  - 팀프로젝트 경험 잘 정리하기 포트폴리오의 정답은 없으나 중요한 것은 있다.  : 가독성, 경험, 트러블 슈팅   - 면접관 입장에서 생각 을 해봐야 한다. (접근성이 있는 사이트를 사용) 포트폴리오에서 흥미를 끌 수록 깃허브, 노션 까지 볼 가능성이 높다.   - 포트폴리오 영상은 컴팩트하게, 1~3분 사이로 설명 (면접관은 시간이 없음)    : 모범적 영상:  https://youtu.be/RUsRpTy4tJc?si=TWh1HH4eXrpnZadA    : 시각적으로 흥미를 끌도록 유도   : 완벽하지 않아도 되나 끝까지 해내는 것 자체가 실력이 된다. 모범 포트폴리오 예시  - 면접관이 필요하면 언제든 들어갈 수 있는 링크 일반적인 포트폴리오 링크를 배치한 포트폴리오 (합격예시1) - 느낌이 좋은 레이아웃 배치  : 자신이 제작한 포트폴리오 프로젝트 는 많고 배치를 해야할때, 배치하는 방법이 중요하다. 같은 명품 브랜드 지만, 배치에 따라 느낌이 달라진다. 자신의 프로젝트들을 스팀 상점페이지에 빗대 어 목차에 추가 한 포트폴리오 (합격예시2) 포트폴리오 초반에 프로필을 넣어서 다시 한번 자신의 경력을 어필 하자. - 코드...
자세한 내용 보기