프로그래머스 데브코스 - 알고리즘 문제를 접근하는 방식

 

문제를 읽기전에 먼저 입출력 제한을 보자

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

1. 입력이 100 이하인 경우
   • 완전 탐색
   • 백트래킹
2. 입력이 10,000 이하인 경우
   • 최대 O(n^2) 이내로 끝내야하는 문제
   • 문제에 따라 O(n^2 log n)까지는 허용
   • n*n 2차원 리스트를 모두 순회해야하는 문제가 많음
3. 입력이 1,000,000 이하인 경우
   • 최대 O(n log n)으로 끝내야하는 문제
   • 힙, 우선순위 큐
   • 정렬
   • 동적 계획법
   • 위상 정렬
   • 다익스트라 알고리즘
4. 입력이 100,000,000 이하인 경우
   • 최대 O(n)으로 끝내야하는 문제
   • 동적 계획법
   • 그리디
5. 그 이상인 경우
   • 최대 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 알고리즘을 사용할 수 있지만 보통 파이썬과 같은 스크립트 언어에선 문자열 탐색이 빌트인으로 존재하기 때문에 구현에만 집중하면 된다.

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

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

---

엣지 케이스

코딩 테스트에선 항상 문제가 되는 것이 엣지 케이스다.

보통 엣지 케이스는 생각하기 힘들거나 상식적이지 않은 입력으로 들어오는 경우가 많다. 시간복잡도 계산을 끝내고 그 안에 풀 수 있도록 로직을 작성했다면 그 다음으로 엣지 케이스에 대한 대비를 해야한다.

엣지 케이스는 보통 다음과 같은 케이스가 많다.

1. 입력 값의 크기가 굉장히 작은 케이스 (대부분의 입력 값이 최대값 언저리인 경우)
2. 입력 값의 크기가 굉장히 큰 케이스 (대부분의 입력 값이 최소값 언저리인 경우)
3. 입력 값의 범위가 넒은 케이스 (A는 최소값이고 B가 최대값인 경우)
4. 음수 입력이 허용된 경우 음수만 입력받는 케이스
5. 리스트를 입력 받을 때 값이 없거나 하나만 있는 케이스

또한 입력 값이 아니더라도 상황에 따른 엣지 케이스도 있다.

1. 그래프에서 사이클(cycle)이 발생하는 경우
2. 길찾기 문제에서 지그재그로 움직일 경우
3. 부동소수점 오차

엣지 케이스는 문제마다 무궁무진하다. 위 사례가 아닌 유형도 문제에 따라 발생할 수 있다. 그렇기 때문에 항상 문제 풀이하면서 엣지 케이스를 염두해야 한다.