[211201] 코딩 테스트, 온라인 저지 사이트, 알고리즘 복잡도

모든 게시물은 macOS Monterey 12.0.1 버전을 기준으로 작성하였습니다.
저서 '이것이 취업을 위한 코딩 테스트다 with 파이썬'을 바탕으로 작성하였습니다.

 

코딩 테스트 개념과 배경

 

기업/기관에서 직원이나 연수생을 선발하기 위한 목적으로 시행되는 문제 풀이 시험.

근래 코딩 테스트가 늘어남에 따라 이를 연습할 수 있는 온라인 시스템인 온라인 저지 사이트 인기.

 

 

처음 코딩 테스트를 준비하는 사람을 위한 커리큘럼은 아래와 같다.

 

파이썬 문법 공부 -> 코드업 쉬운 문제부터 200문제 ->
알고리즘 이론과 기출문제 학습 -> 백준 온라인 저지 유형별 문제 풀이

 

https://codeup.kr

CodeUp

 

특히 코드업은 난이도가 낮은 문제가 많아 처음 공부하는 사람에게 적합하다.

[문제] - [문제집] - [기초 100제]를 통해 알고리즘 문제 풀이에서 자주 사용하는 유형을 연습할 수 있다.

 

https://www.acmicpc.net

Baekjoon Online Judge

 

백준 온라인 저지는 유명한 알고리즘 문제 풀이 사이트로 난이도가 다양하고 국내 사용자가 많다는 장점이 있다.

코드업과 다르게 문제 순서가 난이도와 무관하여 초보자들은 좌절감을 느낄 수 있다.

Chrome의 solved.ac 확장 프로그램을 설치하면 백준 온라인 저지 문제의 난이도를 손쉽게 확인할 수 있다고 한다.

[문제] - [알고리즘 분류] 에서 유형별 알고리즘 문제를 선택하여 풀 수 있다는 장점이 있다.

 

https://programmers.co.kr/learn/challenges

코딩테스트 연습

 

2017 ~ 2020 카카오 공채 문제를 모두 제공하고 있으며 본인이 문제를 풀지 못해도

다른 사람들의 풀이 코드를 열람할 수 있다는 장점이 있지만 본인의 '알고리즘 점수'는 차감된다.

 

https://www.swexpertacademy.com

SW Expert Academy

 

삼성에서 공식적으로 제공하는 사이트로 DFS/BFS를 활용해야 하는 탐색과 시뮬레이션 문제를 자주 출제하기에

삼성전자 IT 직군 테스트에 대비할 수 있다. 난이도가 낮은 A형에 도전해보길 책의 저자는 권한다.

---

실습 환경 구축하기

 

본 저서는 파이썬 3.7을 기준으로 소스코드를 제공한다. 실제 코딩 테스트를 치르는 환경 역시 온라인 형태의

IDE(Integrated Development Environment)일 확률이 높기에 저자는 온라인 실습 환경을 추천하고 있다.

 

https://replit.com/

The collaborative browser based IDE

 

리플릿은 가장 간단하면서도 유용한 무료 개발 환경으로 로그인하면 다른 개발자와 동시에 코딩할 수 있다.

 계정 없이도 사용이 가능하나 온라인 저장 등의 기능이 동작하지 않는다고 하여 github 연동으로 가입하였다.

 

 

알고리즘 코딩 테스트를 준비하는 과정에서 본인만의 소스코드를 관리하는 습관을 들이면 좋다.

자주 사용하는 알고리즘을 라이브러리화 시킨다고 생각하자.

 

https://github.com/ndb796/Python-Competitive-Programming-Team-Notes

GitHub - ndb796/Python-Competitive-Programming-Team-Notes: Python Library for Programming Competition

---

복잡도

 

복잡도는 알고리즘의 성능을 나타내는 척도이다. 공포의 포스텍 필기시험의 기억이 스멀스멀..

 

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

 

즉, 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고,

공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

 

코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 처리하고 실행하기까지 걸리는 시간 제한이 존재한다.

