JavaScript의 자료구조와 알고리즘

서문

비록 스스로 노력하고 대기업에 들어간 경험이 있지만, 컴퓨터 과학 기초 분야는 항상 부족함을 느꼈습니다. 전공자가 아니기 때문에, 후천적인 노력으로 전공자들과의 격차를 좁히고 싶었습니다. 프로그래머의 세 가지 꿈(언어/알고리즘/그래픽) 중 하나인 자료구조와 알고리즘은 항상 마음의 부담이었습니다. 여유 시간에 기술 커뮤니티를 돌아다니다가 자극적인 자료구조 및 알고리즘 관련 제목에 끌려 들어가곤 했지만, 내용은 허전한 경우가 많았습니다. 결국 알고리즘(기초)을 제대로 공부하기로 마음먹었습니다.

이 글은 제가 공부한 내용을 정리한 것으로, <자바스크립트 자료구조와 알고리즘 학습(제2판)>을 보며 요약하고 메모한 것입니다. 먼저 자료구조부터 시작한 후, 다양한 자료구조 알고리즘을 다룹니다. 대부분 ES5 방법을 사용하며, 일부는 ES6 방법을 사용합니다. 효과 구현에 집중하며, 실행 비용과 같은 비관련 요소(예: 프로토타입 체인 대신 각 인스턴스에 메서드 추가 등)는 고려하지 않습니다.

스택

스택의 기본 개념과 메서드

스택은 후입선출(LIFO) 원칙을 따르는 순서가 있는 집합입니다. 새로 추가되거나 삭제될 요소는 스택의 한쪽 끝(스택 상단)에 저장되며, 다른 쪽 끝은 스택 하단이라고 합니다. 스택에서 새 요소는 상단에, 오래된 요소는 하단에 위치합니다. 책을 쌓아 올린 모습을 연상하면 됩니다. 스택 자료구조에는 다음 메서드가 있습니다:

1. push(element) 하나 또는 여러 요소를 추가합니다.
2. pop() 스택 상단의 요소를 제거하고 반환합니다.
3. peek() 스택 상단의 요소를 반환하지만 원본 스택은 수정하지 않습니다.
4. isEmpty() 스택이 비어 있는지 확인합니다.
5. clear() 스택을 비웁니다.
6. size() 스택의 요소 개수를 반환합니다.

스택의 자바스크립트 구현

1. 스택

스택의 응용

1. 10진수를 2진수로 변환
2. 하노이 탑

큐

큐의 기본 개념과 메서드

큐는 FIFO(First In First Out, 선입선출) 원칙을 따르는 정렬된 항목들의 집합입니다. 큐는尾部에 새 요소를 추가하고,顶部에서 요소를 제거합니다. 가장 최근에 추가된 요소는 반드시 큐의 끝에 위치해야 합니다. 큐 자료 구조에는 다음과 같은 메서드가 있습니다:

1. enqueue(element) - 큐의尾部에 하나(또는 여러 개)의 새 항목을 추가
2. dequeue() - 큐의 첫 번째 항목(가장 먼저 추가된 요소)을 제거하고, 제거된 요소를 반환
3. front() - 큐의 첫 번째 요소(가장 먼저 추가된 요소)를 반환하되, 큐는 변경하지 않음
4. isEmpty() - 큐가 비어 있는지 여부를 반환
5. size() - 큐의 요소 개수를 반환

큐의 JavaScript 구현

1. 큐
2. 가중치 큐

연결 리스트

연결 리스트의 기본 개념과 메서드

연결 리스트의 각 항목은 자신의 값뿐만 아니라 다음 항목의 위치를 가리키는 포인터도 저장합니다. 이를 단일 연결 리스트라고 합니다. 각 항목이 다음 항목의 위치를 가리키는 포인터뿐만 아니라 이전 항목을 가리키는 포인터도 저장하는 경우(시작/끝 항목 제외, 이들의 이전/다음 포인터는 null) 이를 이중 연결 리스트라고 합니다. 이중 연결 리스트의 처음과 끝이 서로 연결되어 있으면 이중 순환 연결 리스트라고 합니다. 아래와 같습니다(화살표가 포인터이며, 화살표 꼬리 부분에 해당하는 항목의 일부입니다):

1. 단일 연결 리스트

   graph RL
   A(Tail) --> B(第三项) --> C(第二项) --> D(Head)

