Data Structure & Algorithm

스택과 큐에 대해 설명해본다면?
연결 리스트(Linked List)란?
그래프와 트리란?
이진 탐색 트리(Binary Search Tree, BST)란?
이진 탐색 트리의 연산에 대해 설명해본다면?
불균형한 이진 탐색 트리의 검색 연산을 보완하기 위한 방법은?
힙이란?
힙의 삽입과 삭제 연산에 대해 설명해본다면?
우선순위큐를 구현하는 방법에는 어떤 것들이 있을까?
해시 테이블(Hash Table)이란?
해시 값의 충돌을 해결하는 방법에는 어떤 것들이 있을까?

Algorithm

코딩 인터뷰 팁
정렬의 종류에는 어떤 것들이 있을까?
퀵 소트의 피벗 지정 방식을 어떻게 개선할 수 있을까?
n번째 피보나치 수를 구하는 방법은?
DFS와 BFS의 시간 복잡도는?

Data Structure

스택과 큐에 대해 설명해본다면?

스택

가장 마지막에 삽입된 데이터가 가장 먼저 제거되는 자료구조
변수 TOP이 스택의 가장 위를 가리키며, 이곳을 통해서만 삽입과 삭제가 이뤄진다.
삽입/삭제하는 연산 push와 pop을 메소드로 가진다.
활용 예시
- 웹 브라우저 방문 기록 구현
- 콜스택(Call Stack)
- 후위 표기법 계산
- 수식의 괄호 검사

후입선출(LIFO, Last-In-First-Out)

큐

가장 먼저 삽입된 데이터가 가장 먼저 제거되는 자료구조
삭제가 진행되는 front와 삽입이 진행되는 rear를 변수로 가진다.
삽입 연산 enqueue와 삭제 연산 dequeue를 메소드로 가진다.
활용 예시
- 우선순위가 같은 task 간 실행 순서 관리
- 프로세스 스케줄링
- BFS 구현

선입선출(FIFO, First-In-First-Out)

연결 리스트(Linked List)란?

연속적인 메모리 위치에 저장되지 않는 선형적인 자료구조
포인터(다음 노드에 대한 참조)를 통해 노드(데이터)가 연결된다.

단일 연결 리스트(Single Linked List), 다중 연결 리스트(Doubly Linked List) 등이 존재한다.

장점(배열과의 차이점)

배열은 고정된 크기로 할당이 되는 반면, 연결 리스트는 동적으로 노드를 추가할 수 있다.
배열은 중간 위치에 삽입, 삭제가 O(n)의 시간 복잡도를 가지지만, 연결 리스트는 O(1)의 시간 복잡도를 가진다.

배열은 인덱스로 특정 위치의 데이터에 빠르게 액세스할 수 있다. (시간 복잡도: O(1))

단점

임의의 데이터에 액세스를 허용하지 않아 순차적으로 탐색해야 한다. (시간 복잡도: O(n))
각 노드마다 포인터 값을 위한 메모리 공간이 추가로 필요하다.

그래프와 트리란?

그래프

정점(vertex)과, 정점을 연결하는 간선(edge)으로 구성된 자료구조
네트워크 모델이다.

네트워크 모델: 하위 데이터가 여러 개의 상위 데이터를 가질 수 있도록 표현된 데이터 구조

차수(degree): 한 정점에 연결된 간선의 수

방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)가 있다.

순환 그래프와 비순환 그래프(: 트리)가 있다.

간선에 비용이나 가중치가 할당된 경우 가중치 그래프(Weighted Graph)라 하며, '네트워크'라고도 한다.

트리

사이클이 존재하지 않는(비순환) 그래프
계층 모델이다.

계층 모델: 하나의 상위 데이터가 여러 개의 하위 데이터를 가질 수 있도록 표현된 데이터 구조

사이클(cycle): 한 정점에서 출발해 시작한 정점을 다시 돌아오는 경로

정점이 N개인 트리는 항상 N-1개의 간선을 가진다.

트리의 순회(traversal) 방법에는 preorder, inorder, postorder가 있다.

이진 탐색 트리(Binary Search Tree, BST)란?

정렬된 이진 트리
노드의 왼쪽 자식 트리에는 노드의 키보다 작은 키를 가지는 노드만 포함하며, 노드의 오른쪽 자식 트리에는 노드의 키보다 큰 키를 가지는 노드만 포함한다.

이진 탐색 트리는 중복된 키를 포함하지 않는다.

