코딩 테스트 유형 알아보기

포스팅 목적

코딩 테스트 유형을 알아보고 유형별로 문제를 풀어봐야 대응할 수 있기 때문에 자주 출제되는 유형을 알고 빠르게 알고리즘을 선택하기 위해 포스팅 했습니다.

 

(알고리즘) 코딩 테스트 유형 중요도 순 정리

 

완전 탐색 Exhaustive Search ( Brute Force )

깊이 우선 탐색 ( DFS )

넓이 우선 탐색 ( BFS )

동적 프로그래밍 ( Dynamic Programming )

그리디 ( Greedy )

이진 탐색 ( Binary Search )

파라메트릭 서치 ( Parametric Search )

투 포인터 ( Two Pointer )

유니온 파인드 ( Union-Find )

크루스칼 

프림

다익스트라

GCD (최대공약수, 최소공배수)

순열/조합

Backtracking

Divide and conquer

 

코딩 테스트 사용할 알고리즘 빠르게 파악하기

 

시간 복잡도

• 대부분의 문제는 실행 시간이 1초에 가깝게 디자인이 된다.
  보통 1억번의 연산당 1초
  
  
• 입력이 100이하인 경우
  • 완전탐색
  • 백트래킹
• 입력이 10,000 이하인 경우
  • 최대 O(n^2) 이내로 끝내야 하는 문제
  • 문제에 따라 O(n^2logn) 까지는 허용
  • n * n 2차원 리스트를 모두 순회해야하는 문제
• 입력이 1,000,000 이하인 경우
  • 최대 O(nlogn) 으로 끝내야하는 문제
  • 힙, 우선순위 큐
  • 정렬
  • 동적 계획법
  • 위상 정렬
  • 다익스트라 알고리즘
• 입력이 100,000,000 이하인 경우
  • 최대 O(n) 으로 끝내야하는 문제
  • 동적 계획법
  • 그리디
• 그 이상인 경우
  • 최대 O(logn) 으로 끝내야하는 문제
  • 이진 탐색

 

문제 유형

• 입력값이 작은 문제
  • 완전탐색 or 백트래킹 문제
• 지도가 주어지고 채워진 영역을 찾아야 하는 경우
  • BFS or DFS
• 그래프 그림이 있는 경우
  • 높은 확률로 세가지 유형 중 하나
    1. 최단거리 찾기
    2. 최소 신장 트리 : "가장 저렴한 방법으로 모두 연결" 등 -> 크루스칼, 프림 알고리즘 사용가능
    3. 위상정렬 : "가장 빠른 길", "최단거리"와 비슷한 키워드가 나오거나 "X비용 내로 갈수 있는 길을 찾아라" -> 최단거리 찾기 -> 다익스트라, BFS, DFS
  • "순서", "차례"등의 키워드가 나오면 위상정렬 문제, 위상정렬은 순서를 정해야 할 때 사용
• X라는 조건을 만족하는 가장 최대/최소값을 찾아라
  • 결정문제 -> 파라메트릭 서치
• 실시간으로 정렬이 이루어져야 하는 경우
  • 우선순위 큐 or 힙
• DP문제
  • 보통 문제를 보고 바로 유형을 파악하기 힘든 경우 DP처럼 풀 수 있는지 확인필요
    1. 문제를 따라 먼저 초기값을 적는다.
    2. 초기값을 포함해 모든 상태값을 적는다.
    3. 현재상태를 통해 다음 값을 구할 수 있는지 판단한다.
    4. 혹은 이전상태들을 통해 현재값을 구할 수 있는지 판단한다.
  • 여러번 해보고 식을 만들 수 있다면 100% DP
• 문자열이 주어지는 경우
  • 구현력 문제인 경우가 대부분, 빌트인으로 해결 가능
• 현재 상황에서 가장 최적인 선택을 해야하는 경우
  • "가장 많은 선택을 할 수 있는", "가장 작은/큰" 등의 키워드
    -> 그리디 문제일 확률이 높음 최소신장트리도 그리디의 일종

 

참고 자료

• 내가 정리하는 코딩테스트 문제 유형 별 풀이 방법
• 코딩테스트 준비 Tip
• 코딩테스트 문제유형 빠르게 파악하기
• [그래프로 정리] 코딩 테스트에 가장 많이 출제 되는 알고리즘과 합격권 점수를 알아 보겠습니다.