코딩테스트 기본

코딩테스트 기본

 

복잡도(Complexity)

 

• 알고리즘의 성능을 나타내는 척도로 시간복잡도와 공간복잡도가 있다
• 기능이 같다면 일반적으로 복잡도가 낮을수록 효율이 좋다

1. 시간 복잡도 : 특정 크기의 입력에 대해 알고리즘의 수행 시간 분석
2. 공간 복잡도 : 특정 크기의 입력에 대해 알고리즘의 메모리 사용량 분석

 

 

빅오 표기법(Big-O Notation)

 

O(1)	O(logN)	O(n)	O(NlogN)	O(n²)	O(n³)	O(2ⁿ)	O(n!)
상수형	로그형	선형	로그선형	2차형	3차형	지수형	팩토리얼형
효율적	↔						비효율적

 

 

알고리즘 설계

 

• 통상 연산횟수가 1억이 넘게 되면 1초가 걸림
• 코딩테스트의 시간제한은 보통 1~5초 정도로 요구사항 확인 시 시간제한이 가장 중요
• 시간제한이 1초일 때 기준

1. n의 범위가 500인 경우 O(n³)까지의 알고리즘으로 설계
2. n의 범위가 2000인 경우 O(n²)까지의 알고리즘으로 설계
3. n의 범위가 100000인 경우 O(NlogN)까지의 알고리즘으로 설계
4. n의 범위가 10000000인 경우 O(n)까지의 알고리즘으로 설계

 

 

문제 해결 과정

 

• 대부분 문제의 핵심을 파악했다면 간결하게 소스코드를 작성할 수 있음

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

 

 

자신만의 소스코드 만들기

 

• 코테를 준비하며 알고리즘 소스코드를 라이브러리화 하면 더욱 효율적인 준비 가능

 

 

숙지사항

 

1. 테스트 시 사용할 언어의 자료형
2. 언어의 기본 입출력 방식 : 빠르게 입력 받는법 포함(ex. BufferedReader)
3. 조건문/반복문/연산자

 

 

순열과 조합

 

• 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열한 경우의 수
• 순열 공식 : nPr = n! / (n-r)!
• 조합 : 서로 다른 n개에서 순서와 상관없이 서로 다른 r개를 선택하는 경우의 수
• 조합 공식 : nCr = n! / r! (n-r)!