CS 면접 및 코딩테스트를 위한 알고리즘 개념 정리

2024-05-10

알고리즘 도감 앱에서 알고리즘의 동작을 그림으로 쉽게 이해할 수 있습니다.

정렬 알고리즘

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

버블 정렬

끝에서부터 서로 인접한 두 원소를 비교하며 순서를 정렬하는 알고리즘입니다.
코드가 단순하지만, 시간복잡도가 O(n²)으로 매우 느립니다.

버블 정렬 예시

배열의 한쪽 끝에서 두 원소를 비교하고, 순서에 맞지 않으면 위치를 교환합니다.
다음 원소로 이동하며 인접한 두 원소의 비교 및 교환을 반복합니다.
반대쪽 끝의 정렬된 원소들을 제외하고, 모두 정렬될 때까지 반복합니다.

선택 정렬

리스트에서 최소값을 선택하고 맨 앞에 위치한 값과 교환하며 정렬하는 알고리즘입니다.
정렬되지 않은 데이터가 많을수록 성능이 떨어지며, 시간복잡도가 O(n²) 입니다.

선택 정렬 예시

배열을 선형 탐색하여 최소값을 선택하고, 왼쪽 끝 숫자와 위치를 교환합니다.
다음 최소값을 선택하여 왼쪽 끝+1 숫자와 위치를 교환합니다.
왼쪽 끝의 정렬된 원소들을 제외하고, 모두 정렬될 때까지 반복합니다.

삽입 정렬

각 원소를 왼쪽 원소들과 비교하며 적절한 위치에 삽입하는 알고리즘입니다.
현재 정렬이 역순인 경우, 비교 및 교환이 많아져서 시간복잡도가 O(n²) 입니다.
이미 정렬된 원소가 많은 상태에서는 빠르게 동작합니다.

삽입 정렬 예시

두 번째 원소가 왼쪽 원소보다 값이 작으면 위치를 교환합니다.
세 번째 원소도 왼쪽(-1) 원소들과 순차 비교하며, 값이 작을 때마다 위치를 교환합니다.
모두 정렬될 때까지 반복하여, 각 원소를 적절한 위치에 삽입합니다.

힙 정렬

힙 자료구조를 사용하여 정렬하는 알고리즘이며, 시간복잡도는 O(nlogn)입니다.

힙 정렬 예시

배열을 최대힙으로 구성하고, 최대힙의 첫번째 원소 (가장 큰 수) 를 꺼내서 마지막 원소와 교환합니다.
마지막 원소를 제외한 나머지 원소들로 다시 최대 힙을 만들고, 첫번째 원소를 꺼내서 마지막-1 원소와 교환합니다.
오른쪽 끝의 정렬된 원소들을 제외하고, 모두 정렬될 때까지 반복합니다.

병합 정렬

분할 후 각각 재귀적으로 정렬하며 병합하는 알고리즘이며, 시간복잡도는 O(nlogn) 입니다.
분할 정복 알고리즘의 일종입니다.

병합 정렬 예시

배열을 반씩 분할해나갑니다.
분할된 각 그룹의 선두 숫자 비교 후 작은 숫자 이동을 반복하여, 오름차순으로 병합합니다.
정렬된 하나의 그룹이 될 때까지 각 그룹의 정렬 및 병합을 재귀적으로 반복합니다.

퀵 정렬

비교 및 교환 횟수가 적어서 평균 시간복잡도가 O(nlogn)으로 빠른 알고리즘입니다.
거의 정렬된 배열에서는 시간복잡도가 O(n²)으로 성능이 좋지 않습니다.

퀵 정렬 예시

