1. 온라인 저지
프로그래밍 대회나 코딩 테스트에 나올 법한 문제를 시험해보는 온라인 시스템
1) 해외
- 코드포스 https://codeforces.com/
- 탑코더 https://www.topcoder.com/
- 릿코드 https://leetcode.com/
- 기업 코딩 테스트 준비를 위한 문제들
- 코드셰프 https://www.codechef.com/
2) 국내
- 백준 온라인 저지 https://www.acmicpc.net/
- 대기업 기출 문제, 유형별 문제
- 코드업 https://codeup.kr/
- 처음 알고리즘 문제 풀이를 시작할 때 좋은 입문자용 사이트
- 단계별로 문제가 제시되어 있음
- 프로그래머스 https://programmers.co.kr/
- 인기 it 대기업 문제
- SW Expert Academy https://swexpertacademy.com
2. 온라인 개발 환경
1) Python
- 리플릿
- 파이썬 튜터
- PyCharm
2) C++
- Dev-C++
3. 자신만의 소스 코드 관리
-
알고리즘 코딩 테스트를 준비하는 과정에서 자신만의 소스코드를 관리하는 습관을 들이면 좋음
-
자신이 자주 사용하는 알고리즘 코드를 라이브러리화 하면 좋음
-
내가 생성한 파이썬 알고리즘 노트
: https://github.com/syb0228/Python-Coding-Test-Notes
4. 코딩 테스트 최신 출제 경향
1) 출제 빈도가 높은 알고리즘 유형
- Greedy (쉬운 난이도)
- 구현
- DFS/BFS를 활용한 탐색
2) 2016 ~ 2019년에 출제된 알고리즘 유형
- 구현 33.0%
- BFS/DFS 20.9%
- Greedy 19.8%
- sort 8.2%
- dynamic programming 8.2%
- binary search 3.8%
- shortest path 3.3%
- graph 이론 2.7%
3) 주요 기업 코딩 테스트 유형 분석
5. 알고리즘 성능 평가
1) 복잡도
복잡도는 알고리즘의 성능을 나타내는 척도
- 시간 복잡도
- 공간 복잡도
- 복잡도가 낮을수록 일반적으로 좋은 알고리즘
2) 알고리즘 설계 tip
-
일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우, Python 기준으로 통상 5~15초 가량의 시간이 소요됨
-
코딩 테스트 문제에서 시간 제한은 통상 1~5초 가량임
- 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적임
3) 요구사항에 따라 적절한 알고리즘 설계하기
-
문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)
-
시간 제한이 1초인 문제를 만났을 때, 일반적인 기준은 아래와 같음
- N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있음
- N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘 설계
- N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘 설계
- N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘 설계
4) 수행 시간 측정
import time
start_time = time.time() # 측정 시작
# 프로그램 소스 코드
end_time = time.time() # 측정 종료
print("time : ", end_time - start_time)6. 알고리즘 문제 해결 과정
- 지문 읽기 및 컴퓨터적 사고
- 요구사항(복잡도) 분석
- 문제 해결을 위한 아이디어 찾기
- 소스코드 설계 및 코딩
- 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형식의 문제를 출제함
Backend development