이를 넘기면 Time Limit Exceeded 메세지와 함께 오답으로 처리된다.

 

시간 복잡도를 표현할 때는 빅오 표기법을 사용한다.

간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법이다.

하지만 3N^3 + 5N^2 + 1,000,000 의 연산 횟수를 가지는 알고리즘은 O(N^3)이라 표기되지만

N = 10이면 1,003,500의 연산 횟수를 가지므로 상수가 가지는 영향력이 크다.

따라서 빅오 표기법이 항상 절대적인 것은 아니라는 점을 기억해야 한다.

 

array = [3, 5, 1, 2, 4] # 5개의 데이터 (N=5)
summary = 0
# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
	summary += x
# 결과 출력
print(summary)

 

위 예제에서는 5개의 데이터를 받아 차례로 5회 더한다. 이때 연산 횟수는 N에 비례한다.

물론 소스코드에는 summary에 0을 지정하는 연산도 있고, 결과를 추출하는 연산도 있지만

이는 N이 무한히 커질 때 영향력이 매우 작아진다. 따라서 위 소스코드에서 가장 영향력이 큰 부분은

N에 비례하는 연산을 수행하는 반복문 부분이므로 시간 복잡도를 O(N)이라고 표기한다.

 

다음은 어떤 시간 복잡도를 가질지 생각해보자.

 

array = [3, 5, 1, 2, 4]

for i in array:
	for j in array:
    	temp = i * j
        print(temp)

 

위 소스코드는 데이터의 개수가 N개일 때, O(N^2)의 시간 복잡도를 가진다.

2중 반복문이라서 N x N 연산이 필요하다는 것을 유추할 수도 있지만 모든 2중 반복문의 시간복잡도가 같진 않다.

추후 공부할 Quick Sort의 시간 복잡도는 평균 O(NlogN)이지만 최악의 경우에 O(N^2)의 시간 복잡도를 가진다.

코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 중요하므로 최악의 경우의 시간 복잡도를 고려해야 한다.

 

 

위 시간 복잡도 표를 참고하자.

일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가면

• C언어 기준으로 1 ~ 3초 가량의 시간이 소요된다.
• Python 기준으로 5 ~ 15초 가량의 시간이 소요된다.

따라서 삼차 시간을 넘어가면 일반적으로 시간 제한에 의해 문제 풀이에서 사용하기 어렵다.

 

Note | 시간 복잡도에서 연산은 사칙 연산뿐만 아니라 비교하는 연산 역시 한 번의 연산으로 취급한다.

 

알고리즘 대회 참가에 익숙한 사람들은 문제 조건을 확인하고 사용할 수 있는 알고리즘을 추리기도 한다.

시간 제한이 1초인 문제를 해결하는 예시를 몇 가지 소개해보면 

• N 범위가 500 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N 범위가 2,000 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N 범위가 100,000 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N 범위가 10,000,000 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다.

일반적으로 메모리 사용량 기준은 MB 단위로 제시된다. 쉽게 말해 코딩 테스트 문제에서 보이는

시간 제한 1초, 메모리 제한 128MB 와 같은 문장은 시간 복잡도와 공간 복잡도를 함께 제한하기 위함이다.

 

 

위와 같이 파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다.

그렇다면 다음을 비교하는 소스코드를 작성해보자.

 

선택 정렬 vs 파이썬 기본 정렬 라이브러리
-> 선택 정렬은 최악의 경우 O(N^2), 파이썬 기본 정렬 라이브러리는 최악의 경우 O(NlogN)의 시간 복잡도를 가진다.

 

 

선택 정렬은 28초, 기본 정렬 라이브러리는 1초도 채 걸리지 않을 만큼의 짧은 시간이 걸렸다.

저자는 코딩 테스트에서 문제를 풀 때는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게

프로그램을 작성해야 한다고 강조한다.

 

게시물 하나 작성하면서 사용했던 replit 고생했고 ~

익숙한 코랩으로 계속 가야겠다. - 끝 -