inorder 순회로 모든 키를 정렬된 순서로 가져올 수 있다.

Q. 이진 힙과 이진 탐색 트리의 차이점은? (용도, 연산의 시간 복잡도)

이진 탐색 트리의 연산에 대해 설명해본다면?

검색

루트에서 시작해, 루트보다 작으면 왼쪽 자식 트리에 대해 재귀를 돌리고, 루트보다 크면 오른쪽 자식 트리에 대해 재귀를 돌린다. 일치하는 값을 찾을 때까지 반복한다.
시간 복잡도: 이진 탐색 트리가 균형 상태일 경우 O(logn), 불균형 상태일 경우 최악의 경우에 O(n)(트리의 높이가 n)의 시간 복잡도를 가진다.

균형 상태: 루트로부터, 왼쪽 자식 트리의 높이와 오른쪽 자식 트리의 높이 차이가 1 이하인 상태.

삽입

루트에서 시작해, 루트보다 작으면 왼쪽 자식 트리에 대해 재귀를 돌리고, 루트보다 크면 오른쪽 자식 트리에 대해 재귀를 돌린다.
리프 노드에 도착한 후, 노드보다 작으면 왼쪽에, 노드보다 크면 오른쪽에 리프 노드로 삽입한다.

삭제

삭제할 노드가 리프 노드인 경우
- 해당 노드를 삭제한다.
삭제할 노드에게 자식 노드가 1개 있는 경우
- 노드를 삭제한 후, 자식 노드를 삭제한 노드의 부모 노드에 연결한다.
삭제할 노드에게 자식 노드가 2개 있는 경우
- successor 노드(후임자 노드)를 찾는다. successor 노드는 왼쪽 자식 트리의 가장 오른쪽 노드, 혹은 오른쪽 자식 트리의 가장 왼쪽 노드이다. (정하기 나름)
- 삭제할 노드와 successor 노드를 swap한다.
- 삭제하려 했던 노드를 삭제한다.

불균형한 이진 탐색 트리의 검색 연산을 보완하기 위한 방법은?

자가 균형 이진 탐색 트리를 활용하면 된다.

자가 균형 이진 탐색 트리란, 삽입과 삭제가 일어나는 경우에 자동으로 균형 상태를 유지하는 이진 탐색 트리를 말한다.
자가 균형 이진 탐색 트리에는 AVL 트리, 레드 블랙 트리, B tree 등이 있다.

힙이란?

최대값, 최소값을 빠르게 찾아내기 위해 고안된 완전 이진 트리.
힙의 종류에는 최대 힙(max heap)과 최소 힙(min heap)이 있다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다. 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다.
배열을 통해 쉽게 구현할 수 있다.

힙은 우선순위큐를 구현하는 데 사용될 수 있다.

힙은 중복된 값을 허용한다. 반면 이진 탐색 트리는 중복된 값을 허용하지 않는다.

형제 노드 간에는 우선순위의 대소관계가 정해지지 않는다. 이러한 특성을 '반정렬 상태'라고 한다.

구현을 쉽게 하기 위해 배열의 첫번째 인덱스([0])은 사용되지 않는다.

힙은 일반적으로 이진 힙을 가리킨다.

이진 트리: 각각의 노드가 최대 2개의 노드를 가지는 트리.

완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 왼쪽에 위치한 이진 트리.

힙의 삽입과 삭제 연산에 대해 설명해본다면?

삽입

배열의 마지막에 새로운 데이터를 삽입한다.
삽입된 데이터의 우선순위가 부모 노드의 값보다 높지 않을 때까지 swap한다. (: shiftUp())
O(logN)의 시간 복잡도를 가진다.

삭제

배열의 첫번째 원소와 마지막 원소를 swap한다.
배열의 마지막 원소를 삭제한다.
배열의 첫번째 원소에 대해, 우선순위가 자식 노드의 값보다 낮지 않을 때까지 swap한다. (: shiftDown())
O(logN)의 시간 복잡도를 가진다.

우선순위큐를 구현하는 방법에는 어떤 것들이 있을까?

배열, 연결 리스트, 힙으로 구현할 수 있다.
배열과 연결 리스트는 삭제 연산의 시간 복잡도에서 우위를 점하지만, 힙의 삽입 연산 시간 복잡도가 월등하기 때문에 힙으로 구현한다.

배열

