CS 면접, 코딩테스트 알고리즘 종류 및 Java 코드 정리

2024-05-10

알고리즘 도감 앱을 함께 보면, 각 알고리즘 동작을 그림으로 쉽게 이해하고 복습하기 좋습니다.

정렬 알고리즘

정의된 순서대로 데이터를 나열하는 방법입니다.

선택 정렬

배열의 왼쪽 끝에서부터 차례로, 선택된 최소값과 위치를 교환하며 정렬하는 알고리즘입니다.
정렬되지 않은 데이터가 많을수록 성능이 떨어지며, 시간복잡도가 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²)으로 매우 느립니다.

버블 정렬 코드 예시

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 = 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개입니다.

너비 우선 탐색 (BFS) ★ (설명 수정 예정)

트리, 그래프의 시작 노드부터 차수가 가장 가까운 노드들을 우선하여 탐색하는 알고리즘입니다.
큐에 지금 방문할 노드들을 add 하고, 순서대로 꺼내서 방문합니다.
최단 경로를 찾는 미로찾기 문제, 네트워크 분석 문제에서 사용할 수 있습니다.

큐로 BFS 구현 요약

큐에 그래프의 시작 노드 add, 방문 처리
큐가 비어있지 않을 때까지 반복 시작
큐에서 노드를 poll
현재 노드와 인접한 노드들 중 방문하지 않은 노드들을 방문처리 후 큐에 add

깊이 우선 탐색 (DFS) ★ (설명 수정 예정)

트리, 그래프의 시작 노드부터 간선을 따라 가장 깊은 노드까지 이동하며 탐색하는 알고리즘입니다.
이전에 방문한 노드로 되돌아오며 연결된 노드 중 방문하지 않은 노드를 다시 최대 깊이까지 방문합니다.
스택에 다음 방문할 노드를 push 후 pop 하여 방문하거나, 재귀로 DFS를 구현할 수 있습니다.
최단 경로를 찾는 문제가 아니면 깊이 우선 탐색을 우선 고려해보는 것이 좋습니다.

DFS 재귀 사용 시 주의
부분집합, 순열, 조합, 백트래킹 등 탐색 경우의 수가 지수적으로 증가하는 문제에서
N 제한이 30~50 이상이면, DFS 재귀로 풀었을 때 1분 이상 소요되어 시간초과 날 수 있습니다.
이러한 경우는 DFS가 아니라 DP 냅색알고리즘 등 다른 알고리즘으로 푸는 것이 좋습니다.

스택으로 DFS 구현 요약

스택에 시작 노드를 push
스택이 비어있지 않을 때까지 반복 시작
스택에 최근 push 한 노드를 pop하고 방문 여부 확인 후 방문 처리
현재 노드와 인접한 노드 중 아직 방문하지 않은 노드들을 스택에 push
(스택은 선입후출이므로, 방문할 순서의 역순으로 노드를 push 합니다.)

벨만-포드

음의 가중치가 있는 그래프에서도 올바른 최단 경로를 구할 수 있는 알고리즘입니다.
음의 가중치가 없는 그래프에서는 다익스트라 알고리즘이 더 효율적입니다.

다익스트라

양의 가중치만 있는 그래프의 최단 경로를 구하는 문제에 자주 사용되는 알고리즘입니다.
우선순위 큐로 구현할 수 있으며, 음의 가중치가 있는 그래프에서는 제대로 동작하지 않습니다.

다익스트라 구현 요약

시작 노드의 최단거리를 0, 모든 노드의 최단거리를 무한으로 설정
시작 노드를 (거리 0, 노드) 형태로 우선순위 큐에 추가
(목표 지점에 도착하거나) 우선순위 큐가 비어있지 않을 때까지 반복 시작
우선순위 큐에서 가장 거리가 짧은 노드를 poll
if 현재 노드의 최단거리보다 꺼낸 노드의 최단거리가 크면 continue
꺼낸 노드를 현재 노드로 간주
현재 노드와 인접한 노드들 순회
현재 노드의 최단거리 + 간선 가중치가 인접 노드의 최단거리보다 작으면
인접 노드의 최단거리 갱신 후 (갱신된 거리, 노드) 형태로 우선순위 큐에 추가

