문제 유형 파악하기

코딩 테스트를 볼 때 빠르게 문제 유형을 파악하는 방법을 공유합니다. :)

문제를 읽기전에 무조건 입출력 제한을 보자!

문제를 자세히 읽기전에 입출력 제한을 보는것이 중요합니다. 특히 입력 제한을 보면 어떤 시간복잡도 내에 풀어야 하는지 알 수 있습니다. 예를들어 입력이 100 이하인 경우 높은 확률로 완전 탐색 문제입니다. 시간복잡도 O(n3) 까지도 감당이 가능하기 때문에 플로이드 워셜과 같이 시간복잡도가 높은 알고리즘도 사용이 가능합니다. 보통 다음과 같이 판단하시면 됩니다.

  • 입력이 100 이하인 경우

    • 완전 탐색
    • 백트래킹

  • 입력이 10,000 이하인 경우

    • 최대 O(n2) 이내로 끝내야하는 문제
    • 문제에 따라 O(n2 log n)까지는 허용
    • n*n 2차원 리스트를 모두 순회해야하는 문제가 많음

  • 입력이 1,000,000 이하인 경우

    • 최대 O(n log n)으로 끝내야하는 문제
    • 힙, 우선순위 큐
    • 정렬
    • 동적 계획법
    • 위상 정렬
    • 다익스트라 알고리즘

  • 입력이 100,000,000 이하인 경우

    • 최대 O(n)으로 끝내야하는 문제
    • 동적 계획법
    • 그리디

  • 그 이상인 경우

    • 최대 O(log n)으로 끝내야하는 문제가 많음
    • 거의 안나오는 문제 유형
    • 이진탐색

문제 유형

100%는 아니지만 높은 확률이라고 봐주시면 좋습니다. :) 코딩 테스트에서 많이 나오는 유형을 추렸습니다.

입력값이 작은 문제

위에서 적었듯 높은 확률로 완전 탐색 혹은 백트래킹 문제입니다. 구현력이 중요한 문제로 출제될 가능성이 높습니다.

지도가 주어지고 채워진 영역을 찾아야하는 경우

높은 확률로 BFS, DFS 문제입니다. FloodFill과 같이 정직한 방식으로 나오거나 전염병 문제나 치즈 문제(https://www.acmicpc.net/problem/2636)처럼 살짝 변형되서 나오는 경우가 있습니다.

그래프 그림이 있는 경우

이 경우 높은 확률로 세 가지 유형 중 하나입니다.

  • 최단 거리 찾기
  • 최소 신장 트리
  • 위상 정렬 문제에서 가장 빠른 길, 최단 거리와 비슷한 키워드가 나온다면 당연히 최단 거리 찾기 유형이고 X 비용 내로 갈 수 있는 길을 찾아라와 같은 키워드가 나와도 최단 거리 찾기 유형입니다. 다익스트라, BFS, DFS 등이 사용될 수 있습니다.

최소 신장 트리 문제는 보통 가장 저렴한 방법으로 모든 경로 연결해라 등의 키워드로 출제됩니다. 경로가 아니라 통신망, 전송 시간, 회로, 배관 등 다양한 용어로 나올 수는 있지만 핵심은 모든 경로를 가장 싸게 연결해라입니다. 그래프는 양방향일수도 단방향일수도 있습니다. 크루스칼, 프림 알고리즘을 사용할 수 있습니다.

위상 정렬은 순서를 정해야할 때 사용됩니다. 보통 순서, 차례 등의 키워드가 나오면 위상 정렬 문제입니다.

X라는 조건을 만족하는 가장 최대/최소값을 찾아라

이 경우 높은 확률로 결정 문제입니다. 파라메트릭 서치를 이용해서 풀 수 있습니다.

실시간으로 정렬이 이루어져야 하는 경우

이 문제 유형은 많이 봤었죠? 높은 확률로 우선순위 큐 혹은 힙을 사용하는 문제입니다.

DP 문제

보통 완전 탐색처럼 시간이 오래걸리면 안되는데 특별한 알고리즘을 사용하는 문제가 아닐거 같을 때는 높은 확률로 DP 문제입니다. 다른 문제처럼 딱봐도 이거네! 하는 특징이 없어서 보통 문제를 보고 바로 유형을 판단하기 힘든 경우 DP처럼 풀 수 있는지 생각해봐야 합니다. 종이를 꺼내고 다음과 같은 방식으로 해보셔도 괜찮을 것 같습니다.

  1. 문제를 따라 먼저 초기값을 적는다.
  2. 초기값을 포함해 모든 상태값을 적는다.
  3. 현재상태를 통해 다음 값을 구할 수 있는지 판단한다.
  4. 혹은 이전 상태들을 통해 현재 값을 구할 수 있는지 판단한다. 이런식으로 여러 번 해보고 식을 만들 수 있다면 100% DP 문제입니다.

문자열이 주어지는 경우

구현력 문제인 경우가 많습니다. 문자열을 자르거나, 붙이거나 탐색하는 문제가 대부분입니다. 문자열을 탐색하는 알고리즘이 필요한 경우 KMP 알고리즘을 사용할 수 있지만 보통 파이썬과 같은 스크립트 언어에선 문자열 탐색이 빌트인으로 존재하기 때문에 구현에만 집중하면 됩니다.

현재 상황에서 가장 최적인 선택을 해야하는 경우

문제에서 항상 최적의 선택을 해야하는 경우 혹은 가장 많은 선택을 할 수 있는, 가장 작은/큰 등의 키워드가 들어가면 그리디 문제일 가능성이 높습니다. 위에서 잠깐 말했던 최소 신장 트리도 그리디의 일종입니다.