삽입: 위치를 찾기 위해 순차적으로 데이터를 순회해야 하며, 중간에 삽입할 경우 원소들을 뒤로 하나씩 미뤄야 하므로 O(n)의 시간 복잡도를 가진다.
삭제: 가장 첫번째 원소를 반환하면 되므로 O(1)의 시간 복잡도를 가진다.

연결 리스트

삽입: 위치를 찾기 위해 순차적으로 데이터를 순회해야 하므로 O(n)의 시간 복잡도를 가진다.
삭제: 가장 첫번째 노드의 값을 반환하면 되므로 O(1)의 시간 복잡도를 가진다.

힙

삽입과 삭제: 우선순위에 따른 위치를 탐색할 때 부모와 자식 간의 비교만 이뤄진다. 트리의 높이가 증가할 때마다 저장 가능한 데이터의 개수가 2배씩 증가하므로, 삽입과 삭제 모두 O(log2n)의 시간 복잡도를 가진다.

우선순위큐: 들어간 순서와 상관 없이 우선순위가 높은 데이터 먼저 삭제되는 큐

해시 테이블(Hash Table)이란?

key와 value의 형태로 데이터를 저장하는 자료구조
평균적으로 상수 시간 내에 삽입, 삭제, 검색을 수행할 수 있다.

해시(hash, hash value): 임의의 데이터로부터 해시 함수를 통해 출력(매핑)된 데이터.

해시 함수(hash function): 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 것.

입력값이 같으면 출력값도 같다.

고정된 길이의 반환값을 가진다.

출력값을 토대로 입력값을 계산할 수 없어야 한다.

해시의 충돌: 서로 다른 두 개 이상의 키가 동일한 위치(동일한 해시값)을 가지는 경우를 말한다.

삽입, 삭제, 검색 연산은 평균 O(1), 최악의 경우 O(n)의 시간 복잡도를 가진다.

해시 값의 충돌을 해결하는 방법에는 어떤 것들이 있을까?

Chaining 방식과 Open Addressing 방식이 있다.

Chaining

테이블의 각 요소를 연결 리스트로 구성한다.
충돌이 발생했을 경우, 새로 들어온 값을 연결 리스트의 가장 앞 노드로 추가한다.

연결 리스트는 선형 자료구조로, 삽입, 삭제, 검색 연산의 시간 복잡도가 최악의 경우 O(n)이다. 이를 개선하기 위해 각 요소를 연결 리스트 대신 이분 탐색 트리로 구성할 수 있다. 이 경우 시간 복잡도는 평균적으로 O(logn)이 된다.
(물론 이분 탐색 트리도 최악의 경우 O(n)의 시간 복잡도를 보일 수 있으며, 이는 자가 균형 이분 탐색 트리를 활용해 개선할 수 있다.)

Open Addressing

(별도의 저장 공간을 늘리지 않고) 충돌이 발생한 경우 빈 공간을 찾을 때까지 탐색한다.
3가지 방법이 있다: 선형 조사, 이차원 조사, 이중 해싱

선형 조사(Linear Probing)

충돌이 발생한 경우 충돌한 자리의 다음 값(혹은 i를 더한 다음 값)을 확인한다.
특정 구간에 원소들이 몰리는 '1차 군집(primary clustering)' 현상이 발생한다. (군집의 크기가 확장되면 연산 성능이 저하된다.)

선형 조사의 방정식: h_k = (h(x) + i) mod m

삭제 연산 시, 값을 삭제한 후 해당 자리에 값이 존재했었다는 것을 표시(DELETED 등)해야 한다. 그렇지 않으면 선형 조사 중 중간에 빈 공간을 발견해, 실제로 존재하는 값임에도 존재하지 않는 것으로 판단할 수 있다.

이차원 조사(Quadratic Probing)

충돌이 발생한 경우 이차 함수 값만큼 크기를 늘려가며 빈 공간을 탐색한다.
군집을 빠르게 탈출할 수 있다.
그러나 선형 조사와 마찬가지로, 초기 해시값이 동일하면 '2차 군집(secondary clustering)' 현상을 겪는다.

이차원 조사의 방정식: h_k(x) = h(x) + C1*i^2 + C2*i

더블 해싱(Double Hashing)

두개의 해시 함수를 사용해 빈 공간을 탐색한다.
첫 번째 해시 함수 값이 같아도, 두 번째 해시 함수로 인해 완전히 다른 해시값이 생성된다.
군집 현상이 발생하지 않는다.

더블 해싱의 방정식: h_k(x) = (h(x) + i*f(x)) mod m

Algorithm

코딩 인터뷰 팁