2. 이중 연결 리스트

   graph LR
   A(Head) --> B(第二项) --> A
   B --> C(第三项) --> B
   C --> D(Tail) --> C

3. 순환 연결 리스트

   graph LR
   A(Head) --> B(第二项) --> A
   B --> C(第三项) --> B
   C --> D(Tail) --> C
   A --> D --> A

연결 리스트에는 다음과 같은 메서드가 있습니다:

1. append(element) 연결 리스트의 끝에 새로운 항목 추가
2. insert(position, element) 연결 리스트의 특정 위치에 새로운 항목 삽입
3. remove(element) 연결 리스트에서 항목 제거
4. indexOf(element) 요소의 연결 리스트 내 인덱스 반환, 없을 경우 -1 반환
5. removeAt(position) 연결 리스트의 지정된 위치 항목 제거
6. isEmpty() 연결 리스트가 비어있는지 여부 확인
7. size() 연결 리스트 항목의 개수 반환

연결 리스트의 JavaScript 구현

1. 단일 연결 리스트{:data-open=“”}
2. 이중 연결 리스트{:data-open=“”}
3. 순환 연결 리스트{:data-open=“”}

집합

집합의 기본 개념과 메서드

집합은 순서 없고 유일한(중복 불가) 항목들의 모음입니다. 집합은 다음과 같은 메서드를 가집니다:

1. add(value) 집합에 새로운 항목 추가
2. remove(value) 집합에서 항목 제거
3. has(value) 항목이 집합에 있는지 확인
4. clear() 집합 비우기
5. size() 집합의 크기 반환
6. values() 집합의 모든 값을 포함한 배열 반환
7. union(set) 다른 집합과의 합집합 반환
8. intersection(set) 다른 집합과의 교집합 반환
9. difference(set) 다른 집합과의 차집합 반환(현재 집합에서 지정된 집합을 뺀 것)
10. subset(set) 한 집합이 다른 집합의 부분집합인지 확인

집합의 JavaScript 구현

일반적으로 객체나 ES6의 Set을 사용하여 구현하며, 세부 사항은 생략합니다.

딕셔너리

딕셔너리의 기본 개념

집합은 서로 다른 요소들의 모음을 나타내며, 집합에서는 객체를 사용하여 {값: 값} 형태로 저장합니다. 반면, 사전에서는 {키: 값} 형태를 사용하며, 사전은 매핑이라고도 불립니다. 사전에는 일반적으로 다음과 같은 메서드들이 있습니다:

1. set(key, value) 사전에 항목 추가
2. delete(key) 지정된 키를 가진 항목 삭제
3. has(key) 특정 키를 가진 항목이 사전에 존재하는지 확인
4. get(key) 특정 키를 가진 항목을 찾아 반환
5. clear() 사전 비우기
6. size() 사전의 크기 반환
7. keys() 사전에 포함된 모든 항목의 키를 배열로 반환
8. values() 사전에 포함된 모든 항목의 값을 배열로 반환

사전의 JavaScript 구현

생략

해시 테이블

해시 테이블은 HashTable(배열 구현) 또는 HashMap(객체 구현)이라고도 하며, 사전 데이터 구조의 해시 테이블 구현 방식입니다. 사전에서 항목을 찾을 때 최악의 경우 전체 데이터 구조를 순회해야 할 수 있습니다. 하지만 해시 테이블과 함께 사용되는 해시 알고리즘을 이용하면 값의 정확한 위치를 알 수 있으므로 해당 값을 빠르게 검색할 수 있습니다. 해시 함수의 역할은 주어진 키 값을 기반으로 해시 테이블 내의 주소를 반환하는 것입니다.

해시 테이블의 용도

당신은 왜 해시 테이블이 필요한지 물어볼 수 있습니다. JavaScript에서는 객체를 직접 사용하여 키-값 매핑을 얻을 때 O(1)의 속도로 처리할 수 있지 않냐고요. 이 말은 맞지만, 만약 중복된 키가 있다면 어떻게 해야 할까요? 예를 들어, 다른 학생들의 정보를 기록하기 위한 명부를 만들고 싶다고 가정해 봅시다. 그런데 동명이인 학생이 있다면 어떻게 해야 할까요? 이때는 각 학생의 이름을 입력으로 받아 고유한 출력을 생성하는 알고리즘이 필요합니다. 이렇게 해야 일대일 대응이 가능해져 O(1) 알고리즘을 구현할 수 있습니다. 이를 완벽한 해시라고 하며, 수학에서는 완전 단사 함수라고 합니다. 하지만 이 방법으로 수백만 개의 데이터를 저장하면 Object 객체가 매우 커져 성능 문제가 발생할 수 있습니다. 따라서 시간과 공간을 균형 있게 조절하기 위해 해시 알고리즘이 필요합니다.

