코딩 테스트 합격자 되기 - JS
- 독서 기간 (2024.10.28 ~ )
- 목적 : JS 기반으로 알고리즘 공부와 더불어 코딩 테스트 준비
Intro
코딩 테스트 준비하기 전에
코딩 테스트 준비를 위한 추천 사이트 프로그래머스
- 장점 1 : 다른 사람의 풀이를 볼 수 있음
- 장점 2 : 테스트 케이스를 통해 풀이를 확인할 수 있고, 테스트 케이스를 추가할 수 있음
추가설명 : 타인의 풀이를 보면 다양한 풀이 방법을 알 수 있고, 테스트 케이스를 통해 풀이를 확인하면서 더욱 확실하게 이해할 수 있음
아는 것과 모르는 것을 구분하자
- 기록하기
- 풀지 못한 문제가 있을 때, 어띠가지 생각해봤는지, 어떤 방법으로 풀었는지 기록
- 풀이를 보고 나의 풀이와 비교해보기
- 시험 보듯 공부하기
- 시간 제한을 두고 풀기
- 짧은 기간에 마스터하겠다는 생각 버리기 (최소 1~2달 현실적으로 3달)
- 시간을 가지고 여러번 풀어보기
- 나만의 언어로 요약하기
- 이해하고 나서 내가 다른 사람에게 설명할 수 있을 정도로 요약하기
자료구조와 알고리즘 그리고 코딩 테스트
- 자료구조 : 데이터를 저장하고 조작하는 방법 (배열, 스택, 큐, 트리, 그래프)
- 알고리즘 : 문제를 해결하는 방법 (정렬, 탐색, 그리디, 동적 프로그래밍, 백트래킹)
- 코딩 테스트 : 자료구조와 알고리즘을 통해 문제를 해결하는 과정 (위의 두 가지를 통해 문제를 해결, 즉 구현력 평가)
1장
코딩 테스트 효율적으로 준비하기
문제 분석 연습하기
- 문제를 쪼개서 분석하기 (입력, 출력, 제약 사항, 예제)
- 제약 사항을 파악하고 테스트 케이스를 만들어보기 (예제를 통해)
- 입력값을 분석하기 (이를 통해 어떤 알고리즘을 사용할지 결정)
- 핵심 키워드 파악 (키워드에 따라 어떤 알고리즘을 사용할지 결정, ex 최적의 해 => 너비 우선 탐색)
- 데이터의 흐름이나 구성을 파악하라
- 데이터의 삽입과 삭제가 빈번하다 -> heap
의사코드 작성하기
- 세구 구현보다는 동작 중심으로 작성
- 문제 해결 순서를 작성
- 예외 상황을 고려하여 작성
2장 (프로그래머스 완벽 활용 가이드 - 생략)
3장
알고리즘의 효율 분석
시간 복잡도
- 최악의 경우 시간 복잡도를 표현하는 빅오 표기법
ex: O(1), O(logN), O(N), O(NlogN), O(N^2), O(2^N), O(N!)
만약 다항함수 일 경우
- O(N^2 + 2N + 1) => O(N^2) (가장 큰 차수만 남기고 나머 지는 버림)
지수함수일 경우
- O(2^N + 3^N) => O(3^N) (가장 큰 차수만 남기고 나머지는 버림)
지수함수와 다항함수가 같이 있을 경우
- O(2^N + N^2) => O(2^N) (지수함수가 다항함수보다 더 크기 때문에)
시간 복잡도를 코딩 테스트에서 어떻게 활용할까?
- 시간 복잡도를 고려하여 알고리즘을 선택
- 제한 시간 내에 문제를 해결할 수 있는지 판단
예를 들어 데이터가 1000만개일 때
시간 복잡도 | 최대 연산 횟수 |
---|---|
O(N!) | 10 |
O(2^N) | 20 ~ 25 |
O(N^3) | 200 ~ 300 |
O(N^2) | 3000 ~ 5000 |
O(NlogN) | 100만 |
O(N) | 1000만 |
O(logN) | 10억 |