[코드트리] 약점 집중 돌파로 정복하는 알고리즘 복잡도: '점근 표기법' 완벽 정리

안녕하세요! 이번에 코드트리 청약통장 5회차 미션: 차근차근 약점 집중 돌파를 진행하며 평소에 개념적으로는 알고 있었지만 가끔 헷갈리던 알고리즘의 기초, '점근 표기법' 단원을 완벽하게 정복하고 왔습니다.

 

청약통장 4주차 : 갭체크로 마주한 나의 코테 약점과 남은 3주 목표 설정

 

개발을 하다 보면 시간 복잡도를 계산해야 할 일이 정말 많은데, 이번 기회에 복잡도 서열과 기호들의 의미를 제대로 정리할 수 있었습니다. 학습 경험과 함께 제가 푼 문제들의 풀이 과정까지 공유해 봅니다!

 

코드트리만의 커리큘럼 구조

타 플랫폼(백준, 프로그래머스 등)에서 알고리즘을 공부할 때는 보통 '태그별 문제 모음'을 무작정 풀거나 난이도 순으로 정렬해 풀곤 했습니다. 그러다 보니 기본 개념이 부족한 상태에서 어려운 문제를 만나면 쉽게 지치고, 내가 정확히 어느 부분에서 막히는지 파악하기 어려웠습니다.

 

반면 코드트리는 하나의 대단원 아래에 아주 세부적인 레슨 단위로 쪼개져 있고, 각 레슨은 [기본 문제] ➔ [연습 문제] ➔ [테스트 문제]의 3단계 계단식 구조를 취하고 있습니다.

 

이번에 진행한 Lesson 2. 점근 표기법 역시 이 흐름을 그대로 따라갔는데요. 

• 기본 문제로 핵심 개념의 뼈대를 잡고,
• 연습 문제를 통해 조금씩 살을 붙여가며 응용력을 기른 뒤,
• 테스트 문제로 완벽하게 내 것으로 만들었는지 최종 점검하는 구조였습니다.

이러한 단계별 학습 덕분에 뇌에 과부하가 걸리지 않고 자연스럽게 풀이 감각이 살아나는 것을 경험할 수 있었습니다.

 

레슨 기록: 점근 표기법 3문제 완벽 해설

Lesson 2. 점근 표기법에서 만난 대표적인 세 문제를 통한 핵심 개념을 정리해 보겠습니다.

 

1. 기본 문제: [기호 변환] 

 

이 문제는 점근적 표기법인 Big-O( Ο ), Big-Omega( Ω ), Big-Theta( Θ )의 근본적인 정의를 묻는 문제였습니다.

• Ο (g(x)): f(x)의 차수가 g(x)보다 작거나 같으면 성립 (상한선)
• Ω (g(x)): f(x)의 차수가 g(x)보다 크거나 같으면 성립 (하한선)
• Θ (g(x)): f(x)와 g(x)의 최고차항 차수가 완전히 같으면 성립

표기법	의미
빅오 (Big-O)	상한선 (Worst Case)	<= (이하)
빅오메가 (Big-Omega)	하한선 (Best Case)	>= (이상)
빅세타 (Big-Theta)	상한과 하한이 같음 (Average Case)	= (같음)

 

# 문제 풀이 

• 조건 (1) 
  f(x)의 차수는 8차, g(x)의 차수는 4차입니다. (f의 차수 > g의 차수)
  ① f(x) = O (g(x)) : 8차 함수가 4차 함수보다 차수가 낮거나 같아야 하는데, 더 높으므로 성립하지 않습니다.
  ② f(x) = Ω (g(x)) : 8차 함수가 4차 함수보다 차수가 같거나 높으므로 성립합니다. 
  ③ f(x) = Θ g(x)) : 두 함수의 차수가 다르므로 성립하지 않습니다.
  
  
