코딩 테스트 이해하기

코딩 테스트 종류

• Implementation : 제시된 흐름에 따라 실행하는 코드를 만들도록 요구
• Algorithm comprehension : 문제의 효과적/효율적 해법을 찾아내도록 요구
• Competency test : 특정한 자료구조와 알고리즘을 착안하여 제한시간 내에 풀도록 요구
• etc : 특정한 언어 구문을 활용할 수 있는지를 테스트 (SQL)

---

어떤 대비가 필요할까?

• 구현 능력 갖추기 : 아주 당연한 얘기지만 그만큼 필수적이기도 하다. 적어도 하나의 프로그래밍 언어에 능숙해져야한다.
• 기본적인 자료구조 이해 : Array, Stack/Queue, Hash, Tree, Graph,... 등등 여러 자료구조 익숙해지기
• 기초 알고리즘 및 시간/공간 복잡도에 대한 이해 : 문제를 읽고 어떤 접근방법을 택할지 선정하는것이 굉장히 중요하다
  이때, 선택한 알고리즘이 문제의 제한사항을 충족시킬 수 있는 시간복잡도를 갖는지 생각해보아야 한다.
• 현실 문제를 해결하기 위한 알고리즘 적용 해법 착안 사고 훈련 : 추상적인 문제가 아닌 정말 현실상에 적용하기 위해선 어떤 해결방법을 적용할 수 있는지에 대한 사고 능력도 필요하다.
• 제한 시간 내에 오류 없이 코드 작성 및 디버깅할 수 있는 능력 훈련 : 연습만이 해결가능한 영역!

즉, 문제의 본질을 이해하고 이것에 대해 정보의 처리로 접근할 수 있도록 핵심을 추려내는 능력과, 해법을 구현해낼 수 있는 자료구조와 알고리즘에 대한 충분한 이해력, 마지막으로는 제한시간 내에 코드를 구현해낼 수 있는 능력이 필요한 것이다.

---

코딩 테스트에 나오는 알고리즘 유형

해시 테이블

• key-value 쌍으로 저장되는 특성에 따라 자주 사용되는 자료구조 유형이다.
• 파이썬으로 코테를 준비한다면 딕셔너리라는 아주 좋은 자료형을 사용할 수 있으니 아주 짱짱일 것이다.

 

스택 & 큐

• 많이 사용되긴 하지만 단독으로 사용되는 경우보다 구현하는데 필요한 자료구조 정도로 사용되는 경우가 많다. 예) 스택 : DFS, 큐 : BFS
• 스택은 오로지 최상단 원소를 접근하는 경우에만 사용된다.
• 문제에서 선입선출, 후입선출의 단서가 보이면 사용하자
• c++에서는 stack와 queue를 include해서 사용하지만, 파이썬에서는 주로 list를 활용하여 구현한다.

 

 힙

• 우선순위를 고려하는 문제에서 사용된다. 예) 작은 수부터, 큰 수부터
• 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 

 

구현

• 주어진 문제를 알고리즘을 통하여 코드로 바꾸는 것이다.
• 머리로 구상한 과정을 코드로 옮기는 능력이 중요하다.
• 주로 어렵지는 않지만, 복잡한 구현이 나올 때가 많다.

 

브루트 포스(완전탐색)

• 코딩테스트 필수 of 필수일 만큼 자주 출제되는 유형으로 완탐이라고 줄여 부르기도 한다.
• DFS, BFS, 백트래킹(완탐은 아니긴 하다)이 이에 속한다.
• 이름 그대로 모든 경우를 탐색해야 할 경우에 사용된다. (미로찾기 등)
• 무작정 모든 경우를 탐색하면 효율이 낮으므로, 시간 제한에서 실패하면 다른 풀이를 생각해보거나 문제 조건에 따라 탐색을 최소한으로 만들어야 한다.

 

 다이나믹 프로그래밍(DP)

• 복잡한 문제를 한 번에 해결하는 것이 아닌, 조금씩 점차적으로 풀이하는 유형이다. 
• 점화식만 잘 생각해내면 구현자체에는 그렇게 큰 어려움이 없다.
• 대신 이 점화식 생각해내기가 상당히 어렵다..
• bottom-up, top-down 방식으로 생각을 해나가는 것이 좀 수월하다.

 

그리디

• 부분적인 최적해가 전체적인 최적해가 되는 문제에서 사용한다.
• 즉 그리디를 사용하는 문제가 아닌데 그리디를 써버리면 최적해를 찾을 수 없다는 뜻이다.
• 정렬, 우선순위 큐를 활용하는 경우가 많다.

 

이분 탐색

• 순차적인 배열 탐색으로는 시간 초과가 나는 문제에서 사용한다.
• 시간 복잡도 : O(logN)로 그냥 순회하는 O(N)보다 빠르다.
• 이분 탐색 + 다익스트라 등 다른 유형과 연계되는 문제가 출제될 수 있다.

 

그래프

• 최단 경로를 구하는 문제가 많이 출제된다.
• 최단 경로를 구할 때는 다익스트라, 벨만-포드, BFS, 플로이드-워셜 알고리즘들을 사용하자.
• 그래프 순회에는 DFS / BFS를 사용하자.
• 추가로 학습하면 좋은 알고리즘으로는 위상정렬이 있다.

 

유니온 파인드

• 최근 자주 기출되는 유형이다.
• 노드를 집합에 속하게 하는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.
• 노드들을 루트 노드를 기준으로 하는 어떠한 집합으로 묶는다고 생각하면 이해하기 편하다.

 

비트마스킹

• 문제에서 0, 1로 표현할 수 있는 경우 비트마스크를 사용하여 효율적으로 풀이할 수 있다.
• 비트마스크를 사용하면 수행시간, 메모리에서 이점을 가진다.
• 비트 연산자를 사용하므로 AND, OR, XOR, NOT, Shift 를 공부하자.