취업을 위한 코딩 테스트 공부법에 대해서 알아봤다.
정리해두고 이 순서에 따라 진행해야겠다.
(참고 : https://qkqhxla1.tistory.com/990)

🎓코딩 테스트 공부 방법

1. 기초적인 프로그래밍 공부 💻

📘 첫 번째로, 언어에 대한 기본서 한 권을 읽으며 기본적인 프로그래밍 틀 잡기

👉🏻 프론트엔드를 희망하기에 js 지만 코딩 테스트는 익숙한 언어를 사용하는 게 맞다고 생각해 파이썬으로 준비하려고 한다.

2. 기본적인 프로그래밍, 자료구조, 기초 알고리즘 공부 📖

📘 자료구조와 책 한 권 사서 정독하고 본인의 언어로 개념을 알 때까지 구현하기

알고리즘의 가장 인기 있는 부분이 정렬이며, 한번 정리해두고 시간 복잡도 등은 면접 전에 한 번 더 보기
요즘 알고리즘 시험에는 정렬이 잘 안 나옴. 하지만 면접 때 나올 수 있으니 그전에 한 번 더 보기

📘 시간 복잡도와 공간 복잡도에 대해 잘 알아두기.

특히 시간 복잡도의 경우에는 대부분 면접에서 손 코딩할 경우에 물어봄.
예시 : 이 코드는 시간 복잡도가 어떻게 될까요? O(n^2)의 복잡도인데 복잡도가 너무 큰데 좀 줄이는 방법은 없을까요? 등으로 물어보므로 앞으로 알고리즘 문제를 풀면서 시간 복잡도와 공간 복잡도를 한 번씩 계산해 보기

일반적으로 자주 사용하는 것들 중 몇 개를 적으면 반복문이 한 번이면 O(n), 중첩 반복문이면 O(n^2), 이분 탐색의 시간 복잡도는 O(logn), 언어에 있는 정렬을 사용하면 O(nlogn) 등

📘 이제 이 정도 했으면 백준 사이트 입문할 준비 완료. 백준의 UI도 익숙해질 겸 https://www.acmicpc.net/step 에 있는 기본적인 문제들을 풀어보기.

처음 들어보는 개념들의 문제(동적 계획법, 백트래킹, 네트워크 플로우 등)와 어려워 보이는 것들은 풀지 말고 기본적인 큐 사용하기. 문자열 사용하기. 이런 들어본 것, 공부해 본 것, 정답 비율 높은 것들만 (최소 50~60% 이상)으로 풀어보기
이 정도 난이도부터가 피보나치수열을 재귀함수로 구현하기 시작하는 정도
👉🏻 현재 이 단계 진행 중 😝

'큐 사용하기' 이런 종류의 문제는 자료구조 구현보다도 공부했던 자료구조 복습과 내가 몰랐던 언어 내의 라이브러리를 검색함으로써, 기본적인 검색 능력도 길러짐

3. 기본기 응용, 알고리즘 공부 시작 ⌨️

기본적인 자료구조, 알고리즘을 구현할 수 있으며, 필요에 따라 바꿔서 쓸 수 있음
대부분 2, 3단계부터 면접에서 손 코딩으로 구현해야 하는 정도의 난이도, 3단계 정도부터가 일반적인 기업에서 하는 온라인 알고리즘 '테스트' 난이도

📘 백준에 들어가서 문제집 카테고리 -> 공개 카테고리 -> 끝 페이지 가서 쉬워 보이는 카테고리 풀기

쉬운 문제들이라서 2번 단계와 중복될 수 있지만, 수학 지식이 섞여있는 게 있어서 단순한 구현의 문제인 2번보다는 생각을 더 해야 함 (예시 : https://www.acmicpc.net/problem/1085)

3단계는, 2단계까지의 기본 알고리즘이나 자료구조 등을 활용한 문제, (구현이 아니라 활용한 문제) 프로그래밍 + 수학 지식이 섞인 단계의 난이도

📘 이 정도도 난이도부터가 프로그램을 효율적으로 돌게하기 위한한 로직을 조금씩 생각하기 시작하는 진정한 알고리즘 공부 입문

이 단계부터 단순히 머리로 생각한 것을 프로그래밍으로 별생각 없이 옮기는 게 아닌 추가적으로 생각을 해야 함 (예시 : 1~n까지의 합이라고 하면 단순히 반복문을 돌려가며 다 더하는 게 아닌 n(n+1)/2라는 공식을 써서 효율적으로 만드는 정도, 탐색을 위해서 hashmap 자료구조가 빠르다는 것을 알고 활용하기 시작하는 정도, 피보나치수열을 반복문으로 구현하는 정도)

4. 취업대비 알고리즘 공부 시작 🖱️

여기서부터 난이도가 대폭 상승
난이도를 1~10으로 잡으면 3단계까지는 2,3 정도면 4단계부터는 7,8 정도로 올라감
중견기업 이상 준비하시는 분이면 이 난이도까지는 오는 게 좋고, 이 단계도 할만하다 싶으시면 상위 it 기업 (네이버, 카카오 등)도 가능

📘 대상자 : 코딩테스트용 알고리즘 중급 난이도 시작자.

자료구조를 구현 할 줄 알고, 기본적인 함수들과 다른 자료구조 지식들을 섞어서 프로그램을 자유롭게 만들 수 있는 정도, 시간 복잡도로 효율성을 알며 어떤 경우에 어떤 자료구조를 써야 하는지 아는 정도. 중견, 대기업을 노리며 코딩 테스트 공부에 익숙해지려는 사람.

📘 취업용 알고리즘 책을 사기

'종만북'이라고 불리는 알고리즘 문제 해결 전략 책 추천
챕터 1 읽고, 가볍게 구현해 보기 (예시 : 챕터 7이 분할 정복이면 방법론 등을 이해하고 구현 후 백준 사이트 분할 정복 문제 풀 수 있는 만큼 풀기)

알고리즘 공부 시 본인이 깊게 오랫동안 생각해보는 것도 중요하지만, 초중반에는 코딩 자체를 어떻게 해야 할지 모르는 경우가 많으므로 문제와 답을 보고 이해하면서 머릿속으로 해당 문제의 템플릿을 만드는 게 좋음
다만 어느 정도가 지나면 이 알고리즘에 대해 스스로 코드를 짤 줄 알아야 함

📘 모든 분류를 한 바퀴 순회

종만북에 없는 알고리즘은 네이버나 구글에서 이론을 찾아서 한 번씩 읽어보고 풀기
시간이 많이 부족하면 비주류 알고리즘은 안 푸는 게 효율적
종만북 공부는 알고리즘 공부를 하기 위한 틀을 잡아주는 것

📘 주류와 비주류 구분

👉🏻 주류는 트리, 구현, 다이나믹 프로그래밍, bfs dfs, 백트래킹과 같은 탐색 등
👉🏻 비 주류는 suffix automaton, 아호코라식 등의 알고리즘, 수학과 관련된 것 등
주류 알고리즘을 많이 풀어보는 게 좋음

주류 유형을 알려면 최근 n 년 이내의 코테를 찾아보면서 미리 유형을 익혀두기
카카오 등을 통해 찾아보며, 효율적인 공부를 위해 유형을 파악 중요

특히 구현 종류와 다이나믹 프로그래밍(통칭 DP)을 많이 풀어보기
코테에서 주로 나오는 알고리즘들 대부분은 몇 문제만 풀면 개념적으로 이해하기 쉬운데, (특히 bfs dfs같은건 한번 이해하면 활용하기도 쉬움) dp의 경우 같은 dp라도 종류가 너무 많아서 많이 풀어보기 (다이나믹 프로그래밍이라는 큰 틀 안에도 또 다른 이름의 알고리즘이 많이 있음)

5. 기타 🎸

📘 푼 문제의 질이 괜찮고, 잘 이해했으면 백준 400문제 정도만 풀어도 괜찮음

하지만 활용 문제 연습을 위해 많이 풀면 풀수록 좋음
네이버, 카카오 합격자들도 꼭 백준이 아니더라도 평균적으로는 300~400 문제 정도는 품

📘 ~ 3단계까지의 알고리즘은 풀이법을 알면 혼자서 짤 수 있지만, 4단계의 일부 알고리즘부터는 이론도 복잡해서 혼자서 짜기가 힘든 경우, 이미 있는 코드를 가져와서 변형하는 방식으로 문제를 풀기

하지만 그냥 갖다 쓰라는 게 아니라 나중에 짤 줄 알아야 함
dp 정도는 유형이 워낙 다양해서 웬만해서는 혼자서 짤 줄 알아야 함
공부하다 보면 복잡한 것들이 나오는데 스스로 판별해서 일정 수준 이상이면 이미 있는 거 쓰기

📘 온라인 코딩과 손코딩

집에서 보는 온라인 코딩, 면접 보면서 하는 손 코딩 두 가지 존재

👉🏻 온라인 코딩
문제가 아무리 어려워도 이미 풀어봤었으면 가져다가 응용하면 됨 (하지만 면접 질문 대비해야 함)
대부분 기업들이 cheating을 감안하므로 코딩 테스트는 온라인으로 끝이 아니라 알고리즘 공부 안 해본 사람들 거르기용

👉🏻 오프라인 코딩
그렇게 복잡한 문제를 손 코딩하거나 인터넷, ide 없이 풀어보라고 잘 요구하지 않음
면접 가서 보는 손 코딩은 ~3단계 또는 ~4단계의 극 초반 정도
많이 어려운 문제 꼭 혼자서 해보겠다고 계속 시간 낭비할 필요가 없음
유형만 파악

📘 참고

알고리즘 문제를 풀 때에 문제를 읽고 '최단 길 찾기인 다익스트라로 모델링 해서 풀면 되겠다' 라고 방법론이 떠오르면 50%는 푼 것
어려운 문제의 기준은 코딩 테스트나 면접을 보며 감을 잡는 게 좋음
(이 기준도 해마다 조금씩 바뀜. 예시 : 언제는 잘 안 풀어봤던 투 포인터 문제가 나올때도 있고 구현이 좀 어렵게 나올 때도 있음)

그래프 알고리즘 중 이론 중 네트워크 플로우나 kmp 같은 문자열 처리 등 난이도 있는 문제들은 유형만 알아두는 게 좋고 아무리 난이도가 올라가도 dp나 이진 트리, 탐색, 스택, 큐, 기본적인 문자열 처리 등을 사용한 기본적인 문제 등은 스스로 처음부터 다 짤 줄 알아야 함

6. 더 효율적 🐰

📘 처음에 카테고리 관련된 문제를 풀면서 개념을 잡을 때는 백준으로 풀고, 알고리즘 문제풀이 자체에 익숙해졌다 싶으면 leetcode로 풀기

leetcode로 풀다가 이해 안 가는 카테고리만 백준에서 찾아서 푸는 게 가장 좋음
leetcode의 easy와 medium을 다 푸는 것도 괜찮음
(특히 medium이 괜찮고, 공채 신입 준비면 hard까지)

👉🏻 각 사이트의 장점만 사용
적중률 높은 leetcode를 풀다가, leetcode에서 카테고리의 문제가 좀 이해가 안되는 문제가 많으면, 백준에서 그 문제들만 모아서 풀어보는 방식

📘 leetcode 공부 방법

1. https://leetcode.com/explore/learn/ 여기서 기본적인 카테고리별 문제들을 풀면서 leetcode의 스타일을 익히기

2. 스타일이 어느 정도 파악되었으면 https://leetcode.com/problemset/algorithms/ 에서 top 100 liked questions들로 정렬해서 풀고, 그 후 top interview questions를 풀기

3. '좋아요'가 많은 문제 풀기

(참고 문제 풀이 : https://qkqhxla1.tistory.com/category/algorithm/problem%20solving
https://blog.naver.com/paula23/223437112326)