Greedy AlgorithmGreedy(탐욕법)는 매 순간마다 가장 좋아 보이는 선택(국지적 최적해)를 하여,그 선택들의 결과가 최종적으로 전체 문제의 해(전역 최적해)가 되도록 기대하는 알고리즘 기법이다. 즉, 한 단계에서 내린 최선의 선택이 전체 문제에서도 최적해로 이어질 수 있을 때 사용하는 방법이다. Greedy가 필요한 이유단순 완전 탐색의 한계모든 경우의 수를 다 따지면 시간 복잡도가 폭발적으로 커짐. 빠른 계산매번 가장 좋아 보이는 선택만 하므로 O(N log N)이나 O(N) 안에 해결되는 경우가 많음. Greedy의 두 가지 핵심 조건탐욕적 선택 속성 (Greedy Choice Property)매 순간의 최적 선택이 전체 최적해로 이어져야 함. 최적 부분 구조 (Optimal Subs..

Dynamic ProgramingDynamic Programing(DP)는 복잡한 문제를 작은 부분 문제(sub problem)로 나누고,그 결과를 저장하여 재활용하는 방식으로 문제를 푸는 알고리즘 기법이다. 즉, DP는 큰 문제를 작은 부분 문제로 쪼개고, 그 답을 저장해가면서 큰 문제를 푸는 방법이다. DP가 필요한 이유단순 재귀의 한계 (중복 계산)같은 부분 문제를 여러 번 푸는 비효율 → 예: 피보나치 수열에서 fib(3)이 중복 호출 됨. 시간 복잡도 개선DP를 쓰면 한 번 계산한 결과를 저장해서 O(N) 수준으로 줄일 수 있음. DP의 두 가지 핵심 조건중복되는 부분 문제 (Overlapping Subproblems)큰 문제를 해결하는 과정에서 동일한 작은 문제가 반복적으로 등장해야 함. 최..

Graph Traversal (그래프 탐색)DFS를 들어가기 전, 먼저 그래프 탐색(Graph Traversal)에 대해 알아보자.그래프 탐색이란, 하나의 정점에서 시작하여 도달 가능한 모든 정점을 한 번씩 방문하는 과정을 의미한다.그래프가 비연결(disconnected)인 경우 전체 정점을 모두 방문하려면, 방문되지 않은 정점에서 탐색을 재시작하는 멀티-소스 루프가 필요하다.이 과정은 두 정점이 연결되어 있는지 여부를 확인하거나, 특정 경로를 찾을 때 필수적이다. 예를 들어, 특정 도시에서 다른 도시로 이동할 수 있는지,혹은 전자 회로에서 두 단자가 서로 연결되어 있는지를 확인하는 문제를 그래프 탐색으로 해결할 수 있다. 그래프 탐색에는 크게 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)이 존재한..

Graph Traversal (그래프 탐색)BFS를 들어가기 전, 먼저 그래프 탐색(Graph Traversal)에 대해 알아보자.그래프 탐색이란, 하나의 정점에서 시작하여 도달 가능한 모든 정점을 한 번씩 방문하는 과정을 의미한다.그래프가 비연결(disconnected)인 경우 전체 정점을 모두 방문하려면, 방문되지 않은 정점에서 탐색을 재시작하는 멀티-소스 루프가 필요하다.이 과정은 두 정점이 연결되어 있는지 여부를 확인하거나, 특정 경로를 찾을 때 필수적이다. 예를 들어, 특정 도시에서 다른 도시로 이동할 수 있는지,혹은 전자 회로에서 두 단자가 서로 연결되어 있는지를 확인하는 문제를 그래프 탐색으로 해결할 수 있다. 그래프 탐색에는 크게 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)이 존재한..