코딩테스트 준비 Tip

코딩 테스트를 어떻게 준비해야 할까 ?

(1) 코딩테스트 난이도는 ?

코딩테스트를 어렵게 내는 기업은 4문제 중 1문제 꼴로 프로그래머스 3.5단계 수준
(주로 대기업: 카카오, 구글 등 대기업)

• (최대) 프로그래머스 기준레벨 3, 해커랭크 기준 medium 정도 !!

• (최소)프로그래머스 기준레벨 1단계를 수월하게 !!

코딩 테스트 사이트:
백준코딩: https://www.acmicpc.net/
프로그래머스: https://programmers.co.kr/
해커랭크 : https://www.hackerrank.com/
린트코드 : https://www.lintcode.com/
리트코드 : https://leetcode.com/

(2) 알고리즘을 풀때 ?

반복문 -> 재귀 -> dp - > 이런식으로 완벽하게 이해하고 공부하자!!

(단기간일 경우)
대표적인것(순열, 조합, dps, bps , dp)을 암기를 기본적으로 해야한다.

• 많은 문제를 풀고, 유형에 대비할수 있어야 한다.

• 일부 코딩테스트는 잘 알려진 유형들만 출제되고, 이 유형들을 접근할수 있는 템플릿이 존재함.

• 레버런스 코드슬 보고 해라!!

• 봐야할 유형

  • Backtracking
  • Divide and conquer
  • Graph Algorithm
    (권장)
  • Greedy, DP
  • Searching Sorting - 주어진 함수를 쓰는게 가장 좋음!

Reference code site: https://www.geeksforgeeks.org/job-sequencing-problem/ 검색에 키워드를 검색!!

(3) 시간복잡도

• 대부분의 문제는 실행 시간 : 1초에 가깝게 디자인이 된다. (보통 1억번의 연산당 1초)
  1초가 걸리는 입력의 크기 (외우자)
  • O(N) : 100,000,000
    
  • O(NlogN): 5,000,000
  • O(N^2): 10,000
    
  • O(N^3): 500
    
  • O(2^N): 26
  • O(N!): 11
• 입력의 상한이 존재하는지 항상 확인해야 한다.
• BigO(빅오)는 입력이 커질때, 값이 커지는 속도 !
  만약 입력값이 작을때는, 어떤식으로 풀어도 상관이 없다.!! 큰 차이가 없다라고 말할수 가 있다.
  BUT!!!
  입력값이 큰 경우 !! 시간복잡도가 넘어설경우에는 어떠한 알고리즘으로 풀수 있는지 알아봐야 한다.

정리 내용 : https://velog.io/@jelkov/Time-Complexity

(4) 공간복잡도

• JS에서 보통 변수 하나는 8Byte 입니다.
  알고리즘 문제에 메모리 조건이 나올 수 있습니다.
  일반적으로 128/256/512MB가 자주 등장합니다.
  • KB =1000 byte
  • MB =1000K = 100만 byte
  • GB =1000M = 10억 byte

ex) [1,2,3] = 24byte

(5) 문제를 처음 봤을때 ?

1. 입력과 공간 상한을 확인합니다.
2. 먼저, 완전탐색으로 문제를 풀어봅니다. (알고리즘이 바로 떠오르면 이렇게 푼다.)
3. 문제 푸는 시간의 30~50%는 문제를 푸는데 할애 한다.
4. 문제에 시간 배분을 잘해놓고 넘어가라 . 시간내에 막히면 넘어가라 !!

• 배열 메소드를 쓰는것 보다 반복문을 통해 풀어보는 것을 추천한다.
  (반복문 안에 메소드를 쓰면 이게 반복문인지 모를수 있다.)
• 그리고 주로 비대면이기 때문에 소수만 보는 코딩 테스트라면, 코드에 대해서 설명할 수 있어야 하고 , 그렇기 때문에 주석을 잘달아야 하고 수도코드도 잘 써놓는것도 좋다 !
  코딩테스트에서 본 코드는 잘 기억해 놓고 있는것이 좋다.

(6) 기본적으로 알아두어야 할 유형은 무엇일까 ?

이해해야 하고 , 외워야 하고, 코딩테스트 직전에 보고 가야한다.

1. GCD (최대공약수, 최소공배수)
2. 순열/조합
3. 정렬은 Array.prototype.sort 사용
4. DFS (재귀) BFS(큐)
5. 분할정복(재귀), DP => 감을 잡기 어렵기 때문에 케이스 스터디 필요 !!