알고리즘을 풀기 전

1. 문제풀이를 위한 의식의 흐름

문제조건: N 범위(데이터의 개수) 200,000, 시간제한은 1초

• 시간복잡도 O(NlogN)으로 풀어야겠다,,
• 이러한 복잡도를 만족하는 하나의 아이디어(그리디 알고리즘)가 있을까?
• 그래프 형태로 보자,, DFS/BFS로 완전 탐색(모든 경우의 수 고려)하면 어떨까?
• 경우의 수가 너무 많다 => 다이나믹 프로그래밍으로 접근

컴퓨터는 대략 1초에 50,000,000번 정도의 연산을 처리할 수 있다고 한다.

2. 알고리즘 성능 평가

복잡도란?

알고리즘의 성능을 나타내는 척도

• 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

=> 동일한 기능을 수행하는 성능의 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

3. 복잡도를 어떻게 평가할 수 있는가?

빅오 표기법

가장 빠르게 증가하는 항만을 고려하는 표기법
=> 함수의 상한만을 나타냄
ex) 연산 횟수가 3N³ + 5N² + 1,000,000인 알고리즘
=> 빅오 표기법에서는 가장 큰 항만 나타내므로 O(N³)으로 표현됨

n = 1,000
n³ = 1,000,000,000
n² = 1,000,000
=> 가장 큰 항을 제외한 나머지는 별게 아니다,,로 해석,,

복잡도 계산해보기

• N개의 데이터의 합을 계산하는 프로그램 예제

let arr = [3, 5, 2, 6, 4]; // 5개의 데이터(N = 5)
let sum = 0;
for (let i = 0; i < arr.length; i++) {
	sum += arr[i];
}
console.log(sum);

=> 더하기 연산의 횟수는 데이터의 개수 N과 비례함
=> 시간 복잡도: O(N)

• 2중 반복문을 사용하는 프로그램 예제

let arr = [1, 2, 3, 4, 5]; // 5개의 데이터(N = 5)
for (let i = 0; i < arr.length; i++) {
	for (let j = 0; j < arr.lenth; j++) {
    	let temp = arr[i] * arr[j];
        console.log(temp);
    }
}

=> 시간 복잡도: O(N²)
=> 보통 이중 반복문은 O(N²)이지만 아닌 경우가 있다.
(소스코드가 내부적으로 다른 함수를 호출하고 있다면 그 함수의 시간 복잡도도 고려해야 함)

4. 알고리즘 설계 tip

일반적으로 연산횟수가 5억을 넘어가는 경우, C언어 기준으로 1 ~ 3초 가량의 시간이 소요된다.
N의 개수를 확인 후에 시간 복잡도를 계산해서 알고리즘을 설계해야한다.
코딩테스트 문제에서 시간제한은 보통 1 ~ 5초 정도이다.(명시되어 있지 않은 경우 참고)

• N의 범위가 500인 경우: 시간복잡도(O(N³)인 알고리즘 설계
• N의 범위가 2,000인 경우: 시간복잡도(O(N²)인 알고리즘 설계
• N의 범위가 100,000인 경우: 시간복잡도(O(NlogN)인 알고리즘 설계
• N의 범위가 10,000,000인 경우: 시간복잡도(O(N)인 알고리즘 설계