알고리즘 효율 분석 - 빅오 표기법

문제 분석 연습하기

1. 문제를 쪼개서 분석하기

• 한번에 생각해야 하는 양 줄이기

2. 제약 사항을 파악하고 테스트 케이스 추가하기

• 알고리즘 고민 시 활용
• 구현 단계에서 예외 체크

3. 입력값 분석하기

• 입력값 크기에 따라 사용 가능한 알고리즘이 걸러짐

4. 핵심 키워드 파악하기

• 적용할 알고리즘에 대한 힌트

5. 데이터 흐름이나 구성 파악하기

• 적용할 자료구조, 알고리즘, 구현 방향 결정 시 고려
• 힙 자료구조 - 데이터 삽입, 삭제가 빈번할 때 고려
• 최적화된 방법을 모를 때 - 전체 탐색 방식으로 모든 케이스 확인
• 효율과 더불어 접근성도 생각하기 - 키값을 무엇으로 할지 등

키워드에 따른 알고리즘 선택

알고리즘	키워드	상황
스택	- 쌍이 맞는지 - 최근	- 무언가를 저장하고 반대로 처리해야 할 때 - 데이터의 조합이 균형을 이뤄야 할 때 - 알고리즘이 재귀 특성을 가질 때 - 최근 상태 추적
큐	- 순서대로      - ~대로 동작하는 경우 - 스케줄링      - 최소 시간	- 특정 조건에 따라 시뮬레이션할 때 - 시작 지점부터 목표지점까지 최단 거리
깊이 우선 탐색	- 모든 경로	- 메모리 사용량이 제한적일 때의 탐색 - 백트래킹 문제를 풀 때
너비 우선 탐색	- 최적             - 레벨 순회  - 최소 단계      - 네트워크 전파	- 시작 지점부터 최단 경로나 최소 횟수를 찾아야 할 때
백트래킹	- 조합             - 순열 - 부분 집합	- 조합 및 순열 문제 - 특정 조검을 만족하는 부분 집합
최단 경로	- 최단 경로      - 최소 시간 - 최소 비용      - 트래픽 - 음의 순환      - 단일 출발점 경로	- 다익스트라: 특정 지점에서 나머지 지점까지 가는 최단 경로 - 벨만-포드: 음의 순환 탐지, 음의 가중치를 가진 그래프에서 최단 경로

알고리즘의 효율 분석

시간 복잡도(time complexity)

시간 복잡도란 알고리즘의 성능을 타나내는 지표로 입력 크기(알고리즘이 처리해야 할 데이터)에 대한 연산 횟수의 상한을 의미하며, 낮을수록 좋습니다.

빅오 표기법(big-O notation)

빅오 표기법이란 충분히 큰 입력값 N에 따른 연산에 대해 점근적으로 표기하는 방법을 말합니다. 연산 횟수를 함수로 나타냈을 때, 계수를 제외한 최고차항을 O(최고차항) 으로 표현합니다.

활용하기

문제를 분석한 후 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력이 가능한지를 파악할 때 활용할 수 있습니다. 보통 컴퓨터의 연산 속도는 초당 최대 1억 회이므로, 적절한 연산 횟수를 1,000~3,000만 회로 생각하고 이에 적합한지를 파악합니다.

시간복잡도에 따른 최대 연산횟수는 다음과 같습니다.

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3,000~5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억

---

참고자료

• 코딩테스트 합격자 되기 자바스크립트 편, 프로그래머스O()