Reference: https://www.mtu.edu/career/students/networking/interviews/prepare.pdf

Q. 문제를 어떻게 풀어야 할까?

면접관에게는 언제든 질문해도 괜찮다.
문제를 풀어보라는 지시를 받으면, 처음에는 바로 풀어보기 전에 먼저 문제를 정의하고 분석해야 한다.
만약 잘 이해가 되지 않는다면, 면접관에게 도움을 청하거나 더 구체적인 설명을 요구해야 한다.
만약 문제를 푸는 과정에서 무언가 추론을 해야할 일이 생긴다면, 추론한 내용을 말로 표현하고 면접관에게 해당 내용이 맞는지 확인해야 한다.
문제의 각 파트에 대해 어떻게 생각하고 있고, 어떻게 문제를 해결해나가고 있는지 끊임없이 설명해야 한다. 그래야 면접관이 문제를 접근 방식과 생각의 흐름에 관심을 가질 수 있기 때문이다. 또한, 그래야 문제를 풀다가 막혔을 때 그 사실을 면접관이 알 수 있고, 적절한 힌트를 제공해줄 수 있기 때문이다.
면접관이 제공하는 힌트를 절대 놓치지 않도록 주의를 기울여야 한다.

Q. 면접관이 보고자 하는 것은 무엇일까?

면접관들은 지원자의 '대답'만큼, 지원자의 '질문'에도 관심을 가진다.

문제를 잘 듣고, 이해하는가?
문제 푸는 것을 진행하기 전에 올바른 질문을 던지는가?
brute-force 방식으로 문제에 접근하지는 않는가?
제대로 체크하기 전에 섣불리 추론하지는 않는가?
문제를 이해하거나 푸는 데 너무 오래 걸리지는 않는가?
지원자가 최선의 답변을 선택하기 전에, 여러 해결책을 내놓는 과정을 즐기고 있는가?
문제를 풀기 위한 새로운 방법이나 아이디어가 발견되었는가?
지원자가 창의적이고 유연한 해결책을 내놓으며, 새로운 아이디어에 열려있는가?

정렬의 종류에는 어떤 것들이 있을까?

거품 정렬(Bubble sort)

서로 인접한 두 원소의 대소를 비교하고 교환하는 알고리즘
매 순회마다 가장 큰 원소가 맨 뒤부터 순차적으로 쌓인다.

function bubbleSort(arr) {
  let temp;

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 1; j < arr.length - i; j++) {
      if (arr[j - 1] > arr[j]) {
        [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]]; // swap
      }
    }
  }
}

분석

시간 복잡도: (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 이므로, O(n^2)
공간 복잡도: 주어진 배열 안에서 swap을 통해 정렬이 수행되므로, O(n)

장점

구현이 간단하고 직관적이다.
제자리 정렬로, 다른 메모리 공간을 필요로 하지 않는다.
안정 정렬(stable sort)이다.

단점

비효율적 시간 복잡도
정렬되어 있지 않은 원소가 제자리를 찾아가기 위해 swap 연산이 많이 발생한다.

--

선택 정렬(Selection sort)

매 순회마다 원소를 집어넣을 위치를 정해놓고, 어떤 원소를 넣을지 선택하는 알고리즘

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // i: 원소를 집어넣을 위치의 인덱스
    let minIdx = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j; // 가장 작은 값을 찾는다.
      }
    }

    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; // swap
  }
}

분석

시간 복잡도: (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 이므로, O(n^2)
공간 복잡도: 주어진 배열 안에서 swap을 통해 정렬이 수행되므로, O(n)

장점

구현이 간단하고 직관적이다.
정렬을 의한 비교 횟수는 많으나, 교환 횟수가 적어 효율적이다.
역순으로 정렬되어 있는 배열을 정렬할 때 좋은 효율을 보인다.
제자리 정렬로, 다른 메모리 공간을 필요로 하지 않는다.

단점

비효율적 시간 복잡도
이미/거의 정렬되어 있는 배열을 정렬할 때 최악의 처리 속도를 보인다.
불안정 정렬(unstable sort)이다.

--

삽입 정렬(Insertion sort)

2번째 원소부터 시작해, 매 순회마다 각 원소가 들어갈 위치를 찾아 삽입하는 알고리즘

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i]; // 현재 원소를 저장해놓는다.
    let prev = i - 1; // 원소를 삽입할 자리

    // 현재 원소보다 큰 값들을 모두 한 칸씩 뒤로 옮긴다.
    while (prev >= 0 && arr[prev] > arr[i]) {
      arr[prev + 1] = arr[prev];
      prev--;
    }

    // 자기보다 작은 값 바로 뒤에 원소를 삽입한다.
    // 그 자리의 값은 한칸씩 미뤄져있어 비어있는 것과 마찬가지이다.
    arr[prev + 1] = temp;
  }
}

