2025 09 30 스파르타 코딩클럽 22일차

1. 알고리즘 성능 분석

• 알고리즘 성능 분석이란?
  문제를 해결하는 여러 알고리즘 중에서, 주어진 시간과 자원 제약 안에서 가장 효율적인 방법을 찾기 위해 성능(시간, 메모리 등)을 평가하는 과정.

• 시간 복잡도 (Time Complexity)

  • 입력 크기 n에 따른 알고리즘의 실행 시간을 분석
  • Big-O 표기법을 사용: O(1), O(log n), O(n), O(n log n), O(n^2) 등

• 공간 복잡도 (Space Complexity)

  • 알고리즘 실행 시 필요한 메모리 사용량 분석
  • 예: 재귀 호출의 스택 메모리, 추가 배열/자료구조 사용량 등

---

2. 알고리즘 문제해결 5단계

1단계: 문제 이해 및 요구사항 분석

• 문제를 정확히 읽고 해석하기
• 입력과 출력 형식, 제약 조건 정리
• 예시 입력/출력으로 문제 의도 파악

2단계: 접근 방법 구상하기

• 유사 문제/패턴 떠올리기
• 사용할 수 있는 알고리즘 유형 고려하기 (완전 탐색, DP, Greedy 등)
• 해결 아이디어의 시간·공간 효율성 예측

3단계: 세부 설계 및 검토

• 알고리즘 절차를 단계별로 구체화
• 발생할 수 있는 예외 상황 점검
• 극단적인 입력값(엣지 케이스) 고려
• 시간/공간 복잡도 분석 필수

4단계: 코드 작성 및 구현

• 설계한 알고리즘을 실제 코드로 변환
• 가독성 있는 변수명, 함수명 사용
• 구현 과정에서 알고리즘의 효율성 점검

5단계: 테스트와 디버깅

• 다양한 테스트 케이스 실행 (일반, 극단, 예외 상황)
• 오류 발생 시 디버깅
• 실행 시간이 길 경우 알고리즘/자료구조 최적화
  • 중복 연산 제거 (메모이제이션)
  • 불필요한 탐색 제거 (가지치기)
  • 적절한 자료구조 선택 (예: 해시, 우선순위 큐)

---

3. 알고리즘 유형

• 구현 (Implementation) & 시뮬레이션 (Simulation)

  • 단순히 문제의 요구사항을 그대로 코드로 옮겨 구현하는 방식

• 완전 탐색 (Brute Force)

  • 가능한 모든 경우를 탐색 (효율성은 낮지만 정답 보장)

• 그리디 (Greedy) 알고리즘

  • 매 순간 최적이라고 생각되는 선택을 반복 → 전역 최적 보장 여부는 문제 특성에 따라 다름

• 백트래킹 (Backtracking)

  • 모든 경우를 탐색하되, 불가능한 경우는 조기에 탐색 중단 (가지치기)

• 분할 정복 (Divide and Conquer)

  • 문제를 작은 부분 문제로 나눠 해결 후, 결과를 합치는 방식 (예: 병합 정렬, 퀵 정렬)

• 동적 계획법 (Dynamic Programming, DP)

  • 부분 문제의 해를 저장하여 중복 계산을 줄임 (메모이제이션, 점화식 기반)

---

4. 좋은 알고리즘을 선택하는 기준

1. 입력 크기 (n): n이 작으면 단순 탐색도 가능, 크면 최적화 필요
2. 제약 조건: 시간 제한, 메모리 제한 고려
3. 정확성 vs 효율성: 빠르지만 근사값만 주는 알고리즘도 선택 가능
4. 문제 유형: 최단 경로 → 다익스트라, 최적화 → DP/Greedy, 탐색 → DFS/BFS