위의 명부 예시를 다시 살펴보면, 동명이인 학생이 있는 경우 여전히 그 이름을 키로 사용하지만, 값은 단순히 한 학생의 정보가 아니라 학생 정보의 배열(또는 연결 리스트)이 됩니다. 학생 이름이 주어졌을 때, 해당 값이 배열인 경우 배열을 순회하면서 정확한 학생 정보를 찾습니다. 이렇게 하면 시간(이전의 O(1)보다 길어짐 ❌)과 공간(이전의 Object 객체보다 적은 공간 사용 ✅)을 균형 있게 조절할 수 있습니다. 좋은 해시 알고리즘은 각 키의 배열 크기가 크게 차이나지 않도록 보장해야 합니다.

해시 테이블의 기본 메서드

1. put(key, value) 해시 테이블에 새 항목 추가
2. remove(key) 키를 기반으로 해시 테이블에서 항목 제거
3. get(key) 키를 기반으로 항목 검색

가장 간단한 해시 함수

입력이 문자열인 경우를 예로 들며, 동일한 문자열은 일단 고려하지 않고, 데이터 구조로 배열을 사용합니다. 이렇게 하면 key를 키로 사용할 수 있습니다.

1
2
3
4
5
6
7

let loseloseHashCode = function (key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % 37;
};

해시 테이블의 충돌 해결

위의 해시 알고리즘을 통해 계산된 키는 충돌이 발생할 수 있습니다. 즉, 배열에서 동일한 key에 다른 값이 있을 경우 덮어쓰게 됩니다. 따라서 충돌을 해결해야 합니다. 세 가지 해결 방법이 있습니다:

1. 분리 연결법은 해시 알고리즘이 생성한 키가 동일할 때, 키가 값을 직접 가리키는 대신 배열/연결 리스트를 가리키게 하여 문제를 배열/연결 리스트의 삽입/검색으로 변환하는 방법입니다.
2. 선형 탐사법은 해시 알고리즘이 생성한 키가 동일할 때, 키를 자동으로 +1하여 다시 저장을 시도합니다. 여전히 키 충돌이 발생하면 계속 +1을 하여 빈 위치를 찾을 때까지 반복합니다(키가 숫자인 해시 테이블 형태, 예를 들어 배열에 적합합니다). 숫자 키를 위한 더 훌륭한 해시 구현은 이곳에서 확인할 수 있습니다.
3. 이중 해싱법은 해시 알고리즘이 생성한 키가 동일할 때, 충돌이 발생하면 다른 또는 동일한 해시 함수를 다시 사용하여 키를 생성하는 방법입니다.

해시 테이블의 JavaScript 구현

1. 일반 해시 테이블 구현
2. 분리 연결법
3. 선형 탐사법

트리

트리 관련 용어

먼저 구조 다이어그램을 살펴보세요:

graph TD;
    11---7;
    11---15;
    7---5;
    7---9;
    5---3;
    5---6;
    9---8;
    9---10;
    15---13;
    15---20;
    13---12;
    13---14;
    20---18;
    20---25;

여기서:

1. 11은 0층, 7/15는 1층, 5/9/13/20은 2층, 나머지는 3층입니다.
2. 11을 루트 노드라고 하며, 나머지는 자식 노드라고 합니다. 최소한 하나의 자식 노드를 가진 노드를 내부 노드라고 하며, 자식 요소가 없는 노드를 외부 노드라고 합니다.
3. 노드에는 깊이 속성이 있습니다. 예를 들어 노드 3은 세 개의 조상 요소를 가지므로 깊이가 3입니다.
4. 트리의 높이는 모든 노드의 깊이 중 최댓값에 의해 결정됩니다.
5. 이것은 완전 이진 트리입니다. 가장 아래층 노드를 제외한 모든 노드가 두 개의 노드를 가지고 있기 때문입니다.

주의: 동일한 데이터라도 여러 트리 구조가 있을 수 있으며, 반드시 유일한 표현 형태는 아닙니다. 따라서 다음 절의 AVL 트리가 등장합니다. AVL 트리는 데이터를 가능한 한 완전한 트리로 구성하려고 합니다.