정렬 기준이 되는 피봇(pivot) 숫자를 랜덤으로 선택합니다.
피봇 원소, 가장 왼쪽 원소, 가장 오른쪽 원소에 각각 마커를 표시합니다.
왼쪽 마커를 오른쪽으로 이동하다가 피봇보다 크거나 같은 원소에서 멈춥니다.
오른쪽 마커를 왼쪽으로 이동하다가 피봇보다 작은 원소에서 멈춥니다.
각 마커의 숫자를 교환합니다. 각 마커 위치가 같다면, 피봇 숫자와 위치를 교환합니다.
피봇의 왼쪽에는 피봇보다 작은 숫자들, 피봇의 오른쪽에는 피봇보다 큰 숫자들이 위치하게 됩니다.
둘로 나누어진 배열에 대해 위 작업을 재귀적으로 반복힙니다.
왼쪽 마커가 작업 대상의 오른쪽 끝에 도달한다면, 피봇을 정렬 완료 상태로 두고 다음 작업으로 넘어갑니다.

리스트 탐색 알고리즘

선형 탐색

배열의 앞에서부터 순차적으로 원소를 하나씩 비교하며 찾는 알고리즘입니다.
시간복잡도는 배열의 크기에 비례하여 O(n) 입니다.

이분 탐색 (이진 탐색)

정렬된 배열에서 중간 원소를 기준으로 탐색 범위를 반씩 줄여나가며 찾는 알고리즘입니다.
시간복잡도는 O(logn) 입니다.

이분 탐색 예시

오름차순으로 정렬된 배열에서 정 중앙의 원소와 탐색할 데이터를 비교합니다.
탐색할 데이터가 더 크면, 좌측의 원소들은 후보에서 제외합니다.
우측의 원소 중에서 정 중앙의 원소를 찾고, 비교 및 탐색 범위 제외를 반복합니다.

그래프 탐색 알고리즘

너비 우선 탐색 (BFS) ★

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

큐로 BFS 구현 예시

큐에 그래프의 시작 노드 add
큐 반복 시작
if 큐가 비어있다면 탐색 종료
큐에서 노드를 poll 하고 방문 여부 확인 후 방문 처리
현재 노드와 인접한 노드 중 방문하지 않은 노드들을 큐에 add

깊이 우선 탐색 (DFS) ★

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

스택으로 DFS 구현 예시

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

벨만-포드

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

다익스트라

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

다익스트라 예시

현재 노드의 가중치를 0, 모든 노드의 가중치를 무한으로 설정
시작 노드를 우선순위 큐에 추가
우선순위 큐 반복 시작
if 우선순위 큐가 비어있다면 탐색 종료
현재 노드와 인접한 노드 중 아직 방문하지 않은 노드들을 우선순위 큐에 추가
현재 노드의 가중치 + 후보 노드까지의 가중치가 후보 노드의 가중치보다 작으면 갱신
가중치가 갱신된 노드들을 우선순위 큐에 추가
목표 지점에 도착하거나 큐가 비어있지 않을 때까지 반복

A* (에이 스타)

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

문제 해결 알고리즘

코딩테스트에서 자주 나오는 문제 해결 알고리즘들입니다.

백트래킹

모든 경우의 수를 탐색하는 완전탐색과 달리, 답이 될 가능성이 없는 노드에서 탐색을 배제하고 되돌아가는 알고리즘입니다.
백트래킹은 주로 DFS를 기반으로 재귀적으로 구현되고, 완전탐색보다 효율적입니다.

동적계획법 (DP)

작은 부분 문제들로 나누어 해결한 것으로 전체 문제를 해결하는 알고리즘입니다.
동일한 작은 문제가 반복되고, 작은 문제들의 결과를 재사용하여 해결이 가능한 경우 사용합니다.
단순히 작은 문제를 조합해서 큰 문제를 해결하는 분할 정복 알고리즘과는 다릅니다.

재귀를 활용한 DP 구현 예시

종료 조건을 설정합니다.
재귀로 반복할 수 있는 점화식을 세웁니다.
작은 문제의 결과를 메모이제이션 기법으로 저장하여 중복 계산을 피합니다.

그리디 (Greedy)

문제 해결 과정에서 눈 앞에 보이는 최선의 선택만을 하며, 선택은 번복하지 않는 알고리즘입니다.
각 선택이 부분해 및 최적해를 구하는 과정과 일치하고, 전체 문제 해결에는 영향이 없을 때 사용해야 합니다.

알고리즘 외 문제 유형

구현

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

시뮬레이션

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