✅ [31일차] 알고리즘 기초 – 재귀, 분할 정복, 탐욕, 동적 계획법, 백트래킹

📘 1. 알고리즘이란?

• 문제 해결을 위한 명확한 절차나 방법
• 알고리즘의 성능은 주로 시간 복잡도와 공간 복잡도로 평가

---

📘 2. 재귀 호출(Recursion)

• 함수가 자기 자신을 다시 호출하는 방식

예시:

python

복사편집

def factorial(n): if n == 1: return 1 return n * factorial(n - 1)

• 반복 구조보다 코드가 간단하지만 스택 오버플로우 주의

📌 기출 포인트:

• 재귀는 종료 조건이 필수
• 재귀 호출 → 스택 구조와 관련

---

📘 3. 분할 정복(Divide and Conquer)

• 문제를 작은 문제로 나눈 후, 각각을 해결한 뒤 합치는 방식

대표 알고리즘설명

퀵 정렬	피벗을 기준으로 분할
병합 정렬	반으로 나누고 병합
이진 탐색	중간값을 기준으로 절반만 탐색

 

📌 핵심 개념: 나누고 해결한 후 합친다

---

📘 4. 탐욕 알고리즘(Greedy Algorithm)

• 매 순간 최적(최선)의 선택을 하는 방식
• 전체 최적해를 보장하지는 않음

대표 예시설명

동전 교환 문제	가장 큰 단위부터 선택
활동 선택 문제	가장 먼저 끝나는 활동부터 선택

 

📌 기출 포인트:

• 탐욕 알고리즘은 항상 최적해를 보장 X
• 효율적이나 조건 확인 필요

---

📘 5. 동적 계획법(Dynamic Programming, DP)

• 작은 문제의 해를 저장하고, 이를 재활용해서 큰 문제 해결
• 중복 계산을 줄여 속도 향상

예시설명

피보나치 수열	앞의 두 값을 저장 후 재사용
최단 경로	벨만-포드 알고리즘 등

 

📌 기출 포인트:

• 탐색 구조 + 메모이제이션(Memoization) 활용
• 탑다운/바텀업 방식 구분

---

📘 6. 백트래킹(Backtracking)

• **가능성 없는 해는 미리 제거(가지치기)**하면서 정답을 찾는 방법
• DFS(깊이 우선 탐색) 기반

대표 문제설명

N-Queen 문제	퀸이 서로 공격하지 않도록 배치
순열 생성	조건 만족하는 경우만 탐색

 

📌 기출 포인트:

• 해를 탐색하며 조건이 안 맞으면 돌아감
• 깊이 우선 탐색(DFS)과 매우 관련 있음

---

📘 7. 기출 포인트 요약

알고리즘특징

재귀	자기 자신 호출, 스택 기반
분할 정복	나누고 합치기, 병합 정렬
탐욕	국소 최적 선택, 항상 정답 X
DP	부분 문제 결과 저장, 중복 계산 줄임
백트래킹	조건 불만족 시 중단, DFS 기반

 

---

📝 기출 예시 문제

다음 중 동적 계획법(DP)의 특징으로 옳은 것은?

① 항상 최적해를 구하지 못한다
② 중복 계산을 하지 않도록 결과를 저장한다
③ 각 단계에서 최선의 선택을 한다
④ 문제를 재귀적으로 나누지 않는다

✅ 정답: ②