• 조건 (2) 
  f(x), g(x) 두 식 모두 최고차항이 2차로 동일합니다. 차수가 같을 때는 O, Ω , Θ 가 모두 성립합니다.
  ④ f(x) = O (g(x)) : 차수가 같으므로 O의 조건(같거나 낮음)을 만족합니다.
  ⑤ f(x) = Ω (g(x)) : 차수가 같으므로 Ω의 조건(같거나 높음)을 만족합니다.
  ⑥ f(x) = Θ (g(x)) : 두 함수의 최고차항 차수가 2차로 완전히 일치하므로 만족합니다.

 

2. 연습 문제: [O, Ω, Θ] 

 

로그(log)가 등장하면서 난이도가 살짝 올라간 것처럼 보이지만, 사실 복잡한 로그 계산 없이 시간 복잡도 증가율 서열만 알면 쉽게 풀리는 문제입니다.

$$\log x \;\ll\; x \;\ll\; x \log x \;\ll\; x^2 \;\ll\; x^3 \;\ll\; x^5 \;\ll\; x!$$

• \(\log x\) (로그): 증가 속도가 가장 느립니다. 데이터가 아무리 늘어나도 연산 횟수가 거의 증가하지 않습니다.
• \(x\) (1차): 데이터 수와 연산 횟수가 그냥 정비례해서 직관적으로 늘어납니다.
• \(x \log x\) (로그 곱하기): 1차 함수 \(x\)보다는 조금 더 빠르지만, 뒤에 올 2차 함수 \(x^2\)보다는 훨씬 느리고 효율적입니다. (대표적으로 효율적인 정렬 알고리즘들의 시간 복잡도입니다.)
• \(x^2, x^3, x^5\) (다항식): 지수(차수)가 커질수록 데이터 증가에 따른 연산 횟수가 엄청나게 빨라집니다. 현업에서는 대용량 데이터 처리 시 지양해야 하는 경계선입니다.
• \(x!\) (팩토리얼): 폭발적인 속도로 증가합니다. 사실상 컴퓨터가 계산을 포기해야 하는 수준의 복잡도입니다.

 

# 문제 풀이

점근적 표기법은 항상 가장 강력하게 증가하는 항(최고차항)만 남기고 나머지는 무시합니다.

• \(f_1(x) = x^2\) ➔ \(x^2\) (2차)
• \(f_2(x) = x^3 + x^2 + x + 1\) ➔  \(x^3\) (3차)
• \(f_3(x) = x! - x \log x + x^2\) ➔ \(x!\)

 

① \( \log x = \mathcal{O}(f_1) \) ➔ \(\log x\) vs \(f_1(x) = x^2\)

• 해석: \(\log x\)가 \(x^2\)보다 작거나 같은가?
• 판정: 로그는 서열 최하위이므로 2차식(\(x^2\))보다 훨씬 작습니다. 따라서 성립합니다.

② \( x^5 = \Omega(f_2) \) ➔ \(x^5\) vs \(f_2(x) = x^3\)

• 해석: \(x^5\)이 \(x^3\)보다 크거나 같은가?
• 판정: 5차가 3차보다 차수가 높으므로 성립합니다.

③ \( x \log x = \Theta(f_3) \) ➔  \(x \log x\) vs \(f_3(x) = x!\)

• 해석: \(x \log x\)와 \(x!\)의 증가 속도가 같은가?
• 판정: \(x!\)은 끝판왕이고, \(x \log x\)는 한참 아래에 있으므로 전혀 다릅니다.

④ \( x = \Omega(f_1) \) ➔ \(x\) vs \(f_1(x) = x^2\)

• 해석: 1차식(\(x\))이 2차식(\(x^2\))보다 크거나 같은가?
• 판정: 1차가 2차보다 클 수 없으므로 성립하지 않습니다.

⑤ \( x \log x = \mathcal{O}(f_2) \) ➔ \(x \log x\) vs \(f_2(x) = x^3\)

• 해석: \(x \log x\)가 \(x^3\)보다 작거나 같은가?
• 판정: 서열을 보면 \(x \log x\)는 2차(\(x^2\))보다도 작습니다. 당연히 3차(\(x^3\))보다는 훨씬 작으므로 성립합니다.

 

3. 연습 문제: [펜트하우스] 

 