A* (에이 스타)

현재 노드의 가중치 + 도착 지점까지의 예상 가중치로 최단 경로를 찾는 알고리즘입니다.
예상 가중치를 어떻게 설정하느냐에 따라 효율이 달라질 수 있습니다.

그래프 최적화 알고리즘

크루스칼, 프림 알고리즘 공통점
무방향 그래프에서 모든 노드들을 최소 비용 간선들로 연결하는 최소 스패닝 트리를 찾는 알고리즘들입니다.
음의 가중치가 있어도 정상 동작하고, 모든 간선의 가중치가 서로 다르면 MST는 항상 유일합니다.
가중치가 없는 그래프이거나, 최소 가중치 간선이 중복되면 MST가 유일하지 않을 수 있습니다.

크루스칼

간선 중심으로 확장하므로 시간복잡도는 O(E log E) 이고, 간선 수가 적은 희소 그래프에서 효율적입니다.

크루스칼 알고리즘 구현 방법
모든 간선을 가중치 기준으로 정렬한 뒤, 가장 낮은 가중치의 간선부터 순서대로 확인합니다.
Union-Find 알고리즘으로 사이클 여부를 판별하여 사이클이 생기지 않는 간선이면 트리에 추가합니다.
사이클이 생기는 간선은 제거하며, 트리의 간선 수가 노드 수 -1개가 될 때까지 반복합니다.

프림

정점 중심으로 확장하므로 시간 복잡도는 O(E log V) 이고, 정점 수가 적은 조밀 그래프에서 효율적입니다.

에드몬즈

가중치 방향 그래프에서 루트에서 출발하는 최소 비용 방향 트리를 구성하는 알고리즘입니다.
알고리즘 구현이 복잡해서 코딩테스트에서 나오는 경우는 거의 없다고 합니다.

그래프 알고리즘 보조 도구

Union-Find 알고리즘 (Disjoint Set Union, DSU)

그래프의 노드들이 같은 집합에 속하는지 효율적으로 판별할 수 있는 알고리즘입니다.
크루스칼 알고리즘, 무방향 그래프 사이클 존재여부 판별, 네트워크 수 계산, 원소 그룹 판별 문제 등에서 사용됩니다.

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]);
}

// 두 원소 집합을 연결하여 하나의 집합으로 합치는 함수
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 상향식 (Bottom-up 방식)
반복문으로 작은 문제부터 점진적으로 답을 구하는 방식입니다.
배열, ArrayList 등 DP 테이블에 타뷸레이션하며 점점 큰 문제의 답을 완성해 나갑니다.
재귀를 사용하지 않아 메모리 효율적입니다.

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 time) {
  // DP 테이블 초기화
  int[] dy = new int[time + 1]; // 각 시간으로 풀 수 있는 문제들의 최대 점수 저장 예정

  // 각 문제를 확인
  for (int i = 0; i < problemTimes.length; i++) {
    int problemTime = problemTimes[i];
    int problemScore = problemScores[i];

    // 제한 시간부터 현재 문제를 푸는데 걸리는 시간까지 반복
    for (int j = time; j >= problemTime; j--) {
      // (현재 시간 - 문제 시간)의 최대 점수 + 현재 문제 점수가
      // 현재 시간으로 풀 수 있는 다른 문제들의 최대 점수보다 크면 갱신
      dy[j] = Math.max(dy[j], dy[j - problemTime] + problemScore);
    }
  }

  // 제한 시간동안 풀 수 있는 문제들의 최대 점수 반환
  return dy[time];
}

각 문제는 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에 들어있는 숫자가 가장 유효한 값이 됩니다.

알고리즘 외 문제 유형

구현

문제의 조건에 따라 알고리즘으로 코드를 작성하는 문제 유형입니다.

시뮬레이션

주어진 상황을 이해하고 코드로 구현하는 문제이며, 알고리즘처럼 일반화한 방법으로 풀 수 없습니다.
배열 회전하기, 전치 행렬 만들기, 달팽이 수열 만들기 등의 문제가 있습니다.