문제 접근법

1. 알고리즘이 보인다. -> 바로 적용
   0. 만약 특정 알고리즘을 적용해야 하는 문제였는데, 2번 접근을 사용하면 사람이 직접 다룰 수 없을 만큼의 경우의 수가 발생한다. 그래서 만약 2번 접근 방식 중에 edge case가 너무 많아졌다면 스스로 적합한 알고리즘을 못 찾았다고 판단해야 한다. 참고 링크
2. 알고리즘이 보이지 않는다. (규칙 찾기)
   0. 문제를 쉽게 변형할 수 있다면 변형한다.
      1. 특이한 조건은 단순화 시킨다.
      2. 데이터의 형태를 내가 보기 편하게 변형시킨다.
   1. 구현 문제인지 의심한다.
      1. 시간 복잡도가 크지 않다면 모든 경우의 수를 전부 활용해서 문제를 풀 수 있다.
      2. 시간 복잡도가 크다면, 최적화를 통해 시간 복잡도를 낮출 수 있다. (3번 접근법)
   2. 그리디 문제인지 의심한다.
      1. 문제 내부에 큰 순으로 정렬 또는 작은 순으로 정렬이란 관계가 존재한다면 그리디를 적용해볼 여지가 있다. 그러나 최적해가 보장되지 않기 때문에 최적해 보장이 증명 가능한지 체크해야 한다.
      2. 최적해 보장을 증명하기 위해 반례를 찾아보는 것도 방법이다.
   3. 귀납 추론을 시도한다.
      1. 작은 스케일에서 문제를 관찰해본다. (귀납추론 -> 연역추론)
      2. 수열적인 접근 : 순서에 따른 규칙이 존재하는지 본다.
      3. 정수론적 접근 : 순서에 따른 규칙이 보이지 않을 때 적용
      4. 작은 스케일에서 귀납 추론을 하여 얻어낸 법칙을 연역 추론하듯 사용해본다.
      5. 즉, 작은 스케일에서 찾은 간단한 규칙을 큰 스케일에서도 적용해본다.
      6. 만약 큰 스케일에서도 규칙이 유효하다면, 그 규칙은 보편적인 규칙이라고 판단하고 이를 바탕으로 연역 추론을 시작한다. 즉, 코드를 작성한다.
   4. 연역 추론을 시도한다.
      1. 분할 정복이 가능한지 파악한다.
      2. 이를 통해 점화식 관계가 가능한 지 확인한다.
      3. 점화식 관계가 있다면 cache를 통해 최적화까지 적용시킨다.
      4. 점화식 관계 또한 작은 스케일에서부터 관계를 찾아본다.
      5. 그리고 해당 관계가 큰 스케일에서까지 적용되는지 체크한다.
      6. 적용 가능하다면 해당 관계를 이용하여 재귀함수, 반복문(가능하다면), DP를 적용시킨다.
   5. 이럼에도 보이지 않는다면 답을 찾아서 해당 유형을 외운다.
   6. 추론을 도와줄 생각 툴
      1. 어떤 정수에 대한 명제가 존재할 시에는 나눗셈 관점을 이용하여 무한한 정수 집합을 유한한 집합들로 쪼개어 시야를 좁혀서 살펴본다.