이진 트리와 이진 탐색 트리

이진 트리의 노드는 최대 두 개의 자식 노드를 가질 수 있습니다. 하나는 왼쪽 자식 노드이고, 다른 하나는 오른쪽 자식 노드입니다. 이진 탐색 트리(BST)는 이진 트리의 일종이지만, 임의의 노드의 왼쪽에는 해당 노드보다 작은 값을 저장하고, 오른쪽에는 해당 노드보다 크거나 같은 값을 저장할 수 있습니다. 다이어그램에 나온 것은 이진 탐색 트리이며, 다음과 같은 메서드가 있습니다:

1. insert(key) 새로운 노드 삽입
2. search(key) 노드 검색 또는 null 반환
3. inOrderTraverse 중위 순회로 모든 노드 방문
4. preOrderTraverse 전위 순회로 모든 노드 방문
5. postOrderTraverse 후위 순회로 모든 노드 방문
6. min 트리에서 가장 작은 값 반환
7. max 트리에서 가장 큰 값 반환
8. remove(key) 트리에서 특정 항목 제거

트리 순회 도식:

1. 중위 순회—주로 트리 정렬 작업에 사용됨

   graph TD;
       11---7;
       11---15;
       7---5;
       7---9;
       5---3;
       5---6;
       9---8;
       9---10;
       15---13;
       15---20;
       13---12;
       13---14;
       20---18;
       20---25;
       3-.->5
       5-.->6;
       6-.->7;
       7-.->8;
       8-.->9;
       9-.->10;
       10-.->11;
       11-.->12;
       12-.->13;
       13-.->14;
       14-.->15;
       15-.->18;
       18-.->20;
       20-.->25;

   순회 순서: 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

2. 전위 순회—구조화된 문서 출력에 주로 사용되며, 예시 도식의 순회 순서는: 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

3. 후위 순회—디렉토리와 그 하위 디렉토리의 전체 파일 크기 계산에 적용되며, 예시 도식의 순회 순서는: 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

Adelson-Velskii-Landi 트리(AVL 트리)

AVL 트리는 자가 균형 트리입니다. 이진 트리는 특정 상황에서 한쪽 서브트리가 지나치게 깊어지고 다른 서브트리는 지나치게 얕아질 수 있으며, 아래 그림과 같습니다:

graph TD;
    11---7;
    11---15;
    7---5;
    7---9;
    5---3;
    5---6;
    9---8;
    9---10;
    15---13;
    15---20;
    13---12;
    13---14;
    20---18;
    20---25;
    25---27
    27---30

이 트리의 오른쪽이 지나치게 깊어져 노드 검색, 추가, 삭제 시 성능 문제를 일으킬 수 있으므로 AVL 자가 균형 트리가 필요합니다. AVL은 자가 균형 이진 탐색 트리로, 모든 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 최대 1입니다. 즉, 이 트리는 노드 추가 또는 제거 시 완전 트리에 가깝게 유지하려고 합니다.

AVL 트리의 균형 인자 및 계산

AVL 트리에서 노드 삽입 및 삭제는 BST와 완전히 동일합니다. AVL의 차이점은 삽입/삭제 시 균형 인자(Balance Factor)를 확인하고 필요한 경우 트리의 자동 균형 조정을 적용한다는 점입니다. AVL 트리에서는 각 노드에 대해 오른쪽 서브트리 높이(hr)와 왼쪽 서브트리 높이(hl)의 차이를 계산합니다. 이 값(hr-hl)이 0, 1, -1 중 하나가 아닌 경우 해당 AVL 트리의 균형을 조정해야 합니다. 이것이 균형 인자의 개념입니다. 다음 세 트리는 모두 균형이 잡혀 있습니다:

graph TD;
    subgraph 第三种
        A((+1))---B(( -1))
        A---C(( -1))
        B---E((0))
        C---D((+1))
        C---F((0))
        D---H((0))
    end
    subgraph 第二种
        I((+1))---G((0))
        I---K(( -1))
        K---L((0))
    end
    subgraph 第一种
        M(( -1))---N((0))
    end

AVL 트리의 회전

AVL 트리에 노드를 삽입할 때 단일 회전 또는 이중 회전 두 가지 균형 조정 연산을 수행할 수 있으며, 각각 네 가지 시나리오에 해당합니다:

