코딩테스트 사전 준비
- 프로그래머스 활용
- 다른 사람의 풀이 보기
- 테스트 케이스 직접 추가
- 충분한 시간을 들여 문제를 분석한 후, 코드 구현하기 전에 예외 상황을 충분히 확인할 수 있도록 나만의 테스트 케이스 만드는 연습을 해야함
- 공부 습관
- 기록하기!
- 문제를 보면 어떤 알고리즘을 적용하려 했는지, 근거는 무엇인지, 문제를 푸는 과정에서 내가 떠올린 알고리즘을 어떻게 코드로 만들려 했는지 등
- 전 기록을 보면서 복기
- 이 과정에서 무엇을 모르는지 알 수 있게 됨
- 시험 보듯 공부하기
- 평소에 시간 배분하면서 코딩 테스트 공부하기
- 시간 배분 연습 안함/함 차이가 나중에 결과가 많이 다를 것임
- 2-3개월은 걸릴거임
- 무조건 짧은 시간 내에 할 수 없음, 꾸준히 해야함
- 나만의 언어로 요약
- 내가 정말로 이해하고 있는지 알아보기 위해서
- 기록하기!
- 코딩테스트 효율적으로 공부하기
- 언어 선택 - 자바 (자바 공부 동행하기)
- 문제 분석 연습하기
- 문제를 쪼개서 분석
- 제약사항을 파악하고 테스트 케이스 추가
- 입력값 분석
- 보통 알고리즘 시간 복잡도는 입력값이 결정하는 경우가 많음
- 입력값의 크기를 확인하면 문제를 제한시간 내에 풀 수 있는 알고리즘과 그렇지 않은 알고리즘을 미리 걸러낼 수 있음!
- 그리디하게 접근할 때는 근거를 명확하게
- 데이터 흐름이나 구성을 파악
- Pseudocode (의사 코드)
- 세부 구현 X, 동작 O
- 문제 해결 순서 적기
- 테스트하기
알고리즘의 효율 분석
- 코딩테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용할 때 제한 시간 내에 출력값이 나올 수 있을 지 확인할 수 있음
| 시간 복잡도 | N의 가용 범위 |
| O(N!) | 10 |
| O(2^N) | 20~25 |
| O(N^3) | 200 - 300 |
| O(N^2) | 3,000 - 5,000 |
| O(N log N) | 100만 |
| O(N) | 1,000 - 2,000만 |
| O(logn) | 10억 이상 |
- 예를 들면, 처음부터 끝자기 배열을 순회해서 숫자를 찾는 알고리즘은 O(N)이다.
- O(N)이 허용하는 연산 횟수는 2,000만으로 데이터의 개수가 2,000만 이하면 이 알고리즘은 사용해도 괜찮다!
- 이렇게 시간 복잡도를 활용하여 불필요한 알고리즘을 제외하면 된다