백트래킹은 일종의 DFS 기반 알고리즘으로, 문제 해결 과정에서 해를 찾기 위해 후보군을 검사하다가 조건을 만족하지 않으면 이전 단계로 돌아가 다른 후보군을 찾는 기법이다. 주로 조합, 순열, 부분집합 등을 구하는 문제에서 사용된다. 백트래킹은 유용한 문제 해결 기법 중 하나로, 많은 NP-hard 문제에 적용될 수 있다. 백트래킹의 기본 아이디어 상태 공간 트리(State Space Tree): 문제의 해를 트리 구조로 표현한다. 각 노드는 문제의 한 상태를 나타내며, 간선은 상태 간의 전이를 나타낸다. 프로모션(promising): 해당 노드에서 유망한지 검사한다. 즉, 현재 상태에서 해를 찾을 가능성이 있는지를 확인한다. 가지치기(cutting off): 유망하지 않은 노드의 서브트리는 검사하지 않..
설명 모노톤 스택(Monotonic Stack)은 주어진 배열에서 각 원소에 대해 다음에 올 원소를 찾거나, 또는 이전에 올 원소를 찾는 데에 사용되는 자료 구조이다. 주로 "더 큰 원소를 찾아라" 또는 "더 작은 원소를 찾아라"와 같은 상황에서 유용하게 활용된다. 모노톤 스택의 두 가지 유형: 단조 증가 스택 (Increasing Monotonic Stack): 스택에 원소를 추가할 때, 스택의 맨 위에 있는 원소보다 큰 값을 가진 원소만 추가한다. 이 스택은 "더 큰 원소를 찾아라"와 같은 상황에서 사용된다. 단조 감소 스택 (Decreasing Monotonic Stack): 스택에 원소를 추가할 때, 스택의 맨 위에 있는 원소보다 작은 값을 가진 원소만 추가한다. 이 스택은 "더 작은 원소를 찾아..