3. 알고리즘이 적절히 사용되었으나 시간 초과가 발생했다.(논리적으로는 맞는 코드이나, 최적화가 필요한 상황)
   1. 적절한 자료구조를 사용했는지 파악한다.
      1. 시간 복잡도가 높아지는 구간을 찾는다.
      2. 주로 연산이 집약되어 있는 곳을 의심한다.
      3. 연산이 집약되어 있는 곳에서 동일한 연산이지만 시간 복잡도가 낮은 자료구조로 바꾼다.
   2. 중첩된 반복문을 분리한다.
      1. 중첩된 반복문의 경우에 논리적으로 동일한 결과를 갖고 오나 반복문을 분리해서 구현할 수 있는 경우가 있다. 해당 경우가 가능한지 의심해본다.
   3. DP를 적용해본다.
      1. 분할 정복이 가능한지 파악한다. (동일한 문제로 쪼개지는지)
      2. cache 처럼 무엇인가 기억할 필요가 있는지 파악한다.
      3. 점화식 관계가 있는지 파악한다. (cache + dfs)
      4. 어떤 값의 이동이 있는 문제의 경우 배열을 dp로 사용한다. (연산을 통해 특정 값에 빨리 도달하기)
      5. 경로 이동 같은 경우에는 경로를 나타내는 자료구조 자체가 DP를 기억하는 자료구조가 된다. 따라서 누적합을 이용하여 최대 비용이 드는 경로를 구할 수 있다.
   4. 수학을 이용해서 문제를 해결하기 위한 함축적인 공식을 만들 수 있는 지 살펴본다.
      1. 사실 이 영역에 들어간다면 "귀납 추론 -> 연역 추론" 패턴을 통해서 일반화된 규칙을 찾아내는게 제일 중요하다. (2-3번 접근법으로 돌아간다.)
      2. 귀납추론 못지 않게 연역 추론도 중요하다. 중요한 것은 패턴을 찾는것
      3. 컴퓨터를 이용하여 순차적인 명령을 통해 값을 얻는게 아닌 하나의 공식을 통해서 곧바로 답을 얻을 수 없는지 파악한다.
      4. 예를 들면 for문을 통해 수열의 임의의 값을 구할 수도 있지만 일반식을 구해서 수열의 임의의 값을 구할 수도 있다.
   5. 연산 횟수 줄이기
      1. 함수 호출을 최대한 줄이기 위해서 재사용할 수 있는 변수를 선언한다.
4. 테스트 케이스를 모두 통과한 경우
   1. 엣지 케이스로 테스트 해본다.
      1. 테스트 케이스는 맞아도 히든 케이스를 다 맞는다는 보장이 없다.
      2. 극단적인 경우로 테스트 케이스를 만든다.
         1. 제일 큰 경우
         2. 제일 작은 경우
         3. 주어진 기준을 경계로 가장 가까운 양쪽의 값을 사용하는 경우

알고리즘 적용 기준

완벽한 기준은 아니니 주의

1. 그리디 알고리즘

   • 설명: 각 단계에서 최적의 선택을 하는 방식으로 접근하는 알고리즘입니다.
   • 적용 상황: 각 단계에서의 최적의 선택이 전체 문제에 대한 최적의 해결책을 보장할 때 사용됩니다.
   • 적용 기준: 문제의 구조가 그리디 속성을 만족하는지 확인합니다. 즉, 각 단계에서의 최적의 선택이 전체 최적의 해결책을 이끌어내는지 확인합니다.
   • 예시: 동전 거스름돈 문제에서 가장 큰 동전부터 최대한 사용하는 것이 최적의 해결책을 보장합니다.
   • 백준 문제: 동전 0 (11047), ATM (11399), 회의실 배정 (1931)

2. 분할 정복

   • 설명: 문제를 더 작은 하위 문제로 분할하고, 이 하위 문제들을 각각 해결한 후, 이들의 해를 결합하여 원래 문제를 해결하는 알고리즘입니다.
   • 적용 상황: 문제가 분할 가능하고, 하위 문제의 해가 원래 문제의 해를 구성할 수 있을 때 사용됩니다.
   • 적용 기준: 문제가 분할 가능하며, 분할된 하위 문제의 해결이 원래 문제의 해결로 이어지는지 확인합니다.
   • 예시: 병합 정렬이나 퀵 정렬과 같은 정렬 알고리즘에서 분할 정복 방식이 사용됩니다.
   • 백준 문제: 색종이 만들기 (2630), 종이의 개수 (1780), 행렬 제곱 (10830)

