1. 어떤 알고리즘으로 풀어야 할까?

# 코딩 테스트와 관련된 학습을 시작하기 전에 반드시 알아야 할 2가지 스킬

- 시간 복잡도

- 디버깅

 

시간 복잡도 : 알고리즘에서는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.

일반적으로 수행시간은 1억 번의 연산 = 1초의 시간으로 간주하여 예측함.

ex) 문제에서 시간제한이 2초라고 되어 있다면 2억 번의 연산 안에 답이 나와야 함.

 

 

[시간 복잡도 유형]

• 빅-오메가 : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타 : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오 : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

---

 

시간 복잡도 예제 코드 : 0~99 사이의 무작윗값을 찾아 출력하는 코드

int findNumber = (int)(Math.random() * 100);
for(int i=0; i < 100; i++){
	if(i == findNumber){
		System.out.println(i);
		break;
	}
}

findNumber 변수에 랜덤 값이 0이 나온다면 for문에서 i는 0부터 시작하기 때문에 한 번만에 찾아진 경우 -> 빅-오메가인 경우

findNumber 변수에 특정 랜덤 값이 나와서 특정 랜덤 값 만큼 for문을 돌린 후 i == findNumber가 성립된 경우 -> 빅-세타

findNumber 변수에 99가 나와서 for문을 100번 돌려야 하는 경우 -> 빅-오 (가장 시간이 오래 걸림)

 

 

* 실제로 코딩테스트 할 때는 빅-오 표기법으로 최악의 경우를 염두해놓아야 한다.

 : 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하기 때문.

 

---

 

[문제연습 000 - 수 정렬하기]

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오. (시간제한 2초)

 

입력

1번째 줄에 수의 개수 N(1 <= N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다.

이 수는 절댓값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

 

-> 시간제한이 2초이므로 2억 번 이하의 연산 횟수로 문제를 해결해야 한다.

따라서 문제에서 주어진 시간제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지 판단할 수 있다.

 

연산 횟수 계산 방법 연산 횟수 = 알고리즘 시간 복잡도 x 데이터의 크기

버블 정렬의 시간 복잡도 = (n)²-> (1,000,000)² = 1,000,000,000,000 > 200,000,000 

병합 정렬의 시간 복잡도 = nlog(n) -> 1,000,000 log(1,000,000) = 20,000,000 < 200,000,000 

 

따라서, 버블 정렬은 약 10억 번의 연산 횟수가 필요하므로 2억 번 안에 원하는 답을 구해야 하는 이 문제를 풀기에는 

적합한 알고리즘이 아니다.(시간 초과) 병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 적합한 알고리즘이라 할 수 있다.

 

---

 

*시간 복잡도를 기준으로 내 코드가 잘 짜여있는가?

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.

: for문을 N번만큼 한 번 돌리는 코드가 있고 for문을 3번 돌리는 코드가 있다고 가정한다면

연산 횟수가 N인 경우와 3N인 경우로 나눌 수 있다.

이 경우 연산 횟수는 3배 차이가 나지만 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다.

 

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

: 코드에 이중 for문이 있고 일반 for문이 10개 더 있다 하더라도 가장 많이 중첩된 이중 for문으로 시간 복잡도가 계산된다.

 

내가 아는 알고리즘이야 근데 시간 복잡도에 맞는 알고리즘을 짜서 답도 나왔는데 

시간 초과가 발생했다 그럴 경우 내가 짠 로직이 효율적으로 짜여있는지 확인해야 함.

 

실제 코딩 테스트에서 시간초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고,

이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제 해결할 수 있다.

 

결론

1. 알맞은 알고리즘 쓰기 

2. 비효율적인 로직 찾아서 효율적으로 바꾸기 (가장 시간 복잡도를 잡아먹는 부분)

-> 대부분의 사람들이 알고리즘이 잘못되었다고 생각하는데 로직을 잘 살펴봐야 함.

 

 

 

https://youtu.be/XncTU-4i1KI