코딩테스트 (알고리즘) 준비하기(알고리즘 종류, 방법)

https://mungto.tistory.com/514

2021년 회고(2년 6개월이라는 취준생활을 마무리하며... )(준비, 스펙, 의견)

https://mungto.tistory.com/515

취업을 준비하는 사람들에게... (개인적 의견)

https://mungto.tistory.com/517

CS와 면접 준비하기

 

코딩테스트 공략

목적 : 코딩테스트 준비를 하는 사람들에게 주로 나오는 알고리즘에 대한 키워드를 제공하기 위해 작성한다.

알고리즘에 대한 설명은 부족할 수 있으니 따로 찾아서 공부를 해야한다.

---

해야함

dfs : 깊이우선탐색으로 완전탐색을 할때 사용한다.

백트래킹 : dfs에서 더이상 정답이 아니라고 판단되는 부분은 탐색하지 않도록 가지를 치며 탐색하는 방법

bfs : 너비우선탐색으로 완전탐색이나 최단경로를 찾을때 유리

투포인터 : 특정 구간에서 작업을 할때 효율적

누적합 : 구간합을 빠르게 구하기 위한 방법

에라토스테네스의체 : 특정 범위에서 소수판별을 빠르게 할 수 있음

이분탐색 : 시간복잡도를 볼때 n보다 짧게 처리가 되야할때 사용, 정답을 두고 탐색범위를 반절씩 버리면서 탐색

구현 및 시뮬레이션 문제 : 요구사항 구현, 문자열 관련 문제 등

유클리드호제법 : 최대공약수, 최소공배수 구하기

큐, 스택, 힙, 디큐, 해시를 이용한 문제풀이

---

가끔나와서 준비는 해야함

다익스트라 : 한 출발점에서 모든 다른지점까지의 최단거리

플로이드와샬 : 모든 지점간의 최단거리를 찾을때 사용

유니온파인드 : 같은 부모에 속한 그래프인지 체크하기 위해 사용

크루스칼 : 최소신장트리를 만들때 사용, 엣지를 정렬하여 연결

프림 : 최소신장 트리를 만들때 사용, 노드를 선택 후 가장 적은 비용을 가진 엣지를 연결

LCS : 최장 공통 부분 수열

LIS : 최장 증가 수열

진법변환 : 2진법, 8진법, 16진법 등

---

하면 좋지만 안해도 지장없음

트라이 : 빠른 문자열 검색에 사용

라빈카프, KMP, 보이어-무어 : 문자열 검색 알고리즘

위상정렬 : 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것

---

ETC

비트마스킹

DP

그리디

세그먼트트리

---

공부방법

알고리즘만 죽어라 팔것이 아니라면 아마 목표는 기업코딩테스트를 통과할 정도일 것이다.

네카라쿠배급을 가고싶다면 프로그래머스 기준으로 3레벨까지는 풀 수 있어야한다.

대기업 SI(SK C&C, LG CNS, 삼성 SDS, 롯데정보통신, 신세계 I&C, 한화시스템/ICT, 현대오토에버 등) 이라면 프로그래머스 기준 2레벨을 풀 수 있다면 가능하다고 생각한다. 가끔 어려운 문제가 나온다면 3레벨급이다.

 

처음에는 프로그래머스 1레벨 문제를 풀면서 알고리즘을 푸는 언어에 익숙해지자.

문법도 익히지 못한상태로 알고리즘 풀려고하면 어렵다.

1레벨 문제를 다 풀었다면 이때부터 어려워진다.

프로그래머스 고득점 Kit을 풀면서 다른 자료(유튜브, 블로그 등)와 함께 알고리즘과 문제풀이를 병행한다.

이렇게 2레벨 문제까지 다 풀었다면 3레벨은 어떻게 진행해야 할지 감이 올 것이다.

여기에 추가적으로 제한사항으로 주어진 입력을 보고 시간복잡도를 유추해서 풀이가능한 알고리즘 폭을 줄이는 연습을 하자.

문제양이 부족하다고 생각된다면 백준에서 solved.ac를 이용하거나 알고리즘별 문제를 풀어보자.

 

문제를 풀면 다른사람 풀이를 볼 수 있는데 다 풀었다고 넘어가지 말고 다른사람 풀이를 확인하자.

내가 생각지도 못했던 풀이방법이 나올 수 있다.

 

문제풀이는 123이라는 법칙으로 시간을 조절하면 좋겠다.

3 - 30분동안 손도 못댔다면 해당문제를 풀 준비가 안돼있는 것이다. 추가적인 공부를 하거나 다른사람 풀이를 보자.

1 - 1시간동안 풀었는데 효율성이 안나온다면 다른 알고리즘이나 자료구조 적용을 고려해보자. 생각이 나지 않는다면 다른사람 풀이를 보자.

2 - 2시간동안 엣지케이스를 못찾았다면 다시풀거나 다른사람 풀이를 보자.

 

다른사람의 풀이를 보고 풀었다면 1주일 뒤에 해당 문제를 다시 풀면 좋겠다.

 

우리는 알고리즘 말고도 프로젝트도 해야하고 CS공부도 해야한다. 코딩테스트를 통과해야 뒤에가 의미있지만 코딩테스트만 통과하면 의미가 없다. 자격증도 100점으로통과하나 60점으로 통과하나 80점으로 통과하나 합격이다. 너무 알고리즘에만 매몰되지 말고 시간을 최대한 아껴서 프로젝트, CS(컴퓨터 사이언스)도 같이 준비하자.

---

참고자료

나동빈 유튜브

실전 알고리즘 강좌 (Algorithm Programming Tutorial)

알고리즘 문제풀이 오픈 카톡방

[백준, 프로그래머스]알고리즘 입문방

---

알고리즘 풀이 사이트

일반적인 기업 코테라면

백준

Baekjoon Online Judge

프로그래머스

프로그래머스

---

삼성을 노리고 있다면

SWEA

SW Expert Academy

---

해외기업을 노린다면

코드포스

Codeforces

해커랭크

HackerRank

릿코드

LeetCode - The World's Leading Online Programming Learning Platform