3. 동적 계획법

   • 설명: 복잡한 문제를 더 작은 하위 문제로 분할하고, 이 하위 문제들의 해를 저장하여 재사용하는 알고리즘입니다.
   • 적용 상황: 문제가 최적 부분 구조와 중복 부분 문제를 가질 때 사용됩니다.
   • 적용 기준: 문제가 최적 부분 구조를 가지며, 중복되는 부분 문제를 통해 효율적으로 해결할 수 있는지 확인합니다.
   • 예시: 피보나치 수열이나 배낭 문제와 같은 문제에서 동적 계획법이 사용됩니다.
   • 백준 문제: 1로 만들기 (1463), 2×n 타일링 (11726), 가장 긴 증가하는 부분 수열 (11053)

4. 투 포인터

   • 설명: 배열이나 리스트와 같은 선형 구조에서 두 개의 점을 이용해 원하는 결과를 얻는 알고리즘입니다.
   • 적용 상황: 배열이나 리스트가 정렬되어 있거나, 부분 배열이나 연속된 데이터에 대한 문제를 해결할 때 사용됩니다.
   • 적용 기준: 문제가 선형 구조에서의 부분 배열이나 연속된 데이터를 요구하며, 이를 투 포인터를 통해 효율적으로 해결할 수 있는지 확인합니다.
   • 예시: 정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는 문제에서 투 포인터 알고리즘이 사용됩니다.
   • 백준 문제: 수들의 합 2 (2003), 두 수의 합 (3273), 부분합 (1806)

5. 깊이 우선 탐색 (DFS)

   • 설명: 트리나 그래프에서 한 방향으로 노드를 탐색하다가 더 이상 탐색할 곳이 없으면 이전 노드로 돌아와 다른 방향을 탐색하는 알고리즘입니다.
   • 적용 상황: 모든 노드를 방문하거나, 경로를 찾는 문제를 해결할 때 사용됩니다.
   • 적용 기준: 문제가 그래프나 트리에서의 모든 노드 방문이나 경로 찾기를 요구하며, 이를 DFS를 통해 효율적으로 해결할 수 있는지 확인합니다.
   • 예시: 미로 찾기 문제나 그래프의 연결 요소를 찾는 문제에서 DFS가 사용됩니다.
   • 백준 문제: 연결 요소의 개수 (11724), 이분 그래프 (1707), 단지번호붙이기 (2667)

6. 너비 우선 탐색 (BFS)

   • 설명: 트리나 그래프에서 가까운 노드부터 탐색하는 알고리즘입니다.
   • 적용 상황: 최단 경로를 찾는 문제를 해결할 때 사용됩니다.
   • 적용 기준: 문제가 그래프나 트리에서의 최단 경로 찾기를 요구하며, 이를 BFS를 통해 효율적으로 해결할 수 있는지 확인합니다.
   • 예시: 두 노드 사이의 최단 경로를 찾는 문제나 그래프의 연결 요소를 찾는 문제에서 BFS가 사용됩니다.
   • 백준 문제: 미로 탐색 (2178), 토마토 (7576), 숨바꼭질 (1697)

7. 다익스트라 알고리즘

   • 설명: 그래프에서 한 노드에서 다른 노드로 가는 최단 경로를 찾는 알고리즘입니다.
   • 적용 상황: 가중치가 있는 그래프에서 최단 경로를 찾을 때 사용됩니다.
   • 적용 기준: 문제가 가중치가 있는 그래프에서의 최단 경로 찾기를 요구하며, 이를 다익스트라 알고리즘을 통해 효율적으로 해결할 수 있는지 확인합니다.
   • 예시: 도시 간의 최단 경로를 찾는 문제에서 다익스트라 알고리즘이 사용됩니다.
   • 백준 문제: 최단경로 (1753), 특정한 최단 경로 (1504), 최소비용 구하기 (1916)

