[ Algorithm ] 온라인 코딩 테스트 준비하기(온라인 코딩 테스트 사이트, 온라인 개발 환경, 복잡도란)

코딩 테스트란?

---

• 기업/기관에서 지원자 수가 많을 때 효과적으로 선별하기 위한 채용 과정
• 소규모 프로그램을 개발하거나 알고리즘 문제 풀이 등이 있음
  
• 대부분 공채에서는 알고리즘 코딩 테스트를 본다.
  
• 코딩 테스트는 뛰어난 프로그래밍 실력을 요구하는 것이 아닌 실제 개발에서 사용될 법한 구현 기법들을 통해 문제 해결 능력을 평가하는 것
  
• 코딩 테스트에서 대부분 상위 5% 미만의 사람만이 모든 문제를 풀 수 있으며 전체 문제 중 절반 이상을 정확하게 해결하면 합격할 수 있다.
  
• 대회 입상이 목표가 아니면 고급 알고리즘까지 공부할 필요는 없다.
  
• 정답을 맞추는 것도 중요하지만 어떤 방법으로 문제에 접근해 어떤 알고리즘을 사용했는지 설명할 수 있어야 한다.
  

 

온라인 코딩 테스트 준비 사이트

---

1. 코드업

• 알고리즘을 잘 모르거나 입문용으로 좋음
• [문제] > [문제집] > [기초 100제] 꼭 풀어볼 것!
• 200문제 정도 푼 다음 백준으로 넘어갈 것

2. 백준 온라인 저지

• 국내에서 가장 유명한 알고리즘 문제 풀이 사이트
• 문제 순서는 난이도와 무관
• 크롬의 solved.ac 확장 프로그램을 설치하여 난이도 정보 확인!
• [문제] > [알고리즘 분류] 에서 유형별로 알고리즘을 선택해 풀 수 있다는 장점
• 한 유형씩 공부하고 싶을 때 유용

3. 프로그래머스

• 카카오 공채 문제 제공
• 다른 사람들의 풀이 코드 열람 가능

4. SW Expert Academy

• 삼성에서 공식적으로 제공하는 알고리즘 학습 사이트
• '상시 SW 역량테스트'를 통해 본인의 실력을 가늠할 수 있음
• 가장 낮은 난이도인 A형에 응시해볼 것!
• 삼성전자는 DFS/BFS를 활용하는 탐색과 시뮬레이션 문제 유형이 자주 출제

 

온라인 개발 환경

---

1. 리플릿

• 로그인하면 협업, 온라인 저장 기능 사용가능

2. 파이썬 튜터

• 소스코드 입력하고 [Visualize Execution] 누르면 코드를 단계별로 실행
• 실제 메모리에 데이터가 부여되는지 시각적으로 보여줌

3. 온라인 GDB

• 디버깅 기능 제공

 

복잡도

---

* 복잡도 : 알고리즘의 성능을 나타내는 척도로 시간 복잡도와 공간복잡도로 나누어짐 => 동일한 기능을 수행하는 알고리즘이라면 복잡도가 낮을수록 좋은 알고리즘이다!

 

1. 시간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지(필요한 연산의 횟수)
• 단순하게 복잡도라고 말하면 보통 시간 복잡도를 의미
• 빅오(Big-O) 표기법 : 시간 복잡도의 표현법으로 가장 빠르게 증가하는 항만을 고려하는 표기법(함수의 상한만을 나타냄)

표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

 

• 위쪽에 있을수록 더 빠름
• 일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하므로 우선적으로 고려해야 한다.
• 일반적으로 O(N³)을 넘어가면 연산 횟수가 10억이 넘어 문제 풀이에서 사용하기 어려움
• 보통 시간 복잡도에서의 '연산'은 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연상 등과 같은 기본 연산을 의미
• 알고리즘 풀이에 능숙한 사람들은 문제를 해석하기 전 조건을 먼저 확인해 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성할 지 생각한다!

2. 공간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지(필요한 메모리의 양)
• 공간 복잡도도 시간 복잡도와 마찬가지로 빅오 표기법을 이용한다.
• 보통 코딩 테스트에서는 메모리 사용량을 128~512MB로 제한하므로 데이터 개수가 1,000만 단위를 넘지 않게 올고리즘을 설계해야 한다.

 

시간과 메모리 측정

---

* 실질적으로 알고리즘의 소요 시간을 확인해야 작성한 알고리즘의 효율성을 알 수 있다.

 

수행 시간 측정

import time

start_time = time.time()

# 프로그램 코드

end_time = time.time()
print("time :", end_time - start_time)