코테 준비를 위한 시간복잡도

*참고소스는 최하단 참고 바랍니다.

 

 

1. 시간복잡도란?

---

계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, Pan Bubilek이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. (위키백과)

 

말이 어렵지만, 결국은 시간복잡도는 로직 수행시간과 비례하니

시간복잡도 수치가 작을수록 효율적인 알고리즘이다! 라는 의미입니다.

 

일반적으로 코딩테스트에서 시간복잡도와 관련 있는 건, 

• 주어진 문제를 해결하기 위한 연산횟수이고, 이때 수행시간은 1초 동안 1억번의 연산 기준을 적용합니다.

 

2. 시간복잡도 유형

---

세가지 유형이 있습니다. Big-O(빅-오) , Big-Ω(빅-오메가) ,Big-θ(빅-세타)

예를 들어 크기가 8인 배열이 있다고 가정해봅시다. 해당 인덱스마다 1~8까지의 값이 할당되어 있고요.

이때 다른 사람이 고른 임의의 숫자를 내가 뽑을 확률은 어떻게 될까요?

운이 좋으면 한번만에 찾을 수 있고, 운이 나쁘면 가장 마지막 시도에 찾을 수 있겠죠?

 

• Big-Ω(빅-오메가) : 최선 (1번만에 바로 찾는 경우 = 1)
• Big-θ(빅-세타) : 보통 (평균 4~5회 = N/2)
• Big-O(빅-오) : 최악 (마지막 = N) ★

 

코테에서는 통상 최악을 염두하여 문제를 해결해야 합니다. 다른 말로 표현하면 WoW(Worst of Worst)까지 모두 커버해야 한다. WoW를 테스트 통과한다면 해당 알고리즘으로 개발한 서비스 혹은 프로덕트를 배포해도 되겠죠?

 

 

3. 문제 기준으로 시간복잡도 체크포인트!

---

코테 문제를 보고 시간복잡도를 고려할땐,

• 데이터의 개수(또는 크기)
  ㄴ 예를 들어, 1 <= N <= 1,000,000 와 같은 데이터의 범위로 표시가 되고요.
• 시간제한 : 2초 (예시)

위의 N의 범위는 적절해서 일반 코딩으로 커버 가능한데, 문제는 데이터의 크기가 더 늘어나는 경우입니다.

스케일이 커지면 그에따른 알맞은 알고리즘을 적용하여 문제를 풀어야 합니다.

 

 

연산 횟수 계산 방법

• 연산 횟수 : 알고리즘 시간 복잡도 X 데이터의 크기

 

알고리즘 적합성 평가 (데이터 크기 MAX값 기준)

• 버블 정렬 : O(n^2) 
  ㄴ 데이터의 크기가 1,000,000일 경우, (1,000,000)^2 >>>> 2억 (제한시간2초)
  ㄴ 제한시간의 연산횟수를 초과하므로 부적합한 알고리즘
  
  
• 병합 정렬 :  O(nlog(n))
  ㄴ 데이터의 크기가 1,000,000일 경우, (1,000,000)^2 >>>> 2억 (제한시간2초)
  ㄴ 제한시간의 연산횟수를 초과하므로 부적합한 알고리즘

 

4. 시간 복잡도를 바탕으로 코드 로직 개선 시 체크포인트!

---

 

시간 복잡도 도출 기준

• 상수는 시간 복잡도 계산에서 제외한다
• 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다

 

예를 들면

CASE1. 일반 for문 하나

연산횟수 N(for 1회) VS. 연산횟수 3N(for 3회, 중첩X)의 경우, 시간복잡도는 O(n)

 

CASE2. 중첩된 이중 for문

연산횟수 10N VS. 연산횟수 N^2 의 경우, 시간복잡도는 O(n^2) 

ㄴ 시간복잡도가 올라감으로 피해야겠죠?

 

 

5. 결론

---

 

1. 적합한 알고리즘을 선택하고

2. 비효율적인 로직을 찾아서 효율적으로 바꾼다!
ㄴ 실제 코딩 테스트에서 시간 초과가 발생했을때 로직이 효율적인지 빠르게 검토해야합니다.

 

---

[출처]

 

• https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
• https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94/dashboard
• https://velog.io/@party3205/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://velog.io/@kirby0418/Do-it-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-C-1%EC%A3%BC%EC%B0%A8-%EC%A0%95%EB%A6%AC