1. 오른쪽---오른쪽(RR): 왼쪽으로의 단일 회전
2. 왼쪽---왼쪽(LL): 오른쪽으로의 단일 회전
3. 왼쪽---오른쪽(LR): 오른쪽으로의 이중 회전
4. 오른쪽---왼쪽(RL): 왼쪽으로의 이중 회전

오른쪽—오른쪽(RR): 왼쪽으로의 단일 회전 예시(mermaid 그래프에서는 이진 트리로 표현할 수 없어 80이 왼쪽, 50이 오른쪽에 위치함):

graph TD;
    subgraph 之后
        G((70))---H((50))
        G---I((80))
        I---J((90))
        H---K((30))
        H---L((60))
    end
    subgraph 之前
        A((50))---B((30))
        A---C((70))
        C---D((60))
        C---E((80))
        E---F((90))
    end

왼쪽—왼쪽(LL): 오른쪽으로의 단일 회전 예시(mermaid 그래프에서는 이진 트리로 표현할 수 없어 50이 왼쪽, 10이 오른쪽에 위치함):

graph TD;
    subgraph 之后
        G((30))---H((10))
        G---I((50))
        I---J((40))
        I---K((70))
        H---L((5))
    end
    subgraph 之前
        A((50))---C((30))
        A---B((70))
        C---D((10))
        C---E((40))
        D---F((5))
    end

왼쪽—오른쪽(LR): 오른쪽으로의 이중 회전 예시(기본적으로 RR 회전을 한 번 수행한 후 LL 회전을 수행):

graph TD;
    subgraph 之后
        G((40))---H((30))
        G---I((50))
        H---J((10))
        H---K((35))
        J---L((70))
    end
    subgraph 之前
        A((50))---C((30))
        A---B((70))
        C---D((10))
        C---E((40))
        E---F((35))
    end

오른쪽—왼쪽(RL): 왼쪽으로의 이중 회전 예시(기본적으로 LL 회전을 한 번 수행한 후 RR 회전을 수행, mermaid 그래프에서는 이진 트리로 표현할 수 없어 80이 왼쪽, 70이 오른쪽에 위치함):

graph TD;
    subgraph 之后
        G((72))---I((70))
        G---H((80))
        H---J((75))
        H---K((90))
        I---L((50))
    end
    subgraph 之前
        A((70))---B((50))
        A---C((80))
        C---D((72))
        C---E((90))
        D---F((75))
    end

AVL 트리는 자동 균형 조정이 가능하지만, 노드 삽입 또는 제거 성능이 항상 최적은 아닙니다. 더 나은 선택은 레드-블랙 트리입니다. 레드-블랙 트리는 노드를 효율적이고 순차적으로 탐색할 수 있습니다.

트리 기본 메서드의 JavaScript 구현

1. 이진 트리
2. AVL 트리
3. 레드-블랙 트리
4. 힙 트리

그래프

그래프의 기본 개념

그래프는 네트워크 구조의 추상적 모델입니다. 그래프는 간선으로 연결된 노드(또는 정점)들의 집합을 나타냅니다. 모든 이항 관계는 그래프로 표현할 수 있습니다. 그래프를 사용하여 두 점 사이의 최단 경로 등의 문제를 해결할 수 있습니다.

그래프의 수학적 개념

하나의 그래프 G=(V, E)는 다음 요소들로 구성됩니다.

1. V: 정점들의 집합
2. E: V에 속한 정점들을 연결하는 간선들의 집합

아래는 하나의 그래프를 나타낸 것입니다:

graph TD;
    A---B
    B---E
    B---F
    E---I
    A---C
    A---D
    C---D
    C---G
    D---G
    D---H

그래프 관련 용어

위 그래프에서:

1. 하나의 간선으로 연결된 정점들을 인접 정점이라고 합니다.
2. 하나의 정점의 차수는 그 정점과 인접한 정점들의 수입니다. 위 그래프에서 A는 다른 세 정점과 인접하므로 A의 차수는 3입니다; E의 차수는 2입니다.
3. 경로는 정점 v1, v2,…vk의 연속적인 시퀀스로, vi와 v(i+1)은 인접합니다. 위 그래프에는 ABEI와 ACDG 경로가 포함됩니다.
4. 단순 경로는 반복되는 정점을 포함하지 않아야 합니다. 예를 들어 ADG는 단순 경로입니다. 마지막 정점을 제외하면(첫 번째 정점과 동일한 정점이기 때문에), 순환도 단순 경로입니다. 예를 들어 ADCA(마지막 정점이 A로 돌아옴)가 있습니다.
5. 그래프에 순환이 존재하지 않으면 해당 그래프는 비순환적이라고 합니다. 그래프의 모든 두 정점 사이에 경로가 존재하면 해당 그래프는 연결됨이라고 합니다.
6. 그래프는 방향성이 있을 수도 있고(간선에 방향이 있음) 무방향성일 수도 있습니다(간선에 방향이 없음). 위 그래프는 무방향 그래프입니다.
7. 그래프의 모든 두 정점 사이에 양방향 경로가 존재하면 해당 그래프는 강하게 연결됨이라고 합니다.
8. 그래프는 가중치가 없는 상태일 수도 있고, 가중치가 있는 상태일 수도 있습니다. 가중치 그래프에서는 간선에 가중치가 부여됩니다.

