변수의 기록

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

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) 방식의..

1. 시간 복잡도란?**시간 복잡도(Time Complexity)**는 어떤 함수나 알고리즘이 **입력값의 크기(n)**에 따라 얼마나 많은 연산을 수행하는지를 표현한 것. 다시 말해, 알고리즘이 실행되기까지 필요한 연산 스텝의 수를 의미한다.이때 중요한 건, 정확한 시간(초)이 아니라 입력의 크기 n에 따라 시간이 어떻게 증가하는지를 분석하는 것.2. 점근적 분석이란?시간 복잡도를 분석할 때는 보통 입력값 n이 **매우 커지는 상황(무한대에 가까워질 때)**을 상정한다. 이를 점근적(Asymptotic) 분석이라 하며, 다음과 같은 특징이 있다:덜 중요한 항은 무시한다예: f(n) = 2n² + 3n + 1 → 점근적으로 n²만 남는다.계수도 무시한다예: f(n) = 100n² → O(n²)로 표현한다..