[코드트리 조별과제] - 펜트하우스

https://www.codetree.ai/missions/6/problems/penthouse?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

문제

펜트하우스에 코드들이 입주를 합니다. 모두가 높은 층에 입주하고 싶겠지만, 자리는 한정되어 있기 때문에 다음과 같은 규칙으로 배정하기로 했습니다.

두 코드의 시간복잡도를 각각 f(n),g(n)이라고 할 때,

• f(n)=Θ(g(n))이 성립하면, 두 코드는 같은 층에 배정됩니다.
• 만약 f(n)=O(g(n))이지만 g(n)=O(f(n))이라면, f(n)은 g(n)보다 낮은 층에 배정됩니다.

 

n^3　 　　　 10n^3
nlogn              logn
n^2logn 　  　2^n+2021
1/2​n^5 　　    2^n

 

다음과 같은 8개의 코드의 시간복잡도가 있다고 합시다. 이 경우 최상층으로 가는 코드의 수와 그 아래층으로 가는 코드의 수를 합치면 어떻게 될까요?

 

 

풀이과정

- 같은 차수의 시간 복잡도n^3 == 10n^32^n+2021 == 2^n

 

- 차수 비교

n^3 = Ω (nlogn)

n^3 = Ω (logn)

n^3 = Ω (n^2logn)

n^3 = Ω (1/2​n^5) 

n^3 = O (2^n)

n^3 = O (2^n+2021)

 

최상층 - 2^n+2021 == 2^n

5층 - 1/2​n^5

4층 - n^3 == 10n^3

3층 - n^2logn

2층 - nlogn

최하층 - logn

 

답

최상층의 코드수는 2개, 그 아래층의 코드는 1개이므로 답은 3