그래프의 표현

인접 행렬

그래프를 구현하는 가장 일반적인 방법은 인접 행렬입니다. 각 노드는 정수와 연관되며, 이 정수는 배열의 인덱스로 사용됩니다. 정점들 사이의 연결을 나타내기 위해 2차원 배열을 사용합니다. 인덱스가 i인 노드와 인덱스가 j인 노드가 인접하면 array[i][j] === 1이고, 그렇지 않으면 array[i][j] === 0입니다. 위의 그래프를 인접 행렬로 나타내면 다음과 같습니다:

강하게 연결되지 않은 그래프를 희소 그래프라고 합니다. 인접 행렬로 표현할 경우 행렬에 많은 0이 포함되어, 실제로 존재하지 않는 간선을 표현하기 위해 컴퓨터의 저장 공간을 낭비하게 됩니다.

인접 리스트

인접 리스트는 그래프에서 각 정점의 인접한 정점 목록으로 구성됩니다. 이러한 데이터 구조를 표현하는 여러 가지 방법이 있습니다. 리스트(배열)/연결 리스트/심지어 해시 테이블이나 딕셔너리를 사용하여 인접 정점 목록을 나타낼 수 있습니다. 위의 그래프는 아래의 인접 리스트로 표현될 수 있습니다:

인접 행렬(생략)

그래프 관련 메서드

1. addVertex(v) 새로운 정점 추가
2. addEdge(v, w) 새로운 간선 추가

그래프 순회

그래프 순회는 특정 정점을 찾거나 두 정점 사이의 경로를 탐색하고, 그래프가 연결되어 있는지 확인하며, 그래프에 사이클이 포함되어 있는지 검사하는 등의 용도로 사용됩니다. 그래프 순회 알고리즘의 기본 아이디어는, 처음 방문한 각 노드를 추적하고, 아직 완전히 탐색되지 않은 노드(즉, 아직 탐색되지 않은 자식 노드가 있는 노드)가 무엇인지 추적하는 것입니다. 아래 두 가지 탐색(순회) 모드 모두에서, 첫 번째로 방문할 정점을 명확히 지정해야 합니다. 정점을 완전히 탐색하려면 해당 정점의 모든 간선을 확인하고, 각 간선으로 연결된 방문하지 않은 정점을 발견된 것으로 표시하고, 방문할 정점 목록에 추가해야 합니다. 알고리즘의 효율성을 보장하기 위해 각 정점을 최대 두 번만 방문해야 합니다. 연결된 그래프에서는 모든 간선과 정점이 방문됩니다. 정점의 방문 상태는 세 가지로 나타낼 수 있습니다: 미방문/방문되었지만 완전히 탐색되지 않음/완전히 탐색됨

그래프의 너비 우선 탐색(Breadth-First Search, BFS)

방문할 정점 목록의 데이터 구조는 큐이며, 정점을 큐에 저장하고, 가장 먼저 큐에 들어간 정점부터 탐색합니다.

너비 우선 탐색(BFS)은 최단 경로를 찾는 데 사용됩니다(아래에 구현 예시가 있음). Dijkstra 알고리즘은 단일 출발점 최단 경로 문제를 해결합니다(탐욕 알고리즘). Bellman-Ford 알고리즘은 간선 가중치가 음수인 단일 출발점 최단 경로 문제를 해결합니다. A* 탐색 알고리즘은 한 쌍의 정점 사이의 최단 경로만을 구하는 문제를 해결하며, 휴리스틱을 사용해 탐색 속도를 높입니다. Floyd-Warshall 알고리즘은 모든 정점 쌍 간의 최단 경로 문제를 해결합니다(동적 계획법 알고리즘).