분석

시간 복잡도
- 평균의 경우와 최악의 경우(역순으로 정렬되어 있을 때): (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 이므로, O(n^2)
- 최선의 경우(거의 정렬되어 있는 경우): 각 순회마다 거의 단 한번씩 비교하므로 O(n)
공간 복잡도: 주어진 배열 안에서 swap을 통해 정렬이 수행되므로, O(n)

장점

구현이 간단하고 직관적이다.
대부분의 원소가 거의 정렬되어 있는 경우 매우 효율적인 알고리즘이다. (이미 정렬된 요소는 한 번의 비교만 수행하고 교환 연산은 발생하지 않는다.)
크기가 작은 배열에 대해 성능이 좋다.
제자리 정렬이다.
안정 정렬이다.
- 선택 정렬은 각 순회마다 적절한 원소를 선택하기 위해 모든 원소를 탐색하지만, 삽입 정렬은 필요한 만큼만 탐색하므로 비교적 더 효율적이다.

단점

평균/최악의 경우 비효율적인 시간 복잡도

--

퀵 정렬(Quick sort)

피벗(pivot)을 기준으로 배열을 분할해, 재귀적으로 더 작은 단위의 배열을 정렬해나가는 알고리즘

분할 정복(Divide and Conquer)을 사용하는 정렬 알고리즘이다. 분할 정복이란 큰 문제를 작은 단위의 문제로 쪼개어 해결해나가는 방식이다.

피벗을 선택하는 방법에는 여러가지가 있다(첫번째 요소를 선택, 중간 요소를 선택, 마지막 요소를 선택, 랜덤으로 선택 등). 피벗 선택 방식은 시간 복잡도에 큰 영향을 줄 수 있다.

병합 정렬(Merge sort)와 비교했을 때, 퀵 소트는 배열을 비균등하게 분할한다는 차이점이 있다.

function quickSort(arr, left, right) {
  if (left >= right) {
    return;
  }

  const pivot = partition(arr, left, right);

  quickSort(arr, left, pivot - 1);
  quickSort(arr, pivot + 1, right);
}

function partition(arr, left, right) {
  let pivot = arr[left]; // 첫번째 요소를 피벗으로 설정하는 방식
  let i = left,
    j = right;

  while (i < j) {
    // 오른쪽에서 왼쪽으로 가면서, 피벗보다 작은 값을 찾는다.
    while (pivot < arr[j]) {
      j--;
    }

    // 왼쪽에서 오른쪽으로 가면서, 피벗보다 큰 값을 찾는다.
    while (i < j && pivot >= arr[i]) {
      i++;
    }

    [arr[i], arr[j]] = [arr[j], arr[i]]; // swap
  }

  // 마지막으로 첫번째 요소와 피벗값을 교환한다.
  // 이로써 피벗의 왼쪽에는 피벗보다 작은 값만, 피벗의 오른쪽에는 피벗보다 큰 값만 존재하게 된다.
  arr[left] = arr[i];
  arr[i] = pivot;

  return i;
}

분석

시간 복잡도
- 평균: 배열의 파티션이 균등하게 분할(2분할)된다고 가정했을 때, 재귀 호출 횟수는 logn번이다. 각 호출 횟수에서 n/2번의 비교 연산을 수행한다. 따라서 O(logn * n/2) = O(logn * n) 이므로 O(nlogn).
- 최악의 경우: 이미 거의 정렬되어 있거나, 역순으로 정렬되어 있는 경우이다(더 일반적으로 말하자면, 피벗값이 매번 최소, 혹은 최대값으로 지정되어 파티션이 나뉘어지 않는 상황이라 볼 수 있다). 재귀 호출 횟수가 n번, 각 호출 횟수에서 n/2번의 비교 연산을 수행하므로 O(n*n) = O(n^2)이다.
공간 복잡도: 주어진 배열 안에서 swap을 통해 정렬이 수행되므로, O(n)

장점

O(nlogn)의 효율적인 시간 복잡도
(O(nlogn)의 시간 복잡도를 가지는 다른 정렬 알고리즘에 비해서도 더 효율적인 편에 속한다. 먼 거리의 요소를 비교/swap한다는 점과, 한번 피벗으로 설정된 요소는 이후에는 비교/swap에서 제외된다는 점에서 그렇다.)
제자리 정렬이다.

단점

최악의 경우 비효율적인 시간 복잡도(단, 개선이 가능하다.)
불안정 정렬이다.

--

병합(합병) 정렬(Merge sort)

배열을 쪼갤 수 있는 만큼 쪼갠 후, 순서를 정렬해가며 다시 병합하는 알고리즘.

분할 정복(Divide and Conquer)을 사용하는 정렬 알고리즘이다.

function mergeSort(arr, left, right) {
  if (left < right) {
    const mid = (left + right) / 2;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}

function merge(arr, left, mid, right) {
  const L = arr.slice(left, mid + 1);
  const R = arr.slice(mid + 1, right + 1);

  let i = 0,
    j = 0,
    k = left;

  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) {
      arr[k++] = L[i++];
    } else {
      arr[k++] = R[j++];
    }
  }

  // remain
  while (i < L.length) {
    arr[k++] = L[i++];
  }
  while (j < R.length) {
    arr[k++] = R[j++];
  }
}

