본문으로 건너뛰기

코딩 테스트 합격자 되기 - JS

  • 독서 기간 (2024.10.28 ~ )
  • 목적 : JS 기반으로 알고리즘 공부와 더불어 코딩 테스트 준비

Intro

코딩 테스트 준비하기 전에

코딩 테스트 준비를 위한 추천 사이트 프로그래머스

  • 장점 1 : 다른 사람의 풀이를 볼 수 있음
  • 장점 2 : 테스트 케이스를 통해 풀이를 확인할 수 있고, 테스트 케이스를 추가할 수 있음

추가설명 : 타인의 풀이를 보면 다양한 풀이 방법을 알 수 있고, 테스트 케이스를 통해 풀이를 확인하면서 더욱 확실하게 이해할 수 있음

아는 것과 모르는 것을 구분하자

  1. 기록하기
    • 풀지 못한 문제가 있을 때, 어띠가지 생각해봤는지, 어떤 방법으로 풀었는지 기록
    • 풀이를 보고 나의 풀이와 비교해보기
  2. 시험 보듯 공부하기
    • 시간 제한을 두고 풀기
  3. 짧은 기간에 마스터하겠다는 생각 버리기 (최소 1~2달 현실적으로 3달)
    • 시간을 가지고 여러번 풀어보기
  4. 나만의 언어로 요약하기
    • 이해하고 나서 내가 다른 사람에게 설명할 수 있을 정도로 요약하기

자료구조와 알고리즘 그리고 코딩 테스트

  • 자료구조 : 데이터를 저장하고 조작하는 방법 (배열, 스택, 큐, 트리, 그래프)
  • 알고리즘 : 문제를 해결하는 방법 (정렬, 탐색, 그리디, 동적 프로그래밍, 백트래킹)
  • 코딩 테스트 : 자료구조와 알고리즘을 통해 문제를 해결하는 과정 (위의 두 가지를 통해 문제를 해결, 즉 구현력 평가)

1장

코딩 테스트 효율적으로 준비하기

문제 분석 연습하기

  1. 문제를 쪼개서 분석하기 (입력, 출력, 제약 사항, 예제)
  2. 제약 사항을 파악하고 테스트 케이스를 만들어보기 (예제를 통해)
  3. 입력값을 분석하기 (이를 통해 어떤 알고리즘을 사용할지 결정)
  4. 핵심 키워드 파악 (키워드에 따라 어떤 알고리즘을 사용할지 결정, ex 최적의 해 => 너비 우선 탐색)
  5. 데이터의 흐름이나 구성을 파악하라
    • 데이터의 삽입과 삭제가 빈번하다 -> heap

의사코드 작성하기

  1. 세구 구현보다는 동작 중심으로 작성
  2. 문제 해결 순서를 작성
  3. 예외 상황을 고려하여 작성

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억

4장

코딩 테스트 필수 문법