그래프의 깊이 우선 탐색(Depth-First Search, DFS)

방문할 정점 목록의 자료 구조는 스택이며, 정점을 스택에 저장하고 경로를 따라 정점을 탐색합니다. 새로운 인접 정점이 있으면 방문합니다. 작업이나 단계의 실행 순서를 정렬해야 할 때 이를 위상 정렬(topsort/toposort)이라고 하며, 깊이 우선 탐색을 사용해 위상 정렬을 수행할 수 있습니다. 위상 정렬은 방향성 비순환 그래프(DAG)에만 적용할 수 있으며, 아래에 구체적인 구현 예시가 있습니다.

최소 신장 트리(MST)

최소 신장 트리는 네트워크 설계에서 흔히 접하는 문제입니다. 예를 들어 회사에 여러 사무실이 있고, 전화 회선을 상호 연결해 비용을 최소화하면서 자금을 절약하려면 어떤 방법이 가장 좋을까요? 이는 섬과 다리 문제에도 적용할 수 있습니다. n개의 섬 사이에 다리를 건설해 모든 섬을 상호 연결하는 데 최소 비용을 들이고 싶다면, 이 두 문제 모두 MST 알고리즘으로 해결할 수 있습니다:

1. Prim 알고리즘

   가중치가 있는 무방향 연결 그래프의 MST 문제를 해결하는 탐욕 알고리즘으로, 모든 정점을 포함하는 트리를 구성하는 간선의 부분 집합을 찾아 간선 가중치의 합이 최소가 되도록 합니다.

2. Kruskal 알고리즘

   위와 마찬가지로 가중치가 있는 무방향 연결 그래프의 MST 문제를 해결하는 탐욕 알고리즘입니다.

그래프의 JavaScript 구현

1. 그래프
2. 최단 경로 알고리즘
3. 최소 신장 트리

정렬 및 탐색 알고리즘

정렬 알고리즘

1. 버블 정렬 복잡도 O(n²) 두 개의 루프를 사용하며, 조건을 만족하면 내부 루프의 두 값을 교환합니다.
2. 선택 정렬 복잡도 O(n²) 두 개의 루프를 사용하며, 내부 루프에서 최솟값을 찾아 첫 번째 위치에 놓고, 두 번째로 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복합니다.
3. 삽입 정렬 복잡도 O(n²) 처음부터 시작하여 앞부분이 이미 정렬되었다고 가정한 후, 현재 값이 정렬된 배열의 어느 위치에 들어가야 하는지 판단하여 삽입하고 다음 값으로 넘어갑니다.
4. 병합 정렬 복잡도 O(nlogⁿ) 재귀적 접근으로 배열을 작은 배열로 나눈 후, 각 작은 배열을 두 개씩 정렬(각각 정렬된 두 벌의 카드를 정렬하는 것처럼)하여 최종적으로 완전히 정렬합니다.
5. 퀵 정렬 복잡도 O(nlogⁿ) 피벗(pivot)을 선택하고 데이터를 두 부분으로 나눕니다. 피벗보다 큰 값은 오른쪽, 작은 값은 왼쪽에 배치하며, 왼쪽 포인터가 오른쪽 포인터를 넘어설 때까지 반복합니다.
6. 힙 정렬 배열을 이진 트리로 간주하여 정렬합니다. 규칙은 다음과 같습니다:
   1. 인덱스 0은 트리의 루트 노드입니다.
   2. 루트 노드를 제외한 모든 노드 N의 부모 노드는 N/2입니다.
   3. 노드 L의 왼쪽 자식 노드는 2 * L입니다.
   4. 노드 R의 오른쪽 자식 노드는 2 * R + 1입니다.
   5. 예를 들어 배열 [3, 5, 1, 6, 4, 7, 2]는 다음과 같은 트리로 볼 수 있습니다:

      graph TD;
      A((3))---B((5))
      A---C((1))
      B---D((6))
      B---E((4))
      C---F((7))
      C---G((2))

7. 계수 정렬
8. 버킷 정렬
9. 기수 정렬(분산 정렬)

검색 알고리즘

1. 순차 검색
2. 이진 검색

정렬/검색 알고리즘의 JavaScript 구현

1. 다양한 정렬/검색 알고리즘 모음

알고리즘 패턴

동적 프로그래밍