분석

시간 복잡도: 매 순회마다 1/2의 크기로 배열을 분할하므로, mergeSort()가 재귀적으로 logn번 호출, 각 호출에서 n개의 원소를 순회하며 정렬을 진행하므로 O(logn * n) = O(nlogn)
공간 복잡도: 병합 과정에서 추가 배열이 필요하다. 상수항 제거로, O(n)

장점

효율적인 시간 복잡도
데이터의 특성과 별개로 일정한 시간 복잡도 O(nlogn)를 보인다.
순차적으로 데이터를 비교하며 정렬하기 때문에, 연결 리스트를 정렬할 때 효율적이다. (반면 퀵 소트는 임의 접근으로, 연결 리스트를 정렬할 때 비효율적이다. 연결 리스트는 삽입과 삭제 연산은 효율적이지만 탐색/접근 연산은 O(n)으로 비효율적이기 때문이다.)
안정 정렬이다.

단점

제자리 정렬이 아니다.
이동 횟수가 많아, 레코드의 크기가 큰 경우 상대적으로 시간이 더 소요된다.

--

힙 정렬(Heap sort)

최대 힙 트리, 또는 최소 힙 트리를 구축해 정렬을 수행하는 알고리즘

오름차순을 위해서는 최대 힙을, 내림차순을 위해서는 최소 힙을 구축한다.

힙 생성 알고리즘(heapify algorithm)은 하나의 특정 노드에 대해서만 수행하는 알고리즘이며, 해당 노드를 제외하고는 최대/최소 힙이 구성되어 있는 상태라는 전제가 필요하다. 특정 노드의 두 자식 노드 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다.

보통 힙을 구성할 때는 노드 조작을 편리하게 하기 위해 첫번째 인덱스를 비워둔다(인덱스 1부터 시작). 그러나 힙 정렬은 기존 배열을 정렬해야 하므로, 인덱스 0부터 시작한다.

힙 정렬 과정(오름차순 기준)

오름차순일 경우, 기존 배열로 최대 힙을 구성한다.
- 최소 힙은 그 자체로 오름차순 배열이 되지 못한다. 반정렬 상태이기 때문이다.
- 가장 작은 서브 트리부터 순차적으로 최대 힙을 만족하도록 구성한다. 루트를 부모로 가지는 가장 큰 서브 트리를 마지막으로 전체 배열이 최대 힙을 만족하게 된다. (가장 작은 서브 트리의 루트는 가장 마지막 노드의 부모 트리이다.)
- 특정 서브 트리에서 부모-자식 교환이 일어났을 경우, 교환된 자식 노드의 서브 트리에서 (재귀적으로, 혹은 순차적으로) 다시 heapify를 수행한다.
루트 노드를 순차적으로 pop해, 배열의 맨 뒤부터 차례대로 삽입한다.

const parent = (i) => (i - 1) / 2;
const left = (i) => i * 2 + 1;
const right = (i) => i * 2 + 2;

