알고리즘이란?
유한한 단계를 통해 문제를 해결하기 위한 절차나 방법입니다.
시작과 끝 반드시 존재해야 합니다!
표현 방법 크게 2가지가 있습니다.
슈더코드 ( pseudo code )
대부분의 알고리즘에서 선호하는 표현방법으로 문법이 따로 존재하는 것은 아닙니다.
순서도
그림을 이용하여 구현하고자 하는 알고리즘을 표현할 수 있습니다.
좋은 알고리즘 기준
크게 정확성, 작업량, 최적성★ 3가지가 있습니다.
시간 복잡도 (성능 기준)
빅-오 (O) 표기법 ☆
일반적으로 사용합니다.
과정
- 연산의 수 계산합니다.
- 계수와 상수를 제거합니다.
- 최고차항만 남깁니다.
참고 : O(logn)에서 밑은 숫자 2를 의미합니다.
복잡도 순 정렬
O(1) O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
세타 표기법
논문에서 주로 사용합니다.
오메가 표기법
주요 해결 방법
완전 검색 → 모든 경우 탐색
- 그리디
- 알고리즘분할
- 정보다이나믹 프로그래밍 (동적 프로그래밍)