• 첫 번째 규칙: \(f(N) = \Theta(g(N))\) 이면 같은 층에 산다.
  즉, 최고차항의 차수가 완전히 똑같은 코드들은 동거(같은 층에 배정)합니다. 상수는 무시합니다.
  
  
• 두 번째 규칙: \(f(N) = \mathcal{O}(g(N))\)이지만반대는 아니라면 , \(f(N)\)은 \(g(N)\)보다 낮은 층에 산다
  즉, 증가 속도가 느린(차수가 낮은) 코드가 아래층에 살고, 증가 속도가 빠른(차수가 높은) 코드가 위층(고층)에 삽니다.
  
  
• 증가 속도가 가장 빠르면 최상층에 살고, 차수가 같으면 같은 층에 배정합니다.

 

# 문제 풀이

주어진 8개의 시간 복잡도를 상수를 떼고 순수한 차수로만 정리해 보겠습니다.

• \(N^3 \) ➔ \( N^3 \)
• \(10N^3 \) ➔ \( N^3 \) (앞의 상수 10은 무시하므로 1번과 동급)
• \(N \log N \) ➔ \( N \log N \)
• \(\log N \) ➔ \( \log N \)
• \(N^2 \log N \) ➔ \( N^2 \log N \)
• \(2^{N+2021} \) ➔ \( 2^N \) (지수의 +2021은 상수를 곱한 것과 같으므로 무시합니다)
• \(\frac{1}{2}N^5 \) ➔ \( N^5 \) (앞의 계수 무시)
• \(2^N \) ➔ \( 2^N \) (6번과 동급)

 

가장 약한 곳부터 아래층에 입주시켜 건물을 쌓아 올립니다.

• 1층: (가장 느림): \(\log N \) (1개)
• 2층: \(N \log N \) (1개)
• 3층: \(N^2 \log N \) (1개)
• 4층: \(N^3, 10N^3 \) (차수가 같으므로 2개가 같은 층에 입주)
• 5층: \(\frac{1}{2}N^5 \) (1개)
• 6층: (최상층 - 가장 빠름): \( 2^{N+2021}, 2^N \) (지수함수가 동급이므로 2개가 같은 층에 입주)

 

• 최상층(6층) 코드의 수: \(2^{N+2021}\), \(2^N\) ➔ 2개
• 그 아래층(5층) 코드의 수: \(\frac{1}{2}N^5\) ➔ 1개

따라서 두 층의 코드 수를 합치면 2 + 1 = 3 이 되므로 정답은 ②번이 됩니다.

 

 

해설과 토론 탭 활용

코드트리를 이용하면서 가장 만족스러웠던 포인트 중 하나는 바로 '코드트리만의 상세한 해설과 토론 내용'이었습니다.

문제를 풀다가 헷갈리거나 틀렸을 때, 단순히 정답 코드만 툭 던져주는 것이 아니라 왜 이 답이 도출되었는지 수학적 기저부터 친절하게 설명해 줍니다. 특히 다른 유저들이 남긴 토론 탭을 보며 "아, 나만 이 부분에서 헷갈린 게 아니구나" 하는 위안과 함께, 미처 생각지 못한 예외 케이스나 꿀팁들을 흡수할 수 있어서 학습 효율이 증가되었습니다.

 

마무리

이전에는 코드를 짤 때 "대충 이 정도면 돌겠지?" 하고 감으로 시간 복잡도를 짐작하곤 했습니다. 하지만 이번 코드트리 약점 돌파 미션을 통해 복잡도의 정확한 수학적 억제선(상한·하한)을 이해하고 나니, 코드를 최적화할 때 어떤 기준으로 접근해야 할지 명확한 가이드라인이 생겼습니다.

 

기초가 흔들리거나 특정 유형에서 자꾸 무너지는 분들이라면, 코드트리의 레슨 시스템을 통해 약점을 파악해 보시는 것을 추천합니다! 

 

 

코드트리 추천인 ID : minisol206
https://www.codetree.ai/accounts/sign-up-only?referralCode=minisol206

청약통장 추천 코드 : 74TXLJ
https://www.codetree.ai/ko/no-free-lunch-2026/?ref=74TXLJ