코딩테스트 문제유형 빠르게 파악하기

1. 입출력 제한으로 문제유형 파악하기

"문제를읽기 전 입출력 제한을 잘 살펴보자"

 

밑의 알고리즘이 결정적인 것은 아니고 그럴 확률이 매우 높다는 것을 의미

 

• 입력이 100이하인 경우
  • 완전탐색
  • 백트래킹
• 입력이 10,000 이하인 경우
  • 최대 $O(n^{2})$이내로 끝내야 하는 문제
  • 문제에 따라 $O(n^{2} log n)$까지는 허용
  • n * n 2차원 리스트를 모두 순회해야하는 문제가 多
• 입력이 1,000,000 이하인 경우
  • 최대 $O(n log n)$으로 끝내야하는 문제
  • 힙, 우선순위 큐
  • 정렬
  • 동적 계획법
  • 위상 정렬
  • 다익스트라 알고리즘
• 입력이 100,000,000 이하인 경우
  • 최대 $O(n)$으로 끝내야하는 문제
  • 동적 계획법
  • 그리디
• 그 이상인 경우
  • 최대 $O(logn)$으로 끝내야하는 문제가 많음
  • 거의 안나옴
  • 이진탐색

2. 문제 유형

100%는 아님. (높은 확률)

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

원글 : 프로그래머스 스쿨 (자율주행 데브코스)