알고리즘 개념 정리

알고리즘

• 문제 해결을 위한 일련의 절차나 방법을 공식화한 것.
• 중요한 것은 원리 이해보다 응용 능력과 문제를 푸는 알고리즘 찾기.
• 가장 효과적인 공부 방법: 문제 풀이.
• 중요도: 수행 시간 > 메모리 사용량 > 코드 길이.

시간 복잡도 (Big O Notation)

• 입력 크기 N에 따른 실행 시간 예측.
• 1억 연산 ≈ 1초.
• 대표적인 시간 복잡도
  • $O(1)$
  • $O(\log N)$
  • $O(N)$ : 1억
  • $O(N \log N)$ : 5백만
  • $O(N^2)$ : 1만
  • $O(N^3)$ : 500
  • $O(2^N)$ : 20
  • $O(N!)$ : 10
• 계산 시 상수 무시, 변수가 다를 경우 모든 항 고려.

메모리

• 일반적으로 메모리 제한 크게 문제되지 않음.
• 가장 큰 공간 사용자: 배열.
• 배열 공간 사용 = 배열 크기 × 자료형 크기.