[Algorithm] 알고리즘 공부 순서 & Tip | 대기업 코딩테스트 빈출 유형

1. 개요

신입 개발자로 취업하기 위해서는 코딩테스트는 거의 필수인 듯하다. 
처음 시작할 때 백준 티어 기준 브론즈 5에서 현재 골드 1까지 올라오고 나서 회고 겸 처음 시작할 때 뭐부터 어떻게 해야 할지 정말 모르겠는 알고리즘 공부에 대해서 정리해 볼 것이다.

이 글은 지극히 주관적인 기준이며 알고리즘 및 코테 공부를 하는데 하나의 작은 기준?으로만 생각하고 각자 자신에게 맞는 공부법을 찾길 바란다.

2. 알고리즘 공부 방법

1. 약 30분 ~ 1시간 정도 시간을 정해놓고 그 시간을 넘겨도 못 풀면 구글링으로 다른 사람이 푼 코드를 보고 공부한다.
2. 풀이를 보고 복붙 하지 말고 이해하고 찾아보며 직접 따라 쳐본다. 백문이 불여일타 > 그냥 복붙 하면 살 뺀다고 하고 운동 유튜브 보고 운동했다고 하는 거랑 같다.
3. 처음 본 알고리즘이면 구글링으로 알고리즘에 대한 개념을 찾아본 후 공부하고 다시 풀어본다. 이후 공부한 알고리즘을 활용해야 풀 수 있는 문제를 백준에서 찾아서 3문제 이상 풀어본다.
4. 정 모르는 풀이면 2 ~ 3번 정도 읽고 넘긴 후 1주일 뒤 다시 풀어본다.
5. 문제를 풀었으면 다른 사람의 코드를 참고하고 좋은 풀이가 있으면 또한 공부한다.

---

3. 코딩테스트에 많이 나오는 알고리즘

본인은 대기업 코딩 테스트 합격을 목표로 두고  공부하고 있기 때문에 내 기준에 맞춰 설명할 것이다.
아래는 주로 경험상? 많이 나오는 알고리즘을 써놨으며 이외에도 엄청 많은 알고리즘이 있기 때문에 직접 찾아보고 필요성에 따라 공부하는 게 좋다.

---

★ : 중요도

많이 나오는 거

구현 ★★★★

• 그냥 실수 안 하면 됨. 근데 그게 힘듦. 양치기로 경험 쌓는 방법 밖에 없음

그래프 ★★★★

• BFS, DFS
• 백트래킹
• 다익스트라

목적지와 출발지를 거꾸로 보는 발상도 필요할 수도? 항상 시간 복잡도를 생각할 것. 프로그래머스 같은 곳에는 다익의 효율성도 따짐. O(ElogV)

• 트리 전위, 중위, 후위 순회. 보고 가는 것도 괜찮을 듯.

완전탐색 ★★★★★

조합, 순열문제 자주 풀어보면 감이 옴. DFS 랑 짝꿍
ex) boj 테트로미노

탐욕법/Greedy ★★★★

문제의 시간복잡도 체크를 하고 완탐으로 풀기에는 무겁고 DP로 풀기에는 가벼울 때 접근해야 함.
근데 그리디로 풀 수 있는 문제는 DP로 해결 가능함. (대부분의 경우)

접근법
우선순위 큐, 스택등의 자료구조를 사용하는 방안으로 접근. 거꾸로 접근하면 풀리는 문제들이 있음.
일단 손으로 풀어보고 알고리즘이 완전하게 짜이면 그때 구현.
이거 안 하면 그리디에서 5시간 버림.

해시 응용★★★★★

이건 뭐 할 말이 없음

문자열 ★★★★★

c++로 풀면 불리하기는 함. 문자열 문제 나오면 파이썬으로 하는 게 정신건강에 좋음.

적당히 나오는 거

이분탐색 ★★★

중간 때리고 오른쪽으로 갈지 왼쪽으로 갈지 자기만의 방식을 정해야 됨. 그때그때 달라지면 디버깅하는데 5시간 씀.

동적계획법 ★★★

부분 문제가 어떻게 쪼개지는지.
기저 조건이 어떻게 성립하는지.
경우의 수는 다 더하기, 최댓값, 최솟값은 ret 변수에 max 또는 min.
dp 테이블 초기화 잘할 것. 무지성 -1 하다가 큰코다침.
dp 테이블 반환값. 수 범위 잘 체크. long long 써야 될 수도. 물론 dfs 할 때 함수 리턴 값도 long long.

비트 마스킹★★

익숙해지면 나쁘지 않음. 근데 잘 안 나와서 카카오 들어가고 싶으면 공부해놓는 게 좋음
연계 유형으로 비트 필드를 이용한 동적계획법 나옴.
dp 테이블을 비트로 만든 거임.

슬라이딩 윈도우 & 투포인터 ★★

O(N^2)으로 할 때 터지면 이거로 해보는 것도 괜찮을 듯. 시간복잡도는 O(N)

누적합 ★★

배열 범위 안에 있는 모든 수의 합을 O(1) 만에 구할 수 있음. 합을 계속해서 구하는 경우 쓰면 괜찮을 듯. 단 배열 내부의 값이 변동되면 안 됨.
변동될 때는 세그트리로 합을 O(logN) 만에 구할 수 있음.

거의 안 나오는 거

에라토스테네스의 체

소수 문제 풀 때 사용. 거의 안 나오지만 알면 시간복잡도 녹이는데 좋음

---

4. 기타

알고리즘 풀이용 언어 정하기

자신이 코딩 테스트를 볼 때 사용할 언어를 정하는 것 또한 중요한 것 같다.
나는 처음에 C++로 코딩을 배워서 가장 익숙했기 때문에 C++로 알고리즘을 풀이하고 있다.
다른 후기를 보면 자바 스프링을 사용하는 기업에서는 코딩 테스트 언어를 Java로 제한하는 경우도 있다고 하고(우아한 형제들, 우테코) C++로 풀이를 한다고 해도 나중에 면접에서 해당 기업이 주로 사용하는 언어로 재 풀이를 요청하는 경우도 있다고 한다.

가장 추천하는 언어 : C++, Java, Python 
3개 언어 중 하나를 정해서 공부하면 좋을 것 같다.

알고리즘 공부 사이트

백준 : https://www.acmicpc.net/
프로그래머스 : https://programmers.co.kr/
코드업 : https://codeup.kr/index.php
리트코드 : https://leetcode.com/
코드포스 : https://codeforces.com/
알고스팟 : https://algospot.com/judge/problem/list/

 
책 추천

종만북 - 알고리즘 문제 해결 전략 : https://book.algospot.com/

알고리즘 문제 해결 전략

 - 책 내용 자체가 어렵고 가격도 비싸지만 가격 값 하는 책.

- 알고리즘을 처음 공부 시작한 사람이 봤을 땐 이게 뭔소린가 하지만 어느정도 공부한 후에는 기본적인 템플릿을 정할 수 있고 문제 푸는 방향을 설정하는데 도움을 주는 책.

 

- C++언어로 설명되어 있음