코딩테스트 개요

# 문제에 따른 분류 

1. 알고리즘 코딩테스트 - 문제별 능력을 평가

 - 보통 5시간 내에 알고리즘 문제를 푼다.

 - 알고리즘을 이용해 문제를 해결할 수 있는 능력을 평가한다. 

 

2. 개발 과제 코딩테스트 - 실질적인 개발 능력을 평가 

 - 하나의 프로그램을 완성시키는 것을 시험한다. 

 - 시간단위에서 2주까지 보통 시간을 준다. 

 - 그 회사에서 실제로 사용하는 컴퓨터 언어나 프레임워크를 사용하도록 요구하기도 한다. 

 

https://replit.com/ 웹사이트에서 코딩테스트를 위한 개발환경을 사용할 수 있다. - javascript를 연습할려면 기본적으로 node js를 골라주면 된다. 

 

 

# 시험 환경으로 분류

1. 온라인 코딩테스트

 - 문제를 보고 정답을 작성하면된다. 

 - 공채에서는 혼자 힘으로 풀게 표절 검사를 진행한다. 

 - 인터넷 검색은 가능하지만 단순하게 검색으로는 해결을 하기 힘든 문제를 출제한다. 

 

2. 오프라인 코딩테스트

 - 직접 시험장으로 가서 본다. 

 - 회사마다 인터넷 검색 가능 여부가 다르다. 

 - 대체로 제공되는 컴퓨터로 시험을 치뤄야한다. 

 

 

자신만의 소스코드를 관리하는게 좋다. 

 - 자신의 코드 템플릿을 만드는 거다. 

 - 대표적인 알고리즘(정렬, 최단 경로 등)의 기본형의 코드를 미리 준비해놓는다. 

 예) https://github.com/ndb796/Python-Competitive-Programming-Team-Notes

 

 

# 최신 출제경향

 - 대부분의 대기업은 공채에서 알고리즘 코딩테스트를 본다. 

 - 2~5시간내에 주어진 알고리즘 문제들을 해결해야한다. 

 - 구현, DFS/BFS(탐색), 탐욕 알고리즘 유형이 출제 빈도가 높은 편이다. 

 

# 준비방법

 - 일단 준비할 언어의 문법을 공부

 - 알고리즘 유형별로 이론 및 핵심 문제를 10개 이상 풀어본다. 

 - 대표적인 알고리즘 유형: 정렬, DFS/BFS, 구현, 완전 탐색, 탐욕 알고리즘 

 - 가고싶은 회사의 기출 문제 풀어보기 

 

 

# 기본적인 이론

# 시간복잡도 

  - 알고리즘의 성능을 나타내는 척도다. 

  - 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

  - 동일한 기능을 수행하는 알고리즘이 있으면 보통 복잡도가 낮을수록 좋다. 

일정한 크기로 보여지는데. 

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

 - 함수의 상한을 나타낸다. 

 - 연산횟수가 3N^3 + 5N^2 + 1000000인 알고리즘이 있다고하면 N이 증가할수록 3N^3을 제외한 다른 항의 영향력은 작아진다. 차수가 가장 큰 항에서 계수를 제외하여 0(N^3)으로 표현이된다. 

 

아래에서 위로 올라갈수록 속도가 빨라진다. (성능이 좋아진다.)

시간 복잡도	의미
O(1)	상수 시간(constant time) - 단순하게 사칙연산 수행
O(logN)	로그 시간(log time) - 알고리즘이 무엇을 반으로 쪼갤때 사용 (ex. 이분탐색)
O(N)	선형 시간(linear time) - 배열 안을 하나씩 확인할때 사용
O(NlogN)	로그 선형 시간(log-linear time) - 일반적인 정렬알고리즘(병합정렬, 퀵정렬)
O(N^2)	이차 시간(quadratic time) - 동적개입법에서 넥센문제 등?
O(N^3)	삼차 시간(cubic time) - 플루이드 머신업 등?
O(2^N)	지수 시간(exponential time)

일반적으로는 로그 시간정도만 기억하면 좋다. 

 

 

# 알고리즘 설계

 - 보통 문제에서 시간제한은 5초정도이다. 

 - 문제를보면 가장 먼저 시간제한(수행 시간 요구사항)을 확인해야한다. 

 예로 시간 제한이 1초인 문제라면

N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 해결할 수 있다. 

N의 범위가 2000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀수있다. 

N의 범위가 100000이라면: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 풀 수 있다. 

N의 범위가 10000000이라면: 시간 복잡도가 O(N)인 알고리즘을 설계하면 풀 수 있다.

 

# 자료구조

대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미

 

- 대표적인 자료구조들

배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등

 

# 알고리즘 

 어떤 문제를 풀기 위한 절차/방법