알고리즘

DP는 큰 문제를 작은 문제로 나누고, 그 결과를 저장하여 재활용하는 방식으로 문제를 해결하는 기법이다. 핵심 요약같은 계산을 반복하지 않음이전 단계의 최적 결과를 이용중복 계산을 줄여 효율적으로 계산문제를 쪼갤 수 있는지 확인큰 문제를 작은 하위 문제로 분리 가능해

백트래킹(Backtracking)은 모든 가능한 경우의 수를 탐색하면서, 불필요한 경로를 조기에 차단하는 탐색 알고리즘이다.쉽게 말해 “조건에 맞지 않으면 바로 돌아가는(Backtrack)” 방식의 완전탐색이다.완전탐색(Brute-force)은 가능한 모든 경우를 시도

시뮬레이션 문제는 주어진 규칙에 따라 상태를 직접 변화시키며 최종 결과를 도출하는 문제 유형이다.정해진 공식이나 점화식으로 답을 구하는 DP, 탐색, 수학적 문제와 달리“규칙을 그대로 구현해야 하는 문제”가 대부분이다.즉, 해답의 핵심은 알고리즘보다는 과정의 재현이다.

벨만-포드(Bellman-Ford)는 음수 가중치가 포함된 그래프에서 최단 경로를 찾는 알고리즘이다.최단 경로는 최대 V-1개의 간선을 포함한다.(사이클이 없는 한, 더 이상 추가 간선을 거치지 않아도 모든 노드에 도달 가능)V번째 반복에서도 거리가 갱신된다면, 음수