[코테] 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기 (1)

시작하기

동빈나 - 이코테 2021 강의 몰아보기

언어 : Python

온라인 개발환경 : 리플릿 (추천! => 이후 블로그나 깃허브 등에 기록)

온라인 저지 : 백준, 코드업, 프로그래머스 (국내) / 코드포스, 탑코더, 릿코드, 코드셰프 (해외)

자신이 자주 사용하는 알고리즘 코드를 라이브러리화하면 좋다. (a.k.a 팀노트)

IT 기업 코딩테스트 최신 출제 경향 (2020~2021 기준)

🔥 가장 출제 빈도가 높은 알고리즘 유형 : 그리디(쉬운 난이도), 구현, DFS/BFS를 활용한 탐색 🔥

알고리즘 성능 평가

복잡도(Complexity) : 알고리즘의 성능을 나타내는 척도

• 시간 복잡도 : 수행 시간 분석
• 공간 복잡도 : 메모리 사용량 분석

복잡도가 낮을수록 좋은 알고리즘

빅오(Big-O) 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법

• ex) 3N^3 + 5N^2 + 10000 => O(N^3)

[좋음]
O(1) : 상수시간
< O(logN) : 로그시간
< O(N) : 선형시간
< O(NlogN) : 로그선형시간
< O(N^2) : 이차시간
< O(N^3) : 삼차시간
< O(2^n) : 지수시간
[나쁨]

알고리즘 설계 Tip

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

• C언어 : 통상 1~3초 가량의 시간이 소요됨
• Python : 통상 5~15초 가량의 시간이 소요됨

⏰ 코딩테스트 문제에서 시간제한은 통상 1~5초 가량 ⏰
문제에 명시되어 있지 않은 경우 대략 5초라고 생각

1. 요구사항에 따라 적절한 알고리즘 설계하기

⌛ 문제에서 가장 먼저 확인해야 하는 내용 = 시간제한(수행시간 요구사항) ⌛

시간제한이 1초인 문제를 만났을 때, 일반적인 기준

• N의 범위가 500인 경우 : O(N^3)
• N의 범위가 2,000인 경우 : O(N^2)
• N의 범위가 100,000인 경우 : O(NlogN)
• N의 범위가 10,000,000인 경우 : O(N)

2. 알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

대부분 핵심 아이디어를 캐치하면 간결하게 소스코드를 작성할 수 있는 형태

3. 수행시간 측정 소스코드 예제

import time
start_time = time.time() # 측정시작

# 프로그램 소스코드

end_time = time.time() # 측정종료
print("time: ", end_time - start_time) # 수행시간 출력