변수의 기록

백트래킹(Backtracking) vs 시뮬레이션(Simulation) 문제 정리1. 백트래킹 (Backtracking)✅ 개념백트래킹은 해를 찾기 위해 가능한 모든 경우의 수를 탐색하되,불필요한 경로(조건 위반)가 감지되면 탐색을 중단하고 이전 단계로 돌아가는 방식이다.즉, "완전 탐색 + 가지치기" 전략.✅ 언제 사용하는가?모든 경우의 수를 탐색해야 하는 문제조합, 순열, 부분 집합, 경로 찾기 등의 문제에서 유용for문으로는 해결이 불가능한, 깊이가 달라지는 문제 구조✅ 전형적인 예시 문제N과 M (순열, 조합)모든 연산자 끼워넣기퀸 문제(N-Queen)최소 비용 경로 탐색스도쿠✅ 시간 복잡도 기준 경우의 수 조건 시간 복잡도현실적으로 가능한 N중복 허용N ≤ 7~8 수준중복 불허N ≤ 10 수준..

DFS vs BFS (그래프 탐색 기법 정리)1. 그래프 탐색이란?그래프 탐색(Graph Traversal)이란, 어떤 노드(정점, Vertex)에서 시작해서 연결된 모든 노드를 빠짐없이 방문하는 과정이다.그래프는 다음 두 요소로 구성된다:Vertex (정점): 탐색의 대상이 되는 지점 (예: 사람, 도시, 방 등)Edge (간선): 정점 간의 연결 (예: 친구 관계, 도로, 벽 없는 통로 등)그래프는 연결되어 있는 방식에 따라 다양한 문제(미로 탐색, 단지 번호 붙이기, 친구 관계 등)에 응용될 수 있다.2. 탐색 기법 종류✅ DFS (Depth-First Search, 깊이 우선 탐색)한 방향으로 쭉 들어가며 끝까지 탐색한 뒤, 다시 돌아와서 다른 방향 탐색자식의 자식까지 내려감, 더 이상 갈 곳이 ..

Dynamic Programming (DP) 개념 정리1. Optimization Problem이란?Optimization Problem은 가능한 해답 중에서 **가장 최적의 해(solution)**를 찾는 문제입니다.“최적”이란 일반적으로 최대값(Maximum) 또는 **최소값(Minimum)**을 의미합니다.예시:가장 적은 비용으로 목적지에 도달하는 경로최대 수익을 내는 주식 거래 시점최소 동전 개수로 거스름돈 만들기✅ 하나의 문제에 대해 하나 이상의 최적 해가 존재할 수도 있음.2. Dynamic Programming(DP)이란?Dynamic Programming은 최적화 문제를 효율적으로 해결하는 알고리즘 설계 기법입니다.핵심 아이디어큰 문제를 작은 하위 문제들로 나누고작은 문제들의 정답을 이용해..

Divide and Conquer (분할 정복) 전략개념 정리**Divide and Conquer(분할 정복)**는 컴퓨터 과학에서 널리 사용되는 문제 해결 전략 중 하나로, 다음 세 단계로 이루어져 있습니다:Divide (분할)주어진 문제를 **더 작고 유사한 하위 문제들(sub-problems)**로 나눈다.각 서브 문제는 원래 문제와 구조적으로 유사하며, 전체 문제를 분해하여 해결 가능하도록 만든다.Conquer (정복)나눠진 서브 문제들을 재귀적으로 해결한다.더 이상 나눌 수 없을 정도로 작은 문제(기저 조건 base case)는 직접 해결한다.Combine (통합)해결된 서브 문제들의 결과를 합쳐서 전체 문제의 해답을 구성한다.주요 특징재귀 호출을 기반으로 하며, 하향식(top-down) 방식의..