function heapSort(arr) {
  if (size < 2) return;

  // 가장 마지막(오른쪽 끝) 서브 트리의 부모 노드부터 시작해,
  // 루트 노드까지 순회하며 재귀적으로 heapify를 수행한다.
  for (let parentIdx = parent(arr.length - 1); parentIdx >= 0; parentIdx--) {
    heapify(arr, parentIdx, arr.length);
  }

  // 루트 노드와 마지막 요소를 교환함으로써,
  // 배열의 맨 뒤부터 가장 값이 큰 요소로 채운다.
  // (해당 노드는 다음 순회에서 제외된다)
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, 0, i - 1);
  }
}

function heapify(arr, parentIdx, lastIdx) {
  // 자식 인덱스가 마지막 인덱스를 넘지 않을 때까지 반복.
  // 단, 왼쪽 자식 인덱스를 기준으로 해야 왼쪽 자식이 마지막 인덱스인 경우를 조건에 포함할 수 있다.
  while (
    left(parentIdx) <= lastIdx &&
    // 부모 노드보다 더 큰 자식이 있을 때
    (arr[left(parentIdx)] > arr[parentIdx] ||
      (right(parentIdx) <= lastIdx && arr[right(parentIdx)] > arr[parentIdx]))
  ) {
    const greaterChildIdx =
      right(parentIdx) <= lastIdx &&
      arr[right(parentIdx)] > arr[left(parentIdx)]
        ? right(parentIdx)
        : left(parentIdx);

    // swap
    [arr[parentIdx], arr[greaterChildIdx]] = [
      arr[greaterChildIdx],
      arr[parentIdx],
    ];
    parentIdx = greaterChildIdx;
  }
}

분석

시간 복잡도
- heapify를 통해 최대/최소 힙을 구성하는 시간: 부모 노드의 개수는 n/2(소수점 절삭), heapify는 최대 트리의 높이만큼 수행하므로 logn의 시간이 소요된다. 따라서 n/2*logn ~= nlogn
- 루트를 배열 끝으로 넘기고 heapify를 수행하는 시간: 모든 요소에 대해 heapify를 수행하므로, nlogn
- 따라서, 시간 복잡도는 O(nlogn + nlogn) = O(nlogn)
공간 복잡도: 제자리 정렬로, O(n)

장점

효율적인 시간 복잡도
최악의 경우에도 O(nlogn)의 시간 복잡도를 보인다.
정렬된 상태의 전체 배열이 아니라, 가장 크거나 작은 값 몇개만 필요할 때 더 효율적이다.
제자리 정렬이다.

단점

일반적인 O(nlogn) 정렬 알고리즘에 비해 비교적 성능이 떨어진다.
불안정 정렬이다(최대/최소 힙을 구성하는 과정에서 불안정 정렬 상태가 된다).

퀵 소트의 피벗 지정 방식을 어떻게 개선할 수 있을까?

난수 분할

피벗이 항상 편향되는 최악의 경우를 방지하기 위해 피벗 값을 매번 랜덤한 위치에서 지정한다. (이미 정렬된 배열이 들어왔을 때, 항상 편향된 피벗을 선택하게 되는 위험을 방지할 수 있다.)

세 값의 중위(Median of Three)

배열의 가장 첫번째 인덱스, 마지막 인덱스, 중간 인덱스를 선택한 후, 그 중 중간에 있는 값을 피벗으로 지정한다.

(피벗 지정 방식과 별개) 특정 크기 미만으로 분할된 배열부터는 삽입 정렬을 수행하는 방식으로 퀵 소트를 개선할 수 있다. 재귀 호출되는 깊이를 줄여줘 메모리를 절약할 수 있으며, 삽입 정렬은 크기가 작은 배열에 대해 성능이 좋으므로 시간도 절약할 수 있다.

n번째 피보나치 수를 구하는 방법은?

피보나치 수열: 첫번째, 두번째 항이 1이며, 그 뒤 모든 항은 바로 앞 두 항의 합인 수열.

처음 두 항은 1, 1이며, 편의상 0번째 항을 0으로 두기도 한다.

재귀적 풀이

피보나치 수의 함수적 정의를 그대로 구현한 방법.

function fibo(n) {
  if (n < 2) return n;

  return fibo(n - 1) + fibo(n - 2);
}

분석

시간 복잡도: 함수가 한 번 호출될 때마다 함수가 두 번 다시 재귀적으로 호출되므로, 지수적으로 증가해 O(2^n)이 된다.

--

반복적 풀이

0번째, 1번째 피보나치 수부터 계속 더하는 식으로 피보나치 수를 구할 수 있다.

function fibo(n) {
  if (n < 2) return n;

  let a = 0,
    b = 1;

  for (let i = 0; i < n; i++) {
    b = a + b;
    a = b;
  }

  return b;
}

