코딩테스트 문제 유형

 

코딩테스트는 시간 제한(효율성)이 존재하기 때문에 시간복잡도가 매우 중요하다.
만약 문제에서 주어진 N이 10,000 이라면 O(N^3) 풀이 방법으로는 시간 초과가 날 것이다.

 

 

🔥 스택 & 큐

• 많이 사용되긴 하지만 단독으로 사용되는 경우보다 구현하는데 필요한 자료구조 정도로 사용되는 경우가 많다. 예) 스택 : DFS, 큐 : BFS
• 문제에서 선입선출, 후입선출의 단서가 보이면 사용하자!

ㅇㅖ ) 

 스택 (후입선출) 

 택배 상하차 - 차례대로 위에서부터 쌓고, 다시 꺼낼때도 위에서부터 꺼냄
 입구가 하나밖에 없다고 생각

큐 (선입선출)

은행창구 : 먼저오는 사람이 먼저 서비스를 받음 

 

🔥 힙

• 우선순위를 고려하는 문제에서 사용된다. 예) 작은 수부터, 큰 수부터
• PriorityQueue의 경우 개선된 다익스트라의 구현에 사용된다.

 

🔥 브루트 포스(완전탐색)

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

 

 

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

• 복잡한 문제를 한 번에 해결하는 것이 아닌, 조금씩 점차적으로 풀이하는 유형이다. (점화식을 떠올리면 이해하기 쉬움)
• 개인적으로 어려운 유형이라고 생각한다.
• 다른 유형도 그렇겠지만, 특히 DP는 여러 문제를 풀어보면서 감을 익혀보자.
• bottom-up, top-down 을 모두 공부하자. (필자는 bottom-up 접근이 편하다고 생각)
• 한 문제를 bottom-up, top-down 두 방법으로 각각 풀이해보는 것도 좋다.

 

🔥  그리디

• 부분적인 최적해가 전체적인 최적해가 되는 문제에서 사용한다.
• 어렵게 출제되면 풀이를 쉽게 떠올리기 힘드니, 문제를 많이 풀어보면서 풀이 방법을 기억하자.
• 정렬, 우선순위 큐를 활용하는 경우가 많다.

 

🔥  이분 탐색

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

 

🔥   트리

• 트리의 경우 DFS를 활용한 전/중/후위 순회, 루트노드, 서브트리, 높이, 너비, 그래프에서 트리의 수 찾기 등 다양하게 출제할 수 있다.
• 따라서 트리를 활용한 다양한 문제의 유형을 풀어보는 것이 좋다.
  
  
• 바킹독 트리 문제집의 문제들을 풀어보는 것을 추천한다.

 

 

🔥  그래프

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

 

🔥   투 포인터, 슬라이딩 윈도우

• 배열에서 인덱스 2개를 사용해야 할때 평범하게 for 문 2번으로 풀이하면 시간 초과가 발생하는 경우 생각해볼 수 있다.
• 인덱스 2개를 while 문 한번으로 사용하면서 문제를 해결할 수 있다.
• 구간 합도 공부하자.
  
  
• 예) 백준 - 2230번 수 고르기
• 투 포인터를 사용해서 두 수의 차이가 주어진 값보다 작으면 포인터 이동
• 주어진 값보다 크거나 같으면 최소 값 갱신

 

🔥    유니온 파인드

• 최근 자주 기출되는 유형이다.
• 노드를 집합에 속하게 하는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.
• 노드들을 루트 노드를 기준으로 하는 어떠한 집합으로 묶는다고 생각하면 이해하기 편하다.
  
  
• 예) 백준 - 1717번 집합의 표현
• 입력 값이 0인 경우 Union, 1일 경우 Find하여 루트 노드를 확인

 

🔥   최소 신장 트리

• 최소 신장 트리를 만드는데 필요한 비용을 구하는 유형이다.
• 자주 기출되지는 않지만, 사용되는 알고리즘이 어렵지 않으니 익혀두자.
• 크루스칼, 프림 알고리즘을 공부하자.
  
  
• 예) 백준 - 1368 물대기
• 우물을 하나의 노드라고 생각하고 MST 만드는 비용을 계산

 

🔥   비트마스킹

• 문제에서 0, 1로 표현할 수 있는 경우 비트마스크를 사용하여 효율적으로 풀이할 수 있다.
• 비트마스크를 사용하면 수행시간, 메모리에서 이점을 가진다.
• 비트 연산자를 사용하므로 AND, OR, XOR, NOT, Shift 를 공부하자.
  
  
• 예) 백준 - 11723 집합
• 비트를 해당 값의 유무(있으면 1, 없으면 0)로 사용하여 풀이
• 집합에 x를 추가하거나 있으면 무시하기 위해선 bitmask |= 0b1 << x