취업 취준 코딩테스트 준비! 자주 나오는 유형 알아보기 (기업 코테)

백준이나 요즘 떠오르는 코드트리 등 알고리즘을 공부하는 다양한 방법이 있지만,

취업을 위해서 기업에서 출제하는 알고리즘 유형들을 파악하면 취업에 많은 도움이 됩니다.

 

 

 

알고리즘 공부를 해보시고, 부트캠프나 다양한 기관에서 코딩테스트를 경험해보신 적이 있으시다면 어떤 유형의 문제가 나오는지 유형이 조금씩 보입니다.

 

오늘은 이 코테 문제들 중 기업에서 출제하는 경향이 있는 유형들에 대해서 알아보도록 하겠습니다.

 

 

최적화 (greedy 알고리즘)

https://brilliant.org/wiki/greedy-algorithm/

문제의 접근 방법에 따라 반복문 재귀 백트래킹의 방법으로 풀어야하는 유형이 있습니다.

 

누적합 (prefix sum 알고리즘)

https://osgoodgunawan.medium.com/prefix-sum-80d531154b95

정수론을 사용한는 방법이 있고, DP(탑다운, 바텀업), 메모이제이션 등으로 풀어야하는 유형이 있습니다.

누적합 유형은 '점화식'을 구상하는 방법으로 바텀업 DP 유형의 문제가 나오기도 합니다.

 

완전탐색 (a.k.a 완탐)

완전탐색은 가장 보편적으로 나오는 코테 유형입니다.

문제의 접근 방법에 따라 반복문 재귀 백트래킹의 방법으로 풀어야하는 유형이 있습니다.

 

2차원 DP 

2차원 동적 계획법(DP)은 문제를 2차원 배열 형태로 정의하고, 작은 부분 문제들을 해결하여 전체 문제를 해결하는 유형입니다.

후술하게 될 문자열 비교나 LIS/LCS 등 문제에서도 사용됩니다. 배열 dp[i][j]를 이용해서 부분 문제의 최적 해를 저장하며, 이전 셀들의 값을 이용해 현재 셀의 값을 계산합니다.

 

LIS / LCS

https://www.researchgate.net/figure/Example-of-Longest-Increasing-Subsequence_fig1_286370190, https://www.oreilly.com/library/view/learning-javascript-data/9781788623872/871e4015-5e5a-4afd-93c4-16f37189a71c.xhtml

저는 찾아보면서 익숙하지 않았던 용어들인데요. 

LIS는 Longest Increasing Subsequence로 최장 증가 부분 수열을 의미합니다.

 

최장 증가 부분 수열 유형은 

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 찾는 방법으로 해결하는 유형입니다.

 

예를 들면

{ 6, 2, 5, 1, 7, 4, 8, 3} 이라는 수열에서, LIS는 { 2, 5, 7, 8 } 입니다.

 

LCS은 Longest Common Subsequence/Substring 으로 최장 공통 부분 수열/문자열을 의미합니다. 

LCS은 두 개 이상의 수열이나 문자열 중 공통된 원소를 가지고 있고, 길이가 가장 긴 부분 수열/문자열을 의미합니다.

 

투포인터

https://algodaily.com/lessons/using-the-two-pointer-technique

투포인터는 두 개의 포인터를 사용해 배열이나 리스트를 탐색하는 기법입니다. 시작점과 끝점을 설정해 조건에 맞게 포인터를 이동시키며 문제를 해결합니다. 주로 정렬된 배열에서 특정 합을 찾거나, 연속 부분 배열의 합을 구하는 문제에 사용됩니다. 효율적인 시간 복잡도(O(n))를 제공합니다.

 

이분탐색

https://www.freecodecamp.org/news/binary-search-in-java-algorithm-example/

이분 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다. 배열의 중간 요소와 찾고자 하는 값을 비교해 탐색 범위를 절반으로 줄여나갑니다. 반복적 또는 재귀적으로 수행되며, 시간 복잡도는 O(log n)입니다. 주로 숫자 탐색, 조건을 만족하는 최대/최소값 찾기 등에 사용됩니다.

 

DFS / BFS

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색 알고리즘입니다. DFS는 한 경로를 끝까지 탐색 후 돌아와 다른 경로를 탐색하며, 재귀나 스택을 사용합니다. BFS는 시작 노드에서 가까운 노드부터 탐색하며, 큐를 사용합니다. DFS는 경로 탐색, 미로 찾기에, BFS는 최단 거리 찾기, 레벨별 탐색에 유용합니다. 시간 복잡도는 둘 다 O(V+E)입니다.

 

다익스트라

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘입니다. 우선순위 큐를 사용해 방문하지 않은 정점 중 가장 짧은 경로를 선택하고, 인접한 정점의 경로를 갱신합니다. 시간 복잡도는 O(V^2)이며, 힙을 사용하면 O(E log V)로 효율적입니다. 주로 네트워크 경로 최적화, 지도 애플리케이션 등에 사용됩니다.

 

트리

트리 유형 문제는 계층적 구조를 가진 데이터를 효율적으로 탐색하고 처리하는 데 사용됩니다. 대표적으로 이진 트리, 이진 탐색 트리, AVL 트리, 트라이 등이 있습니다. 주로 순회(전위, 중위, 후위), 삽입, 삭제, 검색 등의 유형에 해당됩니다.

 

유니온파인드

https://yuminlee2.medium.com/union-find-algorithm-ffa9cd7d2dba

유니온파인드(Union-Find) 또는 분리 집합(Disjoint Set)은 서로소 집합을 효율적으로 관리하는 자료구조입니다. 두 주요 연산은 합집합(Union)과 찾기(Find)입니다. 합집합은 두 집합을 하나로 합치고, 찾기는 특정 원소가 속한 집합을 찾습니다. 경로 압축과 랭크를 이용해 시간 복잡도를 거의 상수 시간(O(α(n)))으로 최적화할 수 있습니다. 주로 그래프에서 사이클 판별, 연결 요소 찾기 등에 사용됩니다.

 

최소스패닝트리

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

최소 스패닝 트리(MST)는 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소가 되는 트리입니다. 주요 알고리즘으로 크루스칼(Kruskal)과 프림(Prim)이 있습니다. 크루스칼은 간선을 정렬해 가장 작은 간선부터 추가하며, 유니온파인드를 사용해 사이클을 방지합니다. 프림은 한 정점에서 시작해 연결된 간선 중 최소 가중치를 선택해 확장합니다. MST는 네트워크 설계, 도로 건설 등에서 비용을 최소화하는 데 사용됩니다. 시간 복잡도는 O(E log V)입니다.

 

 

※ 계속해서 유형별 문제를 업데이트할 예정입니다.