분석

시간 복잡도: n번의 반복으로 피보나치 수를 구할 수 있다. O(n)

--

동적 계획법(DP)를 활용한 풀이

재귀적 풀이에서 중복되는 sub problem이 계속 나타난다. 이를 메모이제이션으로 해결하는 방법.

function fibo(n) {
  if (n < 2) return n;

  const DP = [0, 1];

  for (let i = 2; i <= n; i++) {
    DP[n] = DP[n - 1] + DP[n - 2];
  }

  return DP[n];
}

분석

시간 복잡도: O(n)

행렬 곱셈을 이용한 풀이와 일반항을 이용한 풀이도 존재한다. 이 두 방법들은 O(logn)만에 피보나치 수를 구할 수 있다.

DFS와 BFS의 시간 복잡도는?

DFS(깊이 우선 탐색): 다음 브랜치로 넘어가기 전에 현재 브랜치를 모두 탐색하고 넘어가는 탐색. stack이나 재귀로 구현할 수 있다.

BFS(너비 우선 탐색): 시작 노드를 방문 후, 해당 노드와 인접한 모든 노드를 우선적으로 방문하는 탐색. queue로 구현할 수 있다.

구현 방법에 따라 시간 복잡도가 다르다.

인접 행렬(adjacent matrix)로 구현

각 DFS(v)는 모든 정점을 순회하며 연결된 정점을 확인하므로 O(V)의 시간 복잡도를 가진다.
DFS(v)가 총 정점의 개수 V만큼 호출되므로, 최종 시간 복잡도는 O(V^2)가 된다.
- 인접 행렬: 그래프 이론에서 어느 정점들이 간선으로 연결되었는지를 나타내는 정사각 행렬

인접 리스트(adjacent list)로 구현

모든 정점을 한 번씩 방문하고, 각 정점에 연결된 간선을 한 번씩 검사하므로 O(V+E)의 시간 복잡도를 가진다. (인접 행렬을 사용한 구현과 다르게 DFS(v)가 일정한 시간 복잡도를 가지지 않는다. 정점마다 연결된 간선의 수가 각각 다르기 때문이다.)
- 인접 리스트: 그래프 이론에서, 한 정점에 연결된 다른 정점들을 연결 리스트로 표현하는 방법

인접 행렬은 정점의 수가 많은 그래프, 인접 리스트는 정점의 수가 적은 그래프에 효율적이다.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

Data Structure & Algorithm

Table of Contents

Data Structure

스택과 큐에 대해 설명해본다면?

연결 리스트(Linked List)란?

그래프와 트리란?

이진 탐색 트리(Binary Search Tree, BST)란?

이진 탐색 트리의 연산에 대해 설명해본다면?

불균형한 이진 탐색 트리의 검색 연산을 보완하기 위한 방법은?

힙이란?

힙의 삽입과 삭제 연산에 대해 설명해본다면?

우선순위큐를 구현하는 방법에는 어떤 것들이 있을까?

해시 테이블(Hash Table)이란?

해시 값의 충돌을 해결하는 방법에는 어떤 것들이 있을까?

Algorithm

코딩 인터뷰 팁

정렬의 종류에는 어떤 것들이 있을까?

퀵 소트의 피벗 지정 방식을 어떻게 개선할 수 있을까?

n번째 피보나치 수를 구하는 방법은?

DFS와 BFS의 시간 복잡도는?

Files

README.md

Latest commit

History

README.md

File metadata and controls

Data Structure & Algorithm

Table of Contents

Data Structure

스택과 큐에 대해 설명해본다면?

연결 리스트(Linked List)란?

그래프와 트리란?

이진 탐색 트리(Binary Search Tree, BST)란?

이진 탐색 트리의 연산에 대해 설명해본다면?

불균형한 이진 탐색 트리의 검색 연산을 보완하기 위한 방법은?

힙이란?

힙의 삽입과 삭제 연산에 대해 설명해본다면?

우선순위큐를 구현하는 방법에는 어떤 것들이 있을까?

해시 테이블(Hash Table)이란?

해시 값의 충돌을 해결하는 방법에는 어떤 것들이 있을까?

Algorithm

코딩 인터뷰 팁

정렬의 종류에는 어떤 것들이 있을까?

퀵 소트의 피벗 지정 방식을 어떻게 개선할 수 있을까?

n번째 피보나치 수를 구하는 방법은?

DFS와 BFS의 시간 복잡도는?