[ 이 시리즈에서 작성하는 내용은 이것이 코딩 테스트다 - 나동빈 에서 발췌한 내용을 인용했습니다. ]
✏️ 서론
제대한지 어느덧 6개월이 되어가고, 취업을 하겠다는 마음 굴뚝같지만, 정작 움직이지 않는 게으른 나를 채찍질 하고 싶어 작성하는 글이다.
웹 개발자로 취업하려면 컴퓨터공학 지식이나 GET, POST 방식의 차이 혹은 TCP, UDP, HTTP, HTTPS의 개념과 원리를 깨우쳐 기술면접에서 논리정연하게 면접관에게 설명하는것도 중요하지만
무엇보다 프로그래밍의 근간이 되는 컴퓨터에서 작성하는 코드가 어떻게 동작하는지 원리를 알아야한다고 생각한다.
그래서 내 벨로그 첫글을 장식했던 [ 20년 하반기 ] 삼성 코딩테스트 후기 의 후속조치로 코딩테스트를 준비하고자 한다.
현재 나의 계획은 21년 하반기 취업을 마지노선으로 잡고 취업준비에 몰두하고 있다.
그런데, 채용사이트(사람인, 원티드, 잡코리아 등등 ...)를 뒤져보니 내가 가고싶다고 생각하는 회사(굳이 IT대기업이 아니더라도 복지나 연봉이 좋은 스타트업들..)들은 하나같이 채용전형에 코딩테스트가 들어가있었다. 🥲 🥲
경쟁사회에 살면서 기업이 원하는 수준까지 올라가려면 맞춰가야지 어떡하겠나!
그래서 남은 기간동안 코딩테스트 & 포트폴리오를 함께 준비해보려고 한다.
스파르타코딩클럽 오프라인 강의를 들으러 강남을 오갔을 때 한번은 수업시간까지 시간이 남아 강남역 영풍문고에서 코딩관련 서적을 찾아보다 이것이 코딩 테스트다 - 나동빈이란 책을 보게되었다.
대학교시절 코딩을 처음하고 싶다는 생각을 했을 때 자주 들었던 유튜버였는데
지금은 출판까지 하신걸 보니 정말 대단하다는 생각이 들었다.
글쓴이가 책에서 목표하는 학습 순서는 한 달(4주)에 걸쳐 초급단계를 완독하는 과정을 추천했다. (하루 3시간씩 알고리즘에 투자한다는 기준)
그래서, 오늘부터라도 하루하루 책을 읽으면서 무엇을 배웠는지 벨로그에 남기려고한다.
✏️ 본론
코딩테스트에 있어 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다.
복잡도는 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)로 나눌 수 있다.
시간복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고
공간복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 즉, 다음과 같이 요약 할 수 있다.
- 시간복잡도: 알고리즘을 위해 필요한 연산의 횟수
- 공간복잡도: 알고리즘을 위해 필요한 메모리의 양
효율적인 알고리즘을 사용한다고 가정했을때, 보통 시간복잡도와 공간복잡도는 일종의 거래 관계(Trade-off)가 성립하는데, 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.
📍 시간복잡도(Time Complexity)
알고리즘 문제를 풀 때 단순하게 '복잡도'라고 하면 보통 시간복잡도를 의미한다.
코딩테스트에서 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행결과를 출력하는데까지 걸리는 시간을 의미한다.
시간복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 빅오 표기법은 엄밀한 정의는 아니지만 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
다음 예제는 5개의 데이터를 받아 차례로 5회 더해주는 코드이다.(N=5)
이때 연산횟수는 N에 비례하는것을 알 수 있다.
소스코드에서 summary 변수에 값을 대입하는 연산도 있고 summary의 변수에 값을 출력하는 연산도 있다.
하지만, N이 커짐에 따라서 무시할 수 있을 정도로 작아질 것이기 때문에,
가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문이므로 시간 복잡도를 O(N)이라 표기한다.
# 5개의 데이터( N = 5 )
array = [1, 2, 3, 4, 5]
# 합계를 저장 할 변수
summary = 0
# 모든 데이터를 하나씩 확인하며 합계를 계산
for n in array:
summary = summary + n
print(summary)
👉🏽 15그럼, 다음 소스코드는 어떤 시간 복잡도를 가질까?
a = 5
b = 7
print(a+b)
👉🏽 12단순히 대입 연산과 출력 함수를 무시하고 보면, 이 소스코드의 연산 횟수는 1이다. 더하기 연산이 한 번 수행되기 때문이다. 이는 상수 연산이므로 시간 복잡도는 O(1)로 표현 할 수 있다.
마지막으로 다음코드는 어떤 시간 복잡도를 가질까?
array = [1, 2, 3, 4, 5]
for i in array:
for j in array:
temp = i * j
print(temp)
👉🏽 25이 소스코드는 데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N^2)의 시간 복잡도를 가진다. 2중 반복문을 사용하여 각 원소에 대해 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문이다. 실은 간단한 2중 반복문이라서 N x N 만큼의 연산이 필요하다는 것을 유추 할 수 있다.
하지만, 모든 2중 반복문은 시간 복잡도가 O(N^2)이 아니다. 만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야한다. 따라서, 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 한다는 점을 잊지말자.
일반적으로 코딩테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다.
따라서, 최악의 경우의 시간 복잡도를 우선적으로 고려하자.
| 빅오표기법 | 명칭 |
|---|---|
| O(1) | 상수시간(Constant Time) |
| O(logN) | 로그시간 |
| O(N) | 선형시간 |
| O(NlogN) | 로그 선형 시간 |
| O(N^2) | 이차 시간 |
| O(N^3) | 삼차 시간 |
| O(2^n) | 지수 시간 |
일반적으로 코딩테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다. 왜냐하면 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산횟수가 10억을 넘어가면 C 언어를 기준으로 통상 1초 이상의 시간이 소요된다.
이때, N의 크기가 5,000이 넘어가면 족히 10초 이상의 시간이 걸릴 수 있다. 특히, 파이썬은 더욱 오래 걸리며, 코딩 테스트문제에서 시간 제한은 1~5초가량이므로 보통 연산 횟수가 10억을 넘어가도록 작성하면 오답판정을 받을 수 있다.
일반적으로 문제를 풀 때의 예시를 몇 가지 소개하겠다.
다음은 모두 시간 제한이 1초인 문제에 대한 예시이다.
- N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
📍 공간복잡도(Space Complexity)
공간 복자도를 표기할 때도 마찬가지로 빅오 표기법을 사용한다. O(NlogN), O(N^2)처럼 말이다.
코딩테스트 문제는 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다.
먼저, int 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자.
- int a[1000]: 4KB
- int a[1000000]: 4MB
- int a[2000][2000]: 16MB
코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한한다. 즉, 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야한다는 의미이다.
📍 시간과 메모리 측정
파이썬에서는 프로그램 수행 시간과 메모리를 측정 할 수 있다. 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.
import time
# 측정시작
start_time = time.time()
# 측정종료
end_time = time.time()
# 수행시간 출력
print('time: ', end_time - start_time)그렇다면, 선택정렬과 Sort정렬(파이썬의 기본 라이브러리)의 수행시간을 비교해보자.
from random import randint
import time
array = []
for _ in range(10000):
array.append(randint(1, 100))
start_time = time.time()
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index > array[j]]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
end_time = time.time()
print('선택 정렬 시간측정:', end_time - start_time)
sort_start_time = time.time()
array.sort()
sort_end_time = time.time()
print("sort 시간:", sort_end_time - sort_start_time)
👉🏽 선택 정렬 시간측정: 8.62038803100586
sort 시간: 0.0010328292846679688CPU따라 다르겠지만, 선택정렬은 8초, sort라이브러리는 0.001초라는 시간이 소요됐다.
만약, 동일한 기능을 수행할 때는 당연히 후자 알고리즘을 선택할 것이다.
이처럼, 코딩 테스트는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다. 소스코드가 복잡하게 생겼다와는 다른 말로 사용된다는 점을 기억하자.
✏️ 결론
내가 알고리즘 문제를 풀겠다고 다짐한 뒤 CodeUp에서 코딩테스트를 볼때 문제자체를 이해 못한 적이있었다.
문제에서 시간 제한(1분), 메모리 제한용량(128MB)이라고 적혀있는데, 당시에 이 문제가 당최 무슨 말을 의미했는지 몰랐다.
하지만, 지금 책의 서론부분을 읽고나서 무슨말인지 이해되었다.
🧐 코딩테스트는 결국 최대한 복잡도가 낮게 작성하라는 뜻인것 같다.
다만, 본론의 코드예시 중 선택정렬코드는 아직 완벽하게 이해하지 못했지만 알고리즘을 풀다보면 언젠가 해석할 수 있을 날이 오지 않을까?!