1. 배낭 문제는 일련의 아이템과 각각의 가치 및 용량이 주어졌을 때, 총 가치가 최대가 되는 아이템의 집합을 찾는 문제입니다. 제약 조건은 총 용량이 배낭의 용량보다 작거나 같아야 한다는 것입니다.
2. 최장 공통 부분 수열은 여러 수열에서 가장 긴 공통 부분 수열을 찾는 문제입니다(다른 수열에서 요소를 삭제하되 남은 요소의 순서는 바꾸지 않고 얻을 수 있는 부분 수열).
3. 행렬 체인 곱셈은 일련의 행렬이 주어졌을 때, 이들 행렬을 곱하는 가장 효율적인 방법(계산 횟수를 최소화)을 찾는 문제입니다. 실제 곱셈 연산은 수행되지 않으며, 행렬들이 곱해지는 순서를 찾는 것이 목적입니다.
4. 동전 거스름돈 문제는 d1, d2…dn 액면가를 가진 일정 수의 동전과 거스름돈 금액이 주어졌을 때, 거스름돈을 만드는 방법의 수를 찾는 문제입니다.
5. 그래프의 모든 쌍 최단 경로는 모든 정점 쌍(u, v)에 대해 정점 u에서 v로의 최단 경로를 찾는 문제입니다(이전에 Floyd-Warshall 알고리즘으로 해결할 수 있었습니다).

알고리즘 패턴의 JavaScript 구현

1. 재귀
2. 최소 동전 거스름돈 DP 알고리즘
3. 최소 동전 거스름돈 탐욕 알고리즘
4. 배낭 문제 DP 알고리즘
5. 배낭 문제 재귀 알고리즘
6. 배낭 문제 탐욕 알고리즘
7. 최장 공통 부분 수열 DP 알고리즘
8. 최장 공통 부분 수열 재귀 알고리즘
9. 행렬 체인 곱셈 DP 알고리즘
10. 행렬 체인 곱셈 재귀 알고리즘

NP 완전 이론 개요

일반적으로, 알고리즘의 복잡도가 O(n^k)이고 k가 상수인 경우, 이 알고리즘을 효율적이라고 간주하며, 이를 다항식 알고리즘이라고 합니다. 주어진 문제에 대해 다항식 알고리즘이 존재하면 P(polynomial, 다항식)으로 분류합니다.

또 다른 유형인 NP(nondeterministic polynomial, 비결정적 다항식) 알고리즘이 있습니다. 어떤 문제가 다항식 시간 내에 해의 정확성을 검증할 수 있다면 NP로 분류됩니다.

어떤 문제가 다항식 알고리즘을 가지고 있다면, 자연스럽게 다항식 시간 내에 그 해답을 검증할 수 있으므로 모든 P는 NP에 속합니다. 그러나 P=NP가 성립하는지는 여전히 알려지지 않았습니다.

NP 문제 중 가장 어려운 것은 NP 완전 문제로, 다음 두 가지 조건을 만족합니다:

1. NP 문제입니다. 즉, 다항식 시간 내에 해답을 검증할 수 있지만 아직 다항식 알고리즘을 찾지 못했습니다.
2. 모든 NP 문제를 다항식 시간 내에 이 문제로 환원할 수 있습니다.

또 다른 유형의 문제는 NP 완전 문제의 두 번째 조건만 만족하면 되며, 이를 NP 난해 문제라고 합니다. 따라서 NP 완전 문제는 NP 난해 문제의 부분집합입니다.

NP 완전 문제가 아닌 NP 난해 문제의 예로는 정지 문제와 부울 만족 가능성 문제(SAT)가 있으며, NP 완전 문제의 예로는 부분집합 합 문제, 외판원 문제, 정점 커버 문제 등이 있습니다.

마지막으로, 앞서 언급한 문제 중 일부는 해결 불가능하지만, 여전히 요구 사항에 맞는 시간 내에 근사해를 찾을 수 있는 방법이 있습니다. 휴리스틱 알고리즘이 그 중 하나입니다. 휴리스틱 알고리즘으로 얻은 해답이 최적해는 아닐 수 있지만, 문제를 해결하기에는 충분합니다.

휴리스틱 알고리즘의 예로는 지역 탐색, 유전 알고리즘, 휴리스틱 네비게이션, 기계 학습 등이 있습니다. 더 많은 정보는 여기에서 확인할 수 있습니다.

• 이전 글
  에버노트에서 애플 기본 메모 앱으로 이동하기
• 다음 글
  Linux 파일 권한 메모