자신만의 소스코드 관리하기
- 자신만의
코드 템플릿을 만들자 - 대표적인 알고리즘 (
정렬,최단 경로등 )의 기본형에 대해서 미리 코드를 구현해놓자. - 자신의 코드를
라이브러리화해서 깃허브에서 관리하는 것을 추천
코딩테스트 최신 출제경향
- 시간 : 2~5시간
- 출제빈도 :
구현,DFS / BFS,그리디가 높다.
코딩테스트 준비사항
- 적절한 프로그래밍 언어 선택
- 알고리즘 유형 별로 이론 및 핵심 문제를 10개 이상 풀어보기
- 정렬- DFS/BFS
- 구현
- 완전탐색
- 그리디
- 원하는 기업 기출이나 유사한 문제 풀기
시간 복잡도
- 알고리즘의 성능을 나타내는 척도
- 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행시간 분석
- 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 우수
- 복잡도가 높다 -> 오래 걸린다.
- 복잡도가 낮다 -> 빠르고, 결과가 금방 나온다.
시간 복잡도의 표기
빅오표기법
- 가장 빠르게 증가하는 항만을 고려하는 표기법
- 함수의 상한을 나타낸다.
- 3N^3 + 5N^2 + 1000000에서 (데이터크기 N)
- 여기서 가장 빠르게 증가하는 항 (차수가 가장 높은 항은) 3N^3이므로
- Big-O표기법에서는 차수가 가장 큰 항에서 계수를 제외하여 O(N^3)으로 표기한다.
복잡도 표기
-
상수시간
사칙연산을 수행하면 그냥 그게 상수시간 -
로그시간
상수시간에 가까울만큼 빠른 경우가 많다. 상수시간만큼 빠르다고 취급되긴하다. 상수 다음으로 좋다. -
선형시간
어떤 원소가 있는지 한번씩 돌면서 보면 그렇다. -
로그 선형시간
-
이차 시간
동적계획법 등
2중 반복문법
- 모든 2중 반복 문법의 시간 복잡도가 이차시간은 아니다.
- 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수도 고려해야 한다.
- 삼차 시간
플로이드
등등
알고리즘 설계 팁
- 자바스크립트에서 1억번 연산에서 1~5초정도 걸림
- O(n^3)의 알고리즘을 설계한 경우, n의 값이 5000이 넘는다면 얼마나 걸릴까
- 코딩테스트 문제에서 시간제한은 통상 1~5초 가량이다.
- 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적이다.
요구사항에 따라 적절한 알고리즘 설계하기
-
N의 범위가 500인 경우
시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있음 -
N의 범위가 2000인 경우
시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있음 -
N의 범위가 100000인 경우
시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다. -
N의 범위가 10000000인 경우
시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
