CS 면접, 코딩테스트 알고리즘 종류 및 Java 코드 정리
알고리즘 도감 앱을 함께 보면, 각 알고리즘 동작을 그림으로 쉽게 이해하고 복습하기 좋습니다.
정렬 알고리즘
정의된 순서대로 데이터를 정렬하는 방법입니다.
버블 정렬
배열의 한쪽 끝에서부터, 서로 인접한 두 원소를 비교하고 위치를 교환하며 정렬하는 알고리즘입니다.
반대쪽 끝의 정렬된 원소들을 제외하고, 모두 정렬될 때까지 반복합니다.
코드가 단순하지만, 시간복잡도가 O(n²)으로 매우 느립니다.
버블 정렬 코드 예시
int[] digits = { 5, 3, 2, 8, 7, 6 };
// 정렬할 원소 수만큼 반복
for (int i = 0; i < digits.length-1; i++) {
// 0부터 이미 정렬된 요소 전까지 반복
for (int j = 0; j < digits.length-1-i; j++) {
// 인접한 두 원소를 비교하며,
// 왼쪽 값이 오른쪽 값보다 크면 위치 교환
if (digits[j] > digits[j+1]) {
int tmp = digits[j];
digits[j] = digits[j+1];
digits[j+1] = tmp;
}
}
}
Java에서 버블정렬을 오름차순으로 구현한 예시입니다.
선택 정렬
배열의 왼쪽 끝에서부터, 정렬되지 않은 부분에서 선택한 최소값과 위치를 교환하며 정렬하는 알고리즘입니다.
정렬되지 않은 데이터가 많을수록 성능이 떨어지며, 시간복잡도가 O(n²) 입니다.
선택 정렬 코드 예시
int[] digits = { 5, 3, 2, 8, 7, 6 };
// 배열 왼쪽 끝부터 차례로 정렬할 위치 선택
for (int i = 0; i < digits.length-1; i++) {
// 현재 위치를 최소값으로 가정
int minValIdx = i;
// 아직 정렬되지 않은 오른쪽 요소들과 비교하며 최소값 인덱스 선택
for (int j = i+1; j < digits.length; j++) {
if (digits[j] < digits[minValIdx]) {
minValIdx = j;
}
}
// 현재 위치, 최소값 위치 값 교환
int tmp = digits[i];
digits[i] = digits[minValIdx];
digits[minValIdx] = tmp;
}
Java에서 선택정렬을 오름차순으로 구현한 예시입니다.
삽입 정렬
배열의 두 번째 원소부터, 정렬된 왼쪽 구간에서 올바른 위치를 찾아 삽입하며 정렬하는 알고리즘입니다.
현재 정렬이 역순인 경우에는 비교 및 교환이 많아져서 시간복잡도가 O(n²) 입니다.
데이터가 적거나 이미 정렬된 원소가 많은 경우는 O(n)으로 퀵 정렬보다 효율적일 수 있습니다.
삽입 정렬 코드 예시
int[] digits = { 5, 3, 2, 8, 7, 6 };
// 배열의 두 번째 원소부터 올바른 위치에 삽입 반복
for (int i = 1; i < digits.length; i++) {
// 현재 삽입할 값 지정
int iVal = digits[i];
int j;
// 왼쪽 원소들과 차례로 비교
for (j = i-1; j >= 0; j--) {
// 왼쪽 원소가 삽입할 값보다 큰 값이면
if (digits[j] > iVal) {
// 왼쪽 원소를 오른쪽으로 덮어씌우기
digits[j+1] = digits[j];
} else {
// 왼쪽 원소가 삽입할 값보다 작으면 멈춤
break;
}
}
// 삽입할 값을 마지막 비교 +1 위치에 삽입
digits[j+1] = iVal;
}
Java에서 삽입정렬을 오름차순으로 구현한 예시입니다.
힙 정렬
힙 자료구조를 사용하여 정렬하는 알고리즘이며, 시간복잡도는 O(nlogn)입니다.
힙 정렬 구현 방법
- 배열을 최대힙으로 구성하고, 최대힙의 첫번째 원소 (가장 큰 수) 를 꺼내서 배열 마지막 원소와 교환합니다.
- 마지막 원소를 제외한 나머지 원소들로 다시 최대 힙을 만들고, 첫번째 원소를 꺼내서 배열 마지막-1 원소와 교환합니다.
- 오른쪽 끝의 정렬된 원소들을 제외하고, 모두 정렬될 때까지 반복합니다.
병합 정렬
수열을 재귀적으로 반씩 분할하고, 더이상 분할할 수 없으면 정렬하면서 병합해나가는 알고리즘입니다.
시간복잡도는 O(nlogn) 이며, 분할 정복 알고리즘의 일종입니다.
병합 정렬 구현 방법
- 배열을 반씩 분할해나갑니다.
- 분할된 각 그룹의 선두 숫자 비교 후 작은 숫자 이동을 반복하여, 오름차순으로 병합합니다.
- 정렬된 하나의 그룹이 될 때까지 각 그룹의 정렬 및 병합을 재귀적으로 반복합니다.
퀵 정렬
피봇과 좌우 마커를 이용하여 적은 비교 횟수로 정렬하는 알고리즘으로, 평균 시간복잡도는 O(nlogn) 입니다.
거의 정렬된 배열이거나, 피벗이 항상 한쪽 끝 원소로 선택되면 분할이 불균형해져 최악의 경우 O(n²)이 됩니다.
퀵 정렬 구현 방법
- 정렬 기준이 되는 피봇(pivot) 숫자를 랜덤으로 선택합니다.
- 피봇 원소, 가장 왼쪽 원소, 가장 오른쪽 원소에 각각 마커를 표시합니다.
- 왼쪽 마커는 피봇보다 크거나 같은 원소를 만날 때까지 오른쪽으로 이동합니다.
- 오른쪽 마커는 피봇보다 작은 원소를 만날 때까지 왼쪽으로 이동합니다.
- 마커들의 이동이 멈췄을 때, 왼쪽 마커가 오른쪽 마커보다 작으면 두 원소를 교환합니다.
- 만약 왼쪽 마커가 오른쪽 마커 위치와 같거나 지나쳤다면, 피봇 숫자와 오른쪽 마커 원소를 교환합니다.
- 피봇 원소 왼쪽 부분과 오른쪽 부분에 대해 재귀적으로 퀵 정렬을 반복합니다.
리스트 탐색 알고리즘
선형 탐색
배열의 앞에서부터 순차적으로 원소를 하나씩 비교하며 찾는 알고리즘입니다.
시간복잡도는 배열의 크기에 비례하여 O(n) 입니다.
이분 탐색 (이진 탐색 알고리즘)
정렬된 배열에서 중간 원소 값, 목표 값을 비교하며 탐색 범위를 반씩 줄여나가는 알고리즘입니다.
이분 탐색은 반드시 정렬된 자료구조에서만 가능하며, 시간복잡도는 O(logn) 입니다.
이분 탐색 코드 예시
int[] digits = { 5, 3, 2, 8, 7, 6 };
int target = 3;
int targetIdx = -1;
// 이분 탐색이 가능하도록, 배열을 오름차순 정렬
Arrays.sort(digits);
// 이분 탐색용 lt, rt 값 초기화 (답이 될 수 있는 범위로 설정)
int lt = 0;
int rt = digits.length-1;
// lt가 rt보다 작거나 같을 때까지만 반복
// 목표 값을 찾지 못하면, lr가 rt보다 커지게 되어있음
while (lt <= rt) {
// 중간 원소 인덱스 계산
int mid = (lt + rt) / 2;
// 중간 원소 값, 목표 값이 같으면 탐색 종료
if (target == digits[mid]) {
targetIdx = mid;
break;
}
if (target < digits[mid]) {
// 중간 원소 값보다 목표 값이 작으면, 우측 원소들을 후보에서 제외
rt = mid-1;
} else {
// 중간 원소 값보다 목표 값이 크면, 좌측 원소들을 후보에서 제외
lt = mid+1;
}
}
Java에서 배열을 오름차순으로 정렬한 뒤, 이분 탐색을 진행하는 코드입니다.
트리, 그래프 탐색 알고리즘
트리는 사이클이 없는 그래프라고 볼 수 있습니다.
트리의 간선은 무조건 노드 수 -1개입니다.
DFS (깊이 우선 탐색) ★
트리 및 그래프의 시작 노드부터 간선을 따라 가장 깊은 노드까지 이동하며 탐색하는 알고리즘입니다.
이전에 방문한 노드로 되돌아오며, 연결된 노드 중 방문하지 않은 노드를 다시 최대 깊이까지 방문합니다.
스택 또는 재귀 함수로 DFS를 구현할 수 있습니다.
부분집합, 순열, 조합, 순서에 따라 가능한 모든 경로를 탐색하는 문제는 DFS로 풀 수 있습니다.
DFS 재귀 구현 시 주의사항
부분집합, 순열, 조합, 백트래킹 등 탐색 경우의 수가 지수적으로 증가하는 문제에서
N 제한이 30~50 이상이면, DFS 재귀로 풀었을 때 1분 이상 소요되어 시간초과 될 수 있습니다.
재귀로 DFS 구현 예시
public void DFS(int n) {
if (n == 0) return;
// N이 3인 경우, 3 > 2 > 1 출력
// 출력 후 다음 스택 프레임이 생성되므로 N부터 출력됨
// System.out.println("내림차순 출력 : " + n);
// 재귀 함수 호출
DFS(n-1);
// N이 3인 경우, 1 > 2 > 3 출력
// 재귀가 끝까지 내려간 후, 마지막 스택 프레임부터 스택에서 빠져나오면서 출력됨
System.out.println("오름차순 출력 : " + n);
}
1부터 N까지 출력하는 DFS 함수 예시입니다.
재귀 및 스택으로 트리 탐색 DFS 구현 예시
// 트리 구성용 노드 클래스
class Node {
int data;
Node lt;
Node rt;
public Node(int data) {
this.data = data;
lt = null;
rt = null;
}
}
public class Main {
// 재귀로 트리 탐색 DFS 함수
public void DFS(Node root) {
// DFS 함수 종료 조건
if (root == null) return;
// 전위순회 : root 노드 > 왼쪽 노드 > 오른쪽 노드 방문
System.out.println("전위순회 root 노드 방문처리 : " + root.data);
// 왼쪽 노드 재귀 호출
DFS(root.lt);
// 중위순회 : 왼쪽 노드 > root 노드 > 오른쪽 노드 방문
// System.out.println("중위순회 root 노드 방문처리 : " + root.data);
// 오른쪽 노드 재귀 호출
DFS(root.rt);
// 후위순회 : 왼쪽 노드 > 오른쪽 노드 > root 노드 방문
// System.out.println("후위순회 root 노드 방문처리 : " + root.data);
}
// 스택으로 트리 탐색 DFS 함수
public void DFS_Stack(Node root) {
// 시작 노드가 비어있으면 종료
if (root == null) return;
// 시작 노드 push
Stack<Node> stack = new Stack<>();
stack.push(root);
// 스택이 비어있지 않을 때까지 반복
while (!stack.isEmpty()) {
// 스택에 최근 추가한 노드 꺼내기
Node curNode = stack.pop();
// 전위순회 : root 노드 > 왼쪽 노드 > 오른쪽 노드 방문
System.out.println("전위순회 root 노드 방문처리 : " + curNode.data);
// 스택으로 구현 시, 후위순회는 스택 2개로 구현해야 해서 어렵습니다.
// 현재 노드와 인접한 노드 중 아직 방문하지 않은 노드들 추가
// 스택은 선입후출이므로, 방문할 순서의 역순으로 push
if (curNode.rt != null) stack.push(curNode.rt);
if (curNode.lt != null) stack.push(curNode.lt);
}
}
public static void main(String args[]) {
// 트리 생성
Node root = new Node(1);
root.lt = new Node(2);
root.rt = new Node(3);
root.lt.lt = new Node(4);
root.lt.rt = new Node(5);
root.rt.lt = new Node(6);
root.rt.rt = new Node(7);
Main main = new Main();
// 재귀로 트리 탐색 DFS 힘수 호출
main.DFS(root);
// 스택으로 트리 탐색 DFS 함수 호출
main.DFS_Stack(root);
}
}
트리는 사이클이 존재하지 않아 방문여부 체크를 생략해도 무한루프가 생기지 않습니다.
재귀로 부분집합 생성 DFS 구현 예시
public static void main(String args[]) {
int[] arr = new int[] {1, 2, 3}; // 원소 배열
List<Integer> subset = new ArrayList<>(); // 부분집합 원소 리스트
Main main = new Main();
main.DFS(0, arr, subset);
}
public void DFS(int i, int[] arr, List<Integer> subset) {
// 부분집합 하나 완성
if (i == arr.length) {
// 현재까지 선택된 원소들로 이루어진 부분집합 출력
System.out.println(subset);
return;
}
// 현재 원소 포함 후 다음 원소로 넘어가기
subset.add(arr[i]);
DFS(i + 1, arr, subset);
// 현재 원소 미포함 후 다음 원소로 넘어가기
subset.remove(subset.size()-1);
DFS(i + 1, arr, subset);
}
재귀로 합이 같은 부분집합 탐색 DFS 구현 예시
public void DFS(int L, int sum, int[] arr) {
// 답을 찾은 경우, 스택에 쌓인 DFS들 조기 종료
// 문제의 답이 하나만 존재하는 경우 사용
if (flag) return;
// 답이 될 가능성이 없는 DFS 탐색 종료 (백트래킹, 가지치기)
if (sum > total / 2) return;
// 모든 원소 탐색 후 재귀에서, 부분집합 하나 완성 (종료 조건)
if(L == n) {
if ((total - sum) == sum) {
answer = "집합 내에 현재 부분집합과 합이 같은 부분집합이 있음";
flag = true; // 문제의 유일한 답을 찾았으므로 flag 변경
}
} else {
// 다음 원소 DFS 호출
DFS(L+1, sum + arr[L], arr); // 현재 원소 포함
DFS(L+1, sum, arr); // 현재 원소 미포함
}
}
DFS로 부분집합에 각 원소를 포함할지, 포함하지 않을지 결정하며 모든 부분 집합을 탐색합니다.
재귀로 중복순열 DFS 구현 예시
public void solution(int n, int m) {
// 순열 배열 생성
int[] pm = new int[m];
// 순열 DFS 함수 호출
DFS(0);
}
public void DFS(int L) {
// m개 선택 완료 (종료 조건)
if (L == m) {
// 현재까지 선택된 순열 출력
for (int x : pm) {
System.out.println(x + " ");
System.out.println();
}
return;
}
// 1번부터 N번까지 원소 선택 (중복 허용)
for (int i = 0; i < n; i++) {
// 현재 자리에 원소 채우기
pm[L] = i;
// 다음 자리에 원소 채우기 호출
DFS(L + 1);
}
}
중복 순열은 N개의 원소 중 M개를 중복해서 선택할 수 있고, 순서 있게 나열하는 경우의 수입니다.
재귀로 순열 DFS 구현 예시
public void solution(int n, int m) {
// 원소 사용 체크 배열 생성
boolean[] ch = new boolean[n];
// 순열 배열 생성
int[] pm = new int[m];
// 순열 DFS 함수 호출
DFS(0);
}
public void DFS(int L) {
// m개 선택 완료 (종료 조건)
if (L == m) {
// 현재까지 선택된 순열 출력
for (int x : pm) {
System.out.println(x + " ");
System.out.println();
}
return;
}
// 1번부터 N번까지 원소 선택 (중복 미허용)
for (int i = 0; i < n; i++) {
if (ch[i] == true) {
continue;
}
// 현재 자리에 원소 채우기
pm[L] = i;
// 현재 원소 사용 체크
ch[i] = true;
// 다음 자리에 원소 채우기 호출
DFS(L + 1);
// 현재 원소 사용 체크 해제
ch[i] = false;
}
}
순열은 N개의 원소 중 M개를 중복 없이 순서 있게 나열하는 경우의 수입니다.
ch 배열을 사용해서, 현재까지 이미 선택한 원소는 선택하지 않습니다.
재귀로 조합 DFS 구현 예시
public void solution(int n, int m) {
// 조합 배열 생성
int[] combi = new int[m];
// 조합 DFS 함수 호출 (1부터 N개까지)
DFS(0, 1);
}
public void DFS(int L, int start) {
// m개 선택 완료 (종료 조건)
if (L == m) {
// 현재까지 선택된 조합 출력
for (int x : combi) {
System.out.println(x + " ");
System.out.println();
}
return;
}
// 현재까지의 조합에 사용되지 않은 숫자부터 N번까지 DFS
for (int i = start; i <= n; i++) {
// 현재 자리에 원소 채우기
combi[L] = i;
// 다음 자리에 원소 채우기 호출
DFS(L + 1, i + 1);
}
}
조합은 N개의 원소 중 M개를 중복 없이, 순서 상관 없이 뽑는 경우의 수입니다.
이전에 선택한 원소보다 큰 원소만 탐색하여 모든 조합을 생성합니다.
구슬 뽑기, 로또번호 뽑기 문제 등에서 사용되므로 로직을 외워두면 좋습니다.
BFS (너비 우선 탐색) ★
트리 및 그래프의 시작 노드부터 차수가 가장 가까운 노드들을 우선 탐색하는 알고리즘입니다.
for문으로 현재 노드에 연결된 다음 뎁스 노드들을 큐에 add 하고, 순서대로 꺼내서 방문합니다.
가중치가 없는 트리 및 그래프에서 레벨 탐색, 최소 이동 횟수, 최단거리 문제는 BFS로 푸는게 효율적입니다.
DFS, BFS 메모리 사용 차이
DFS는 현재 탐색중인 경로에 속한 노드들만 스택에 저장하므로 깊이가 깊으면 메모리 사용이 많아집니다.
BFS는 현재 레벨의 모든 노드를 큐에 저장하므로 너비가 넓으면 메모리 사용이 많아집니다.
큐 트리 탐색 BFS 구현 예시
// 트리 구성용 노드 클래스
class Node {
int data;
Node lt;
Node rt;
public Node(int data) {
this.data = data;
lt = null;
rt = null;
}
}
class Main {
// 큐로 트리 탐색 BFS 함수
public int BFS(Node root) {
Queue<Node> queue = new ArrayDeque<>();
// 큐에 시작 노드 추가
queue.offer(root);
// 루트 레벨 초기화
int L = 0;
// 큐가 비어있지 않을 때까지 반복
while(!queue.isEmpty()) {
// 현재 레벨 노드 수 저장 (반복문 시작 후 변동되므로, 미리 저장)
int len = queue.size();
// 현재 레벨 노드들 탐색
for (int i = 0; i < len; i++) {
// 큐에서 현재 레벨 노드 꺼내기
Node curNode = queue.poll();
// 말단 노드 발견 시, 최단거리 출력
if (curNode.lt == null && curNode.rt == null) return L;
// 큐에 다음 레벨 노드들 추가
if (curNode.lt != null) queue.offer(curNode.lt);
if (curNode.rt != null) queue.offer(curNode.rt);
}
L++;
}
return L;
}
public static void main(String args[]) {
// 트리 생성
Node root = new Node(1);
root.lt = new Node(2);
root.rt = new Node(3);
root.lt.lt = new Node(4);
root.lt.rt = new Node(5);
root.rt.lt = new Node(6);
root.rt.rt = new Node(7);
Main main = new Main();
// 큐로 트리 탐색 BFS 함수 호출
System.out.println( main.BFS(root) );
}
}
수직선 좌표 탐색 BFS 구현 예시
public int BFS(int start, int end) {
// 이동 가능한 방향 배열
int[] dis = {1, 5, -1};
// 방문 체크 배열 (1부터 최대 좌표 10000까지 저장)
int[] ch;
ch = new int[10001];
Queue<Integer> queue = new ArrayDeque<>();
// 큐에 출발 좌표 추가 및 방문 표시
queue.offer(start);
ch[start] = 1;
// 점프 횟수 초기화
int L = 0;
// 큐가 비어있지 않을 때까지 반복
while(!queue.isEmpty()) {
int len = queue.size();
// 현재까지 이동한 좌표들 탐색
for (int i = 0; i < len; i++) {
// 큐에서 현재 좌표 꺼내기
int x = queue.poll();
// 현재 좌표에서 이동 가능한 다음 좌표들 확인
for (int j = 0; j < dis.length; j++) {
int nx = x + dis[j];
// 송아지를 찾은 경우, 점프 횟수 반환
if (nx == end) return L + 1;
// 다음 좌표가 이동 가능 범위이고, 방문하지 않은 좌표인 경우
if (nx >= 1 && nx <= 10000 && ch[nx] == 0) {
// 방문 처리
ch[nx] = 1;
// 큐에 다음 좌표 추가
queue.offer(nx);
}
}
}
// 점프 횟수 추가
L++;
}
// 송아지가 없어서 찾지 못한 경우
return -1;
}
1~ 10000 수직선 좌표에서 한 번의 점프로 1, 5, -1 이동 가능할 때
최소 몇 번의 점프로 송아지 위치까지 갈 수 있는지 구하는 문제 풀이입니다.
다익스트라
양의 가중치만 있는 방향/무방향 그래프에서 목표 노드까지의 최단 경로를 구하는 알고리즘입니다.
음의 가중치가 있는 그래프에서는 올바르게 동작하지 않습니다.
우선순위 큐로 다익스트라 구현 예시
// 노드 클래스 정의
class Node implements Comparable<Node> {
int vertex; // 노드 번호
int cost; // 현재 노드까지의 가중치
public Node(int vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
@Override
public int compareTo(Node order) {
// 가중치 오름차순 정렬
return Integer.compare(this.cost, order.cost);
}
}
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
// 노드 수, 간선 수 입력
int n = sc.nextInt();
int m = sc.nextInt();
// 인접 리스트 그래프 생성
List<List<Node>> graph = new ArrayList<>();
// 그래프에 노드 리스트 추가 (1번 노드부터 있으므로, 0번 인덱스 미사용 예정)
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// 간선 연결 정보 입력
for (int i = 0; i < m; i++) {
int curVertex = sc.nextInt();
int nextVertex = sc.nextInt();
int cost = sc.nextInt();
// 현재 노드 리스트에 다음 노드 객체 추가
graph.get(curVertex).add(new Node(nextVertex, cost));
// 무방향 그래프 (양방향 그래프) 인 경우 추가
// graph.get(nextVertex).add(new Node(curVertex, cost));
}
// 각 노드까지의 최단거리 배열 생성 (최단거리 초기값 무한으로 설정)
int[] dist = new int[n+1];
Arrays.fill(dist, Integer.MAX_VALUE);
// 시작 노드부터 각 노드까지의 최단거리 탐색
Main main = new Main();
main.solution(graph, dist);
// 시작 노드부터 각 노드까지의 최단거리 출력
for (int i = 1; i <= n; i++) {
if (dist[i] != Integer.MAX_VALUE) {
System.out.println(i + "번 노드까지의 최단거리 : " + dist[i]);
} else {
System.out.println(i + "번 노드까지 도달 불가");
}
}
}
// 다익스트라 알고리즘으로 시작 노드부터 모든 노드까지의 최단거리 탐색 함수
public void solution(List<List<Node>> graph, int[] dist) {
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 노드 및 최단거리 추가
pq.offer(new Node(1, 0));
dist[1] = 0;
// 우선순위 큐가 비어있지 않을 때까지 반복
while(!pq.isEmpty()) {
// 우선순위 큐에서 가장 가중치가 작은 노드 꺼내기
// Node 클래스 내 compareTo 메소드 기준으로 정렬되어 꺼내집니다.
Node curNode = pq.poll();
// 현재 노드 최단거리보다 현재 노드 가중치가 크면 넘어가기
if(dist[curNode.vertex] < curNode.cost) {
continue;
}
// 현재 노드에서 갈 수 있는 다음 노드들 순회
for(Node nextNode : graph.get(curNode.vertex)) {
// 다음 노드 최단거리보다 현재 노드 가중치 + 다음 노드 가중치가 작으면
if(dist[nextNode.vertex] > curNode.cost + nextNode.cost) {
// 다음 노드 최단거리 갱신
dist[nextNode.vertex] = curNode.cost + nextNode.cost;
// 다음 탐색할 후보 노드 추가
pq.offer(new Node(nextNode.vertex, curNode.cost + nextNode.cost));
}
}
}
}
}
인접 행렬 그래프 + for문을 이용하면 방문하지 않은 각 노드마다 최단거리 노드를 순차 탐색해서 O(n²)이지만,
인접 리스트 그래프 + 우선순위 큐를 이용하면 다음 최단거리 후보 노드를 바로 꺼내서 효율적입니다.
벨만-포드
음의 가중치가 있는 그래프에서도 올바른 최단 경로를 구할 수 있는 알고리즘입니다.
음의 가중치가 없는 그래프에서는 다익스트라 알고리즘이 더 효율적입니다.
A* (에이 스타)
현재 노드의 가중치 + 도착 지점까지의 예상 가중치로 최단 경로를 찾는 알고리즘입니다.
예상 가중치를 어떻게 설정하느냐에 따라 효율이 달라질 수 있습니다.
그래프 최적화 알고리즘
크루스칼, 프림 알고리즘 공통점
무방향 그래프에서 모든 노드들을 최소 비용 간선들로 연결하는 최소 스패닝 트리를 찾는 알고리즘들입니다.
음의 가중치가 있어도 정상 동작하고, 모든 간선의 가중치가 서로 다르면 MST는 항상 유일합니다.
가중치가 없는 그래프이거나, 최소 가중치 간선이 중복되면 MST가 유일하지 않을 수 있습니다.
크루스칼
간선 중심으로 확장하므로 시간복잡도는 O(E log E) 이고, 간선 수가 적은 희소 그래프에서 효율적입니다.
크루스칼 알고리즘 구현 방법
모든 간선을 가중치 기준으로 정렬한 뒤, 가장 낮은 가중치의 간선부터 순서대로 확인합니다.
Union-Find 알고리즘으로 사이클 여부를 판별하여 사이클이 생기지 않는 간선이면 트리에 추가합니다.
사이클이 생기는 간선은 제거하며, 트리의 간선 수가 노드 수 -1개가 될 때까지 반복합니다.
프림
정점 중심으로 확장하므로 시간 복잡도는 O(E log V) 이고, 정점 수가 적은 조밀 그래프에서 효율적입니다.
에드몬즈
가중치 방향 그래프에서 루트에서 출발하는 최소 비용 방향 트리를 구성하는 알고리즘입니다.
알고리즘 구현이 복잡해서 코딩테스트에서 나오는 경우는 거의 없다고 합니다.
그래프 알고리즘 보조 도구
Union-Find 알고리즘
그래프의 노드들이 같은 집합에 속하는지 효율적으로 판별할 수 있는 알고리즘입니다.
크루스칼 알고리즘, 무방향 그래프 사이클 존재여부 판별, 네트워크 수 계산, 원소 그룹 판별 문제 등에서 사용됩니다.
Union-Find 알고리즘 코드 예시
int[] parent = new int[원소수];
// 각 원소가 속한 집합의 루트 원소 초기화
for (int i = 0; i < 원소수; i++) {
parent[i] = i;
}
// 원소가 속한 집합의 루트 원소 반환 함수
public int find(int v) { // v는 vertex (정점)
// 현재 원소가 루트 원소면 값 반환
if (parent[v] == v) return v;
// 현재 원소가 루트 원소가 아니면,
// 재귀적으로 루트 탐색하고 돌아오며 최신 루트 원소로 값 업데이트
return parent[v] = find(parent[v]);
// 집합 내에 간접적으로 연결된 원소들을 루트에 연결하면서
// 경로를 압축하여 다음 find 시 시간복잡도를 낮춤
}
// 두 원소 집합을 연결하여 하나의 집합으로 합치는 함수
public void union(int v1, int v2) {
// 두 원소가 속한 집합의 루트 원소 조회
int fv1 = find(v1);
int fv2 = find(v2);
// 원소1, 원소 2가 서로 다른 집합이면,
if (fv1 != fv2) {
// 원소1의 루트 원소 값을 원소2의 루트 원소로 변경하여 같은 집합으로 합치기
parent[fv1] = fv2;
}
}
// 원소 연결 정보 입력 시 집합 생성
for (int i = 0; i < 원소연결수; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
union(v1, v2);
}
// 두 원소가 같은 집합에 속하는지 확인
if (find(v1) == find(v2)) {
// 같은 집합 관계
} else {
// 다른 집합 관계
}
union(원소1, 원소2) 함수를 원소간 연결 관계 수만큼 호출하여 집합 관계 저장 후,
find(원소1), Find(원소2) 결과 비교 시 서로 같으면 같은 집합에 속하는 원소입니다.
문제 해결 알고리즘
코딩테스트에서 자주 나오는 문제 해결 알고리즘들입니다.
백트래킹
모든 경우의 수를 탐색하는 완전탐색의 한 종류입니다.
가능한 모든 경우의 수를 탐색하되, 답이 될 가능성이 없는 노드에선 탐색을 포기하고 되돌아갑니다.
일반적으로 백트래킹은 DFS 재귀 기반으로 구현하고, 완전탐색보다 효율적입니다.
분할 정복
전체 문제를 작은 문제들로 나누어 해결한 결과를 합쳐서 해결하는 알고리즘입니다.
동적계획법 (DP)
전체 문제를 작은 부분 문제들로 나누어 해결한 결과를 재사용하며 해결하는 알고리즘입니다.
동일한 부분 문제들의 중복이 있다는 점에서 분할 정복 알고리즘과는 개념이 다릅니다.
특정 합을 만드는 경우의 수 문제 등에서 DP를 사용하면 효율적입니다.
DP 상향식 (Bottom-up 방식)
반복문으로 작은 문제부터 큰 문제까지 순차적으로 답을 구하는 방식입니다.
배열, ArrayList 등 DP 테이블에 타뷸레이션하며 점점 큰 문제의 답을 완성해 나갑니다.
스택 프레임이 메모리를 차지하는 재귀를 사용하지 않고 for문으로 구현해서 메모리 효율적입니다.
DP 하향식 (Top-down 방식)
큰 문제에서 작은 문제를 재귀적으로 호출하는 방식입니다.
계산된 답을 배열, ArrayList, 해시맵 등에 메모이제이션 후 재사용합니다.
모든 작은 문제를 해결하지 않고 필요한 문제만 계산합니다.
재귀를 활용한 DP 구현 방법
- 종료 조건을 설정합니다.
- 재귀로 반복할 수 있는 점화식을 세웁니다.
- 작은 문제의 결과를 메모이제이션 기법으로 저장하여 중복 계산을 피합니다.
냅색 알고리즘
제한된 조건을 충족하는 조합들 중에서 최대 가치를 구하는 DP 기반 알고리즘입니다.
거스름돈 동전 개수 문제 풀이
public int solution(int[] coin, int n) {
// DP 테이블 초기회
int[] dy = new int[n + 1];
Arrays.fill(dy, Integer.MAX_VALUE); // 각 금액마다 필요한 최소 동전 수 배열
dy[0] = 0;
// 각 금액에 필요한 최소 동전 수 구하기
for (int i = 0; i < coin.length; i++) {
for (int j = coin[i]; j <= n; j++) {
dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);
}
}
// 목표 금액에 필요한 최소 동전 수 반환
return dy[n];
}
동전의 개수가 무한하므로, j를 앞에서부터 시작하여 같은 동전 중복을 허용합니다.
최대 점수 구하기 문제 풀이
public int solution(int[] problemTimes, int[] problemScores, int timeLimit) {
// DP 테이블 초기화
int[] dy = new int[timeLimit + 1]; // 각 시간으로 풀 수 있는 문제들의 최대 점수 배열
// 각 문제 풀이 시작
for (int i = 0; i < problemTimes.length; i++) {
int problemTime = problemTimes[i];
int problemScore = problemScores[i];
// 제한 시간부터 현재 문제를 푸는데 걸리는 시간까지 반복
for (int j = timeLimit; j >= problemTime; j--) {
// (현재 시간 - 문제 시간)의 점수 + 현재 문제 점수가
// 현재 시간으로 풀 수 있는 다른 문제 조합의 점수보다 크면 갱신
dy[j] = Math.max(dy[j], dy[j - problemTime] + problemScore);
}
}
// 제한 시간동안 풀 수 있는 문제들의 최대 점수 반환
return dy[timeLimit];
}
각 문제는 1번씩만 풀 수 있으므로, j를 뒤에서부터 시작하여 같은 문제 중복 풀이를 허용하지 않습니다.
그리디 (Greedy)
문제 해결 과정에서 눈 앞에 보이는 최선의 선택만을 하며, 선택을 번복하지 않는 알고리즘입니다.
각 단계의 선택이 부분 문제의 최적해와 일치하고, 전체 문제의 최적해를 만들 수 있을 때 사용해야 합니다.
결정 알고리즘
주어진 입력에 대해 특정 조건을 만족하는지 참/거짓 여부를 결정하는 알고리즘입니다.
최적값 후보 범위 내에서 이분 탐색으로 범위를 좁히며 판정을 반복하면 최적값을 찾을 수 있습니다.
최대값, 최소값 등 조건을 만족하는 최적의 답을 효율적으로 찾아내는 문제에 주로 사용됩니다.
마구간 정하기 문제 풀이
public int count(int stables, int distance) {
// 1번째 마구간에 1마리 배치
int cnt = 1;
int endPoint = stables[0];
// 입력받은 거리를 유지하며 다음 마구간에 말 배치 및 카운트
for (int i = 1; i < stables.length; i++) {
if (stables[i] - endPoint >= distance) {
cnt++;
endPoint = stables[i];
}
}
// 마구간에 배치할 수 있는 말의 수 반환
return cnt;
}
public int solution(int n, int[] stables) {
int answer = 0;
// 이분 탐색을 위해서 마구간 좌표 정렬
Arrays.sort(stables);
// 이분 탐색용 lt, rt 값 초기화
int lt = 1; // 가능한 말 사이 최소 거리
int rt = stables[ stables.length -1 ]; // 가능한 말 사이 최대 거리
// 결정 알고리즘 코드 (이분 탐색 활용)
while (lt <= rt) {
int mid = (lt + rt) / 2;
// mid 거리를 유지하며 각 마구간에 배치할 수 있는 말의 수가 N마리 이상인 경우
if (count(stables, mid) >= n) {
// 가장 가까운 두 말의 거리 최대값 갱신
answer = mid;
// 더 큰 거리로 배치 시도
lt = mid + 1;
} else {
// 더 좁은 거리로 배치 시도
rt = mid -1;
}
}
return answer;
}
N마리의 말을 마구간에 배치할 때, 가장 가까운 두 말의 거리 최대값을 구하는 문제 풀이입니다.
결정알고리즘은 while문이 끝날 때 answer에 들어있는 숫자가 가장 유효한 값입니다.
알고리즘 외 문제 유형
시뮬레이션 & 구현
주어진 상황을 이해하고 코드로 구현하는 문제이며, 알고리즘처럼 일반화한 방법으로 풀 수 없습니다.
배열 회전하기, 전치 행렬 만들기, 달팽이 수열 만들기 등의 문제 등이 있습니다.
청소 로봇 시뮬레이션 문제 풀이
public int[] solution(int[][] board, int time) {
// 12시부터 90도 회전 방향 배열
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
// 로봇의 초기 이동 방향 : 3시
int dir = 1;
int x = 0;
int y = 0;
// 로봇(2)의 초기 위치 찾기
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == 2) {
x = i;
y = j;
}
}
}
int seconds = 0;
// 1초마다 이동 또는 회전하는 로봇 청소 시작
while (seconds < time) {
// 다음 위치 계산
int nx = x + dx[dir];
int ny = y + dy[dir];
// 로봇의 다음 위치가 이동할 수 없는 곳이거나, 장애물(1)이면 90도 회전
if (nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length || board[nx][ny] == 1) {
// 다음 방향 = 현재 방향 + 1을 방향 수로 나눈 나머지 ★
dir = (dir + 1) % dx.length;
} else {
// 로봇이 이동할 수 있는 곳이거나, 장애물이 아니면 이동
x = nx;
y = ny;
}
seconds++;
// 만약, 로봇이 청소를 멈춰야 하는 경우는 여기에서 체크 후 break;
}
// 로봇의 최종 위치 배열 반환
return new int[] { x, y };
}
나선형 좌석 배치 시뮬레이션 문제 풀이
public int[] solution(int row, int col, int k) {
// K번째 손님이 앉을 좌석이 없는 경우
if (k > (row * col)) {
// 문제에서 요구하는 값 리턴
return new int[]{ 0, 0 };
}
// 문제는 좌표처럼 좌측 하단부터 배치하는 형태이므로,
// 배열에 좌측 상단부터 배치해도 정답이 되도록
// 행, 열을 반전하여 90도 회전
int[][] board = new int[col][row];
// 12시부터 90도 회전 이동 방향 배열
int[] dx = new int[]{ -1, 0, 1, 0 };
int[] dy = new int[]{ 0, 1, 0, -1 };
// 좌석 초기 이동 방향 : 3시
int dir = 1;
// 초기 좌석 배치
int x = 0;
int y = 0;
int count = 1;
board[x][y] = count;
// K번째 좌석이 배치될 때까지 반복
while(count < k) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// 다음 좌석이 배열 범위를 넘어가거나, 이미 좌석 배치가 된 경우
if (nx < 0 || nx >= col || ny < 0 || ny >= row || board[nx][ny] > 0) {
// 방향 변경 후 넘어감
dir = (dir + 1) % dx.length;
continue;
}
// 다음 좌석으로 이동
x = nx;
y = ny;
// 이동한 좌석 배치
count++;
board[x][y] = count;
}
// k번째 좌석 좌표 반환
// 문제는 좌표가 (1, 1)부터 시작하므로 +1
return new int[]{ x+1, y+1 };
}
나선형으로 좌석 배치 시, K번째 손님이 앉을 수 있는 좌석의 좌표를 반환하는 문제입니다.