1. 코딩 테스트 출제 경향, 성능 평가 방식

코드업이 초보자에게는 좋음.

자바가 C++보다 더 느리고 코드가 길다.

온라인 코딩 테스트를 준비할 때는 온라인 환경을 이용하는 것이 좋다.

 

** 온라인 개발 환경 (Python)

리플릿 : https://repl.it/languages/python3파이썬 튜터 : http://pythontutor.com/visualize.html

** 오프라인 개발 환경 : 파이참

 

추천하는 방식은 온라인 개발 환경에서 개발을 하고 블로그에 정리하는 것 !!

자신이 자주 사용하는 알고리즘 코드를 라이브러리화 하는 것이 좋다 !!

팀 노트 예시) https://github.com/ndb796/Python-Competitive-Programming-Team-Notes

문제 유형에 따라서 비슷한 코드를 사용하기 때문에 !!

 

** 가장 출제 빈도가 높은 알고리즘 유형

• 그리디 (쉬운 난이도)

• 구현

• DFS/BFS를 활용한 탐색

 

카카오 준비하는 사람들은 카카오 기술 블로그 참고하기!

카카오 2차에서는 개발형 코딩테스트를 실행함! (추천시스템 개발, 시뮬레이션 개발)

카카오 같은 경우에는 구현이나 문자열을 처리하는 방식의 문제들이 많이 출제됨

 

---

 

복잡도(Complexity)

복잡도는 알고리즘의 성능을 나타내는 척도이다

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

(높다는 것은 시간이 많이 걸리다는 의미)

• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

(높다는 것은 메모리가 많이 사용된다는 의미)

동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

빅오 표기법(Big-O Notation)

가장 빠르게 증가하는 항만을 고려하는 표기법이다.

함수의 상한만을 나타내게 된다.

예를 들어 연산 횟수가$3N^3+5N^2+1,000,000$인 알고리즘이 있다.

빅오 표기법에서는 차수가 가장 큰 항만 남기므로$O(N^3)$으로 표현된다.

빅오표기법 성능이 좋은 순서대로

순위	명칭	설명
O(1)	상수 시간(Constant time)	상수 번 (몇 번)의 연산만 거치면 된다는 의미이다.
O(logN)	로그 시간(Log time)	log N에 비례하는 만큼 실행된다.
O(N)	선형 시간(Linear time)
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

시간 복잡도 계산하는 예제

N개의 데이터의 합을 계산하는 프로그램 예제

array=[3,5,1,2,4] summary=0  for x in array: 	summary += x  print(summary)

수행 시간은 데이터의 개수 N에 비례할 것임을 예측할 수 있다.

시간 복잡도 :$O(N)$

 

이중 반복문을 이용하는 예제

array=[3,5,1,2,4] for i in array: 	for j in array: 		temp = i*j 		print(temp)

시간 복잡도 :$O(N^2)$

소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 한다.

 

---

 

알고리즘 설계 Tip

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

C언어를 기준으로 통상 1~3초 가량의 시간이 소요된다.

Python을 기준으로 통상 5~15초 가량의 시간이 소요된다.

PyPy의 경우 때때로 C언어보다도 빠르게 동작하기도 한다. (?)

 

코딩 테스트 문제에서 시간 제한은 통상 1~5초 가량이라는 점에 유의 !

혹여 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적이다.

보통 채점 사이트에서는 python이 1초에 2000만번의 연산만 가능하다고 생각하고 해야됨 !

어느 정도 수행 시간을 계산하면서 해야된다.

 

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

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

시간 제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다.

• N의 범위가 500인 경우 : 시간 복잡도가$O(N^3)$인 알고리즘을 설계

• N의 범위가 2,000인 경우 : 시간 복잡도가$O(N^2)$인 알고리즘을 설계

• N의 범위가 100,000인 경우 : 시간 복잡도가$O(NlogN)$인 알고리즘을 설계

• N의 범위가 10,000,000인 경우 : 시간 복잡도가$O(N)$인 알고리즘을 설계

핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 출제한다.

 

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

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

 

 

Uploaded by Notion2Tistory v1.1.0