★ 코딩 테스트에 나오는 알고리즘/문제 유형 총정리

 알고리즘

• 구현(Implementation) 알고리즘:  머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이 어려운 알고리즘
• 브루트 포스(Brute Force) 알고리즘: 모든 경우의 수를 탐색하는 알고리즘
• 그리디(Greedy) 알고리즘: 각 단계마다 항상 최선의 선택을 하여 해에 근사한 값에 도달하는 알고리즘
• 다이나믹 프로그래밍(Dynamic Programming) 알고리즘: 큰 문제를 작은 문제들로 나누어 해결하고, 그 결과를 큰 문제 해결할 때 사용하는 알고리즘
• 재귀(Recursive) 알고리즘: 함수 내부에서 함수가 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘
• 분할 정복(Divide and Conquer) 알고리즘: 큰 문제를 분할이 불가능할 때까지 나누고(divide) 작은 문제들을 해결한 후 다시 합치면서 큰 문제를 정복하는(conquer) 알고리즘
• 백트래킹(Backtracking) 알고리즘: DFS를 사용하여 탐색 중인 경로에 찾고자 하는 답이 없다면 되돌아와 다른 루트로 탐색을 진행하는 완전 탐색 알고리즘
• 누적합(Prefix Sum) 알고리즘: 배열의 특정 구간의 합을 빠르게 구하는 알고리즘. 1차원 또는 2차원 배열에서 이용될 수 있다.
• 투 포인터(Two Pointers) 알고리즘: 두 개의 포인터를 적절히 사용하여 배열에서 원하는 값을 찾는 알고리즘
• 이진 탐색(Binary Search) 알고리즘: 중복이 없는 정렬된 배열에서 찾고자 하는 값의 위치를 찾는 알고리즘
• 상한선/하한선(upper/lower bound): 정렬된 배열에서 찾고자 하는 값과 같거나 큰 값이 처음으로 나오는 위치 혹은 찾고자 하는 값보다 큰 값이 처음으로 나오는 위치를 반환해주는 알고리즘
• 매개 변수 탐색(Parametric Search) 알고리즘: 조건을 만족하는 최댓값을 구하는 알고리즘
• 스위핑(Sweeping) 알고리즘: 한 쪽 방향으로 전체 공간을 스캔해주며 차례대로 판단 기준을 적용해시키는 알고리즘

 

 

▶ 그래프 관련

 

 그래프 탐색(Graph Search) 알고리즘

• 깊이 우선 탐색(DFS, Depth-First Search) 알고리즘: 루트 노드에서 시작하여 현재 분기를 완벽하게 탐색한 후 다음 분기를 탐색하는 알고리즘. 스택 또는 재귀함수로 구현한다.
• 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘: 루트 노드에서 시작하여 인접한 노드들을 먼저 탐색하는 알고리즘. 큐를 이용하여 구현한다.

 

 최단 경로(Shortest Path) 탐색 알고리즘

• 다익스트라(Dijkstra) 알고리즘: 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘. 다이나믹 프로그래밍에 속하며, 우선순위 큐를 사용한다.
• 벨만-포드(Bellman-Ford) 알고리즘: 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘. 음수 간선의 순환을 감지할 수 있다.
• 플로이드-워셜(Floyd-Warshall) 알고리즘: 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘. 간선의 가중치가 음수인 경우도 가능하다.
• 0-1 BFS(0-1 Breadth-First Search) 알고리즘: 가중치가 0이나 1로만 주어진 그래프에서 최단 경로를 찾는 알고리즘

 

 최소 신장 트리(MST, Minimum Spaining Tree) 구현

• 크루스칼(Kruskal) 알고리즘: 그래프 내 모든 정점을 최소 비용으로 연결하는 알고리즘. 그리디 알고리즘에 속하며, 유니온 파인드(Union-Find) 자료구조 사용.
• 프림(Prim) 알고리즘
• 위상 정렬(Topoplogical Sort) 알고리즘: 순서가 정해져 있는 작업들이 있을 때, 이들의 순서를 명확하게 결정해주는 알고리즘
• 최소 공통 조상(LCA, Lowest Common Ancestor) 알고리즘: 두 노드의 공통된 조상들 중에서 가장 가까운 조상을 찾는 알고리즘

 

 

 

특정 유형의 문제들

• 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제: 어떠한 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제. 다이나믹 프로그래밍 또는 이진 탐색 알고리즘을 이용하여 풀 수 있다.
• 최장 공통 부분 수열/ 최장 공통 문자열(LCS, Longest Common Subsequence/Substring) 문제: 두 문자열의 공통된 부분 수열 중 가장 긴 것을 고르거나, 공통된 연속 문자열 중 가장 긴 것을 고르는 문제
• 배낭(Knapsack) 문제: 서로 다른 가치와 무게를 가진 물건들을 한정된 무게만을 담을 수 있는 배낭에 최대의 가치를 가지도록 넣는 문제. 다이나믹 프로그래밍 문제이다.
• 펠린드롬(Palindrome) 문제: 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열인지 판별해야 하는 문제
• 기하학(Geometry) 문제: 기하학의 기본 요소인 점, 선, 다각형, 다면체와 관련된 문제
• 시뮬레이션(Simulation) 문제: 문제에서 제시되는 명령을 따라 차례대로 직접 수행해야 하는 문제

 

 

 

특정 테크닉 / 자료 구조

• 비트 마스크(BitMask) 기법: 정수의 이진수 표현을 이용하는 기법
• 유니온 파인드(Union-Find) 자료구조: 서로소 집합(disjoint set)의 묶음을 관리하는 자료구조. union연산은 두 집합을 합치는 연산이고, find연산은 해당 원소가 속한 집합의 루트노드를 구하는 연산이다.
• 세그먼트 트리(Segment Tree) 자료 구조: 특정 배열 구간의 합을 빠르게 구할 수 있는 자료 구조