8. 벨만-포드 알고리즘

   • 설명: 그래프에서 한 노드에서 다른 노드로 가는 최단 경로를 찾는 알고리즘입니다.
   • 적용 상황: 가중치가 음수인 간선이 있는 그래프에서 최단 경로를 찾을 때 사용됩니다.
   • 적용 기준: 문제가 가중치가 음수인 간선이 있는 그래프에서의 최단 경로 찾기를 요구하며, 이를 벨만-포드 알고리즘을 통해 효율적으로 해결할 수 있는지 확인합니다.
   • 예시: 환율 변환 문제에서 벨만-포드 알고리즘이 사용됩니다.
   • 백준 문제: 타임머신 (11657), 웜홀 (1865), 숨바꼭질4 (13913)

9. 플로이드-워셜 알고리즘

   • 설명: 그래프에서 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘입니다.
   • 적용 상황: 모든 노드 간의 최단 경로를 찾을 때 사용됩니다.
   • 적용 기준: 문제가 모든 노드 쌍 간의 최단 경로 찾기를 요구하며, 이를 플로이드-워셜 알고리즘을 통해 효율적으로 해결할 수 있는지 확인합니다.
   • 예시: 모든 도시 쌍 간의 최단 경로를 찾는 문제에서 플로이드-워셜 알고리즘이 사용됩니다.
   • 백준 문제: 플로이드 (11404), 경로 (11403), 키 순서 (2458)

10. 최소 신장 트리 (MST)

    • 설명: 그래프에서 모든 노드를 포함하면서 간선의 가중치 합이 최소가 되는 트리를 찾는 알고리즘입니다.
    • 적용 상황: 네트워크를 구성하거나, 모든 노드를 최소 비용으로 연결할 때 사용됩니다.
    • 적용 기준: 문제가 모든 노드를 포함하면서 간선의 가중치 합이 최소가 되는 트리를 찾는 것을 요구하며, 이를 MST 알고리즘을 통해 효율적으로 해결할 수 있는지 확인합니다.
    • 예시: 전기 네트워크 구성 문제나 도로 네트워크 구성 문제에서 MST 알고리즘이 사용됩니다.
    • 백준 문제: 네트워크 연결 (1922), 최소 스패닝 트리 (1197), 행성 연결 (16398)

알고리즘과 자료구조를 기준으로 나오는 문제 유형

완벽한 기준은 아니니 주의

	리스트	딕셔너리	집합	스택/큐	힙	트리/그래프
그리디 알고리즘	동전 0 (11047), ATM (11399)	빈도 수 계산 문제	중복 제거 문제	LIFO/FIFO 문제	최대/최소 값 찾기 문제	최소 신장 트리 문제, 네트워크 연결 (1922)
분할 정복	색종이 만들기 (2630), 종이의 개수 (1780)	-	-	-	힙 정렬 문제	행렬 제곱 (10830)
동적 계획법	1로 만들기 (1463), 2×n 타일링 (11726), 가장 긴 증가하는 부분 수열 (11053)	-	-	-	-	최소 비용 경로 문제
투 포인터	수들의 합 2 (2003), 두 수의 합 (3273), 부분합 (1806)	-	-	슬라이딩 윈도우 문제	-	-
DFS/BFS	-	-	-	깊이/너비 우선 탐색 문제, 연결 요소의 개수 (11724), 이분 그래프 (1707), 단지번호붙이기 (2667)	-	그래프 탐색 문제
다익스트라	-	-	-	-	우선순위 큐 문제, 최단경로 (1753), 특정한 최단 경로 (1504), 최소비용 구하기 (1916)	최단 경로 문제
벨만-포드 알고리즘	-	-	-	-	-	타임머신 (11657), 웜홀 (1865), 숨바꼭질4 (13913)
플로이드-워셜 알고리즘	-	-	-	-	-	플로이드 (11404), 경로 (11403), 키 순서 (2458)
최소 신장 트리 (MST)	-	-	-	-	-	네트워크 연결 (1922), 최소 스패닝 트리 (1197), 행성 연결 (16398)