Status
Published
Category
알고리즘
Tags
알고리즘
전공수업
Python
이모저모
Author
Published Date
Jul 4, 2025
Featured Image
코딩 테스트는 왜 존재할까?
기업이 개발자를 채용할 때 어떤 기준으로 채용을 할 까?
기업은 어떤 개발자를 뽑기 원할까?
기업 입장에서는 수백, 수천, 수만명의 신입 개발자들을 마주한다.
이력서에 “C언어 가능합니다.”, “JAVA 사용해봤습니다.” 적혀 있다고 해서 그 사람이 실제로 문제를 효율적으로 해결할 수 있는지는 모른다.
학점이 높다고 해서, 자격증이 많다고 해서, 무조건 개발 실력이 뛰어난 것도 아니다.
그렇다면 기업은 어떻게 사람을 선별할까?
“이 사람이 실제로 일할 수 있는 실력을 갖췄는가”를 보고 싶은 것이다. ‘일할 수 있는 실력’이라는 건 단순히 컴퓨터 언어 문법을 안다는 게 아니라, 주어진 문제를 정확히 이해하고, 필요한 알고리즘과 자료구조를 빠르게 떠올릴 수 있으며, 시간 안에 효율적인 코드로 해결할 수 있는 능력을 말한다.
코딩 테스트는 그냥 “문제 푸는 시험”이 아니다.
마치 개발자의 실전 시뮬레이션이다.
주어진 시간, 제한된 조건, 정확한 구현, 그리고 효율성까지.
하나라도 놓치면 통과하기 어렵다. 바로 효율성!
코드가 맞았더라도, 너무 느려서 시간 초과가 나면 실패다.
실제로 사용하는 서비스라면,
정답을 내는 것보다 얼마나 빠르게, 효율적으로 결과를 줄 수 있는가가 훨씬 중요하다.
그래서 시간 복잡도 개념이 중요해진다.
→ “이 코드, 1초 안에 답을 줄 수 있을까?”
바로 이 질문에 답하려면, 시간 복잡도를 이해해야 한다.
그럼 이제,
왜 1억 번 안에 끝내야 하는지
이야기를 시작해보자.
시간 복잡도의 등장
1초 만에 10,000개의 데이터를 처리하는 A 코드가 있고,
1초 만에 10개의 데이터만 처리하는 B 코드가 있다면,
딱 봐도 첫 번째 코드가 훨씬 빠른 것처럼 느껴진다.
하지만 이건 지금 당장의 데이터 양이 작을 때 이야기다.
만약 1억 개의 데이터가 들어온다면 어떨까?
처음에 빨라 보였던 첫 번째 코드는
처리 시간이 10배, 100배, 1,000배까지 늘어나며 성능이 급격히 떨어질 수 있다.
반면, 처음엔 느렸던 두 번째 코드는
입력 크기가 커져도 처리 속도가 완만하게 증가할 수 있다.
결국 중요한 건 지금의 속도가 아니라,
데이터가 많아졌을 때, 그 코드가 얼마나 “버텨주는가다.
우리는 단순히 “지금 빠른 코드”를 찾는 게 아니라,
입력 크기가 커졌을 때도 견딜 수 있는 코드를 고민해야 한다.
이런 코드의 성능 변화 추이를 표현한게 바로 시간 복잡도(Time Complexity)란 개념이다.
💡 왜 ‘1억 번 안에’ 끝내야 할까?
코딩 테스트 문제는 대부분 시간 제한 1초
그리고 컴퓨터는 1초에 약 1억 번의 연산을 수행할 수 있다고 가정한다. (C++ 기준)
이 말은 곧,
우리가 작성한 코드가 1억 번 이내의 연산으로 문제를 해결해야 한다.
❓실제로 연산 횟수를 왜 따지는 걸까? Why!!
우리는 코드가 몇 초 걸리는지 직접 측정하지 않는다.
왜냐하면 그건 환경마다 달라질 수 있기 때문이다.
- 내 컴퓨터에선 0.5초 걸리지만,
- 채점 서버에선 1.2초 걸릴 수도 있다.
그럼 공정하지 않다. 이게 공정한거면 나는 양자컴퓨터로 그냥이제 팍
그래서 언어, 환경, 기기와 무관하게 코드의 성능을 판단할 수 있는 지표가 필요하다.
그게 바로 연산 횟수(=시간 복잡도)다.
✅ 1억 번이 기준이 되는 이유
1초에 1억 번이라는 기준은
현실의 컴퓨터 처리 속도 + 여유 버퍼 + 채점 시스템 평균치를 반영한 것이다.
물론 언어마다 처리 속도는 다르다:
언어 | 1초당 연산 수 (대략) |
C++ | 약 1억 번 |
Java | 약 5천만 번 |
Python | 약 1천만 번 |
그래서 대부분의 코딩 테스트 문제는
“C++ 기준으로 1억 번 이내의 연산”을 통과 기준으로 잡느다.
그 후에 언어별 차이를 고려해
- Python 사용자에겐 좀 더 여유 있는 입력 범위를 주거나
- Java 사용자에겐 시간을 약간 더 주는 등
채점 시스템이 언어 간 차이를 조정해준다.
💬 현실과 연계
서비스에 접속한 유저가 1초 이상 기다린다면? → 이탈 가능성 증가
백엔드 서버에서 응답이 늦으면? → 병목 발생
데이터가 많아질수록 비효율적인 코드는 발목을 잡는다
그래서 기업도 이렇게 묻는 것이다:
이 양반, 느려지지 않는 코드를 짤 줄 아는가?
Big-O 표기법의 등장
앞에서 계속 말했듯이, 우리는 코드를 “지금 빠른가?” 로만 판단하지 않는다.
데이터가 커졌을 때도 견디는가?
그 코드의 성능이 어떻게 변화하는지가 훨씬 중요하다.
데이터의 증가에 따라 속도 차이를 정량적으로 비교할 수 없을까?
빅오 표기법(Big-O)
- 빅오 표기법은 “입력 크기(N)”에 따라 코드가 얼마나 느려지는지를 수학적으로 표현한 것이다.
즉 : 코드가 얼마나 빨리 망가지는지 보여주는 지표이다.
종류는 아래 표를 확인하자!
시간 복잡도 | 의미 | 예시 상황 |
O(1) | 입력이 아무리 커져도 항상 똑같은 시간 | 해시 탐색 |
O(log N) | 조금씩 느려지지만 거의 영향 없음 | 이진 탐색 |
O(N) | 입력이 2배면 시간도 2배 | 배열 순회 |
O(N log N) | 대부분의 정렬 알고리즘 | 퀵정렬 등 |
O(N²) | 입력이 조금만 커져도 급격히 느려짐 | 이중 반복문 |
O(2ⁿ) | 거의 쓰면 안 되는 수준 | 완전 탐색 |
예시 상황의 알고리즘들은 나중에 알아보자! 지금은 시간 복잡도와 의미만 보자.
- O(1) : 마법처럼 바로 정답 나옴
- O(N) : 일일이 모든 사람한테 물어봐야 함
- O(N²) : 한 명마다 모든 사람을 또 확인함 (지옥)
- 🔹 O(1) : 입력이 아무리 커져도 변하지 않음 (최고의 효율)
- 🔹 O(log N) : 느리게 증가 (예: 이진 탐색)
- 🔹 O(N) : 선형 증가 (예: 단순 반복문)
- 🔹 O(N log N) : 병합정렬 등 효율적 정렬
- 🔹 O(N²) : 중첩 반복문 (버블 정렬 등)
- 🔹 O(2ⁿ) : 지수 증가 (입력 조금만 커져도 폭발적 증가)
결국 중요한 건 “버티는 힘”
코드는 단순히 “돌아가는 것”만으로는 부족하다.
많은 양의 데이터가 들어왔을 때도 무너지지 않는 탄탄한 구조
그게 바로 우리가 코딩 테스트에서 시간 복잡도를 따지는 이유입니다.
‘지금 빠른가’보다 더 중요한 건
“많아 졌을 때도 견디는가”
코딩 테스트는 단순한 시험이 아니라
현실에서 마주할 문제를 버틸 수 있는지를 묻는 진짜 시뮬레이션이다.