[CS 스터디] 자료구조 1

1. 시간복잡도와 공간복잡도에 대해 설명해 주세요.

상대 속도 / 하드웨어에 따라 시간은 다를 수 있어 처리 횟수로 봐야 한다.

시간 복잡도 : 알고리즘이 주어진 입력 크기에 따라 소요되는 시간, 즉 처리 횟수의 총량을 의미
공간 복잡도 : 알고리즘이 주어진 입력 크기에 따라 소요되는 메모리 공간의 총량을 의미

알고리즘의 최적화 작업을 위해 두 지표를 사용할 수 있으며 두 복잡도를 낮추기 위한 노력을 통해 최적의 성능을 가진 알고리즘을 구현할 수 있습니다.

적은 연산 횟수와 적은 메모리 공간을 차지하도록!

시간 복잡도와 공간 복잡도는 반비례적 성향이 있다. 그렇지만 공간 복잡도의 경우 메모리 용량이 부족한 사례가 많이 없어져서 상대적으로 시간 복잡도에 대한 분석을 더 중요하게 생각하게 된다.

Big-O, Big-Theta, Big-Omega 에 대해 설명해 주세요.

점근 표기법이며 알고리즘의 효율을 표현해주는 방식들

Big-O : 소요 시간이 증가할 수 있는 최악의 경우를 표현
Big-Theta : 소요 시간이 증가할 수 있는 평균적인 경우를 표현하며 최악, 최선의 경우 모두 같은 복잡도로 표현합니다.
Big-Omega : 소요 시간이 증가할 수 있는 최선의 경우를 표현

다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?

최악의 경우에도 데이터를 처리해주는 어플리케이션의 성능은 보장되어야 하기 때문입니다. 이를 평가하고 최적화하기 위해선 Big O 표기법으로 알고리즘을 평가하는 것이 적합하기 때문이라고 생각합니다.

O(1)은 O(N^2) 보다 무조건적으로 빠른가요?

이론적으로는 무조건 빠르다고 볼 수는 없을 것 같습니다.

Big O 표기법 그래프를 보더라도 분명하게 N^2이 1보다 빠른 구간은 존재
O(1)의 의미는 어떠한 데이터의 경우에도 동일한 시간을 소요한다의 의미
O(N^2의) 의미는 특정 구간을 지난 시점부터 기하급수적으로 소요시간이 증가한다 라는 의미
그러므로 두 복잡도가 소요 시간에 대한 비교보단 증가하는 방식의 차이라고 볼 수 있고, 데이터 량이 증가할 때 더 큰 증가폭을 보이는 것이 N^2입니다.

2. 링크드 리스트에 대해 설명해 주세요.

각각의 노드가 포인터를 통해 앞,뒤 원소에 대한 정보만 가지면서 연결된 자료구조로 이해하고 있습니다.

일반 배열과, 링크드 리스트를 비교해 주세요.

배열
- 인덱스를 가지고 순차적으로 저장 및 관리가 되어 인덱스를 통한 조회의 목적으로 사용 시 장점이 있습니다. O(1)의 시작 복잡도.
- 수정이나 삭제 시, 새로운 배열을 생성해 재배치 시켜줘야 하므로 효율이 떨어집니다. O(N)의 시간 복잡도
- 연속적인 저장 공간을 사용해 메모리 관리가 쉽습니다.
링크드 리스트
- 노드가 포인터를 통해 다음 또는 이전 노드를 가르키며 연결되므로 수정, 삭제가 빠릅니다. O(1) 시간 복잡도
- 다만 인덱스를 통한 조회가 불가능해 루프를 통해 데이터를 조회해야 합니다. O(n) 시간 복잡도.
- 메모리가 연속적이지 않아 관리가 불편합니다.

실제 Java에서 구현된 배열과 링크드 리스트의 경우
ArrayList의 경우, add()를 호출하면 기존 배열을 복사하고 새로운 배열로 재생성해 리턴
LinkedList의 경우, get(int index) 메소드를 호출하면 전체 노드를 반복문을 통해 조회한 다음 리턴

링크드 리스트를 사용해서 구현할 수 있는 다른 자료구조에 대해 설명해 주세요.

스택 : 하나의 입구와 출구로 구성, FILO의 방식으로 동작합니다.(JVM 메모리 영역 중 스택 영역, DFS)
큐 : 입구와 출구가 각각 구성되어 있어 FIFO의 방식으로 동작합니다.(kafka, redis pub/sub과 같은 메세지/이벤트 큐 브로커, BFS)
데큐 : 입구와 출구가 양쪽에 모두 구성, 양방향 큐라고 할 수 있습니다.
원형 연결 리스트 : 원형으로 노드들이 연결된 구조
그래프 : 각 그래프의 정점을 연결한 구조

3. 스택과 큐에 대해서 설명해 주세요.

스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.

참고 자료

스택 2개로 큐 생성 방법
1. 입력용 스택과 출력용 스택을 구현한다.
2. 입력용 스택에서 값을 입력받는다.
3. 출력 요청을 받는다.
4. 입력용 스택에 쌓인 데이터를 출력용 스택으로 옮긴다.
5. 출력용 스택에 가장 마지막에 들어온 데이터(= 입력용 스택에 가장 먼저 들어온 데이터)를 리턴한다.
큐 2개로 스택 생성 방법
1. 입력용 큐와 출력용 큐를 구현한다.
2. 입력용 큐에 데이터를 쌓는다.
3. 출력 요청을 받는다.
4. 입력용 큐에 쌓인 데이터를 출력용 큐에 옮긴다.
5. 입력용 큐에 가장 마지막 데이터가 남았을 때, 해당 데이터를 리턴한다.
6. 출력용 큐에 쌓여 있던 데이터를 다시 입력용 큐로 옮긴다.

큐와 스택은 데이터 추가에 대해서 O(1) 시간 복잡도를 가집니다. 그리고 위애서 구현한 두 방식 모두 입력에 대해서는 O(1)의 복잡도를 가집니다. 하지만 출력에 대해서는 전체 데이터를 모두 순환해야 하므로 O(N)의 시간 복잡도를 가진다고 할 수 있습니다.

다만 연속적으로 데이터 리턴을 해줘야 하는 경우에는 O(1) 시간 복잡도를 유지할 수 있습니다.

시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?

스택은 가능합니다. 배열의 가장 마지막 열로만 삽입/추출할 경우, 기존 데이터의 위치를 변경하지 않고 구현이 가능하므로 O(1)을 유지할 수 있습니다. 하지만 이건 크기가 정적인 큐에 대해서만 가능합니다. 만약 동적인 크기를 가지는 스택을 구현하고 싶다면 배열이 가득 찰 때마다 새로운 배열로 copy되어야 하므로 O(N) 시간 복잡도를 가지게 됩니다.

JAVA에서 ArrayList도 Arrays.copyOf()를 통해 배열을 재생성하도록 구현되어 있습니다.

큐는 배열의 가장 앞 열을 삽입 혹은 추출로 사용해야 하므로 기존 데이터의 재배치가 필요합니다. 이 경유 O(N)의 시간 복잡도가 요구됩니다.

그러나 배열로 스택과 큐를 구현할 경우, 장점이라고 한다면 특정 원소에 대한 접근을 인덱스를 통해 가능하며 이는 O(1)의 시간 복잡도를 가질 수 있게 됩니다.

하지만 이런 장점을 활용하고자 한다면 꼭 큐나 스택을 사용해야 할 지 다시 고민해봐야 하지 않을까..

Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산/하는 방법에 대해 설명해 주세요.

세 개념 모두 수식을 표현하는 방식

Prefix : 연산자를 피연산자 앞으로 배치
Infix : 연산자를 피연산자 사이에 배치
Postfix : 연산자를 피연산자 뒤로 배치, 컴퓨터가 수식을 계산할 때 사용하는 표현법
컴퓨터가 후위 표현식을 주로 사용하는 것 후위 표현식은 가독성이 높고, 괄호 사용이 줄어들며, 연산의 연속성을 제공하고, 스택을 이용한 계산이 용이하기 때문에 다양한 수식을 효과적으로 처리할 수 있기 때문입니다.

Postfix 동작 방식

왼쪽에서 오른쪽으로 하나씩 읽어간다.
피연산자를 만나면 스택이 추가하고 연산자를 만나면 피연산자 두개를 꺼내 계산하고 다시 스택에 추가한다.

Prefix 동작 방식

오른쪽에서 왼쪽으로 하나씩 읽어간다.
피연산자를 만나면 스택이 추가하고 연산자를 만나면 피연산자 두개를 꺼내 계산하고 다시 스택에 추가한다.

예시)

Infix : (3+5) * 2 = 16 -> Postfix : 3 5 + 2 *

순서) 스택
1)   3
2)   5 3
3)   8
4)   2 8
5)   16

Deque는 어떻게 구현할 수 있을까요?

배열이나 LinkedList로 구현이 가능합니다. 다만 배열로 구현할 경우 O(N)의 시간 복잡도를 가질 수 있습니다.

(C++ 한정) Deque의 Random Access 시간복잡도는 O(1) 입니다. 이게 어떻게 가능한걸까요?

4. 해시 자료구조에 대해 설명해 주세요.

키 : 값 구조의 해시테이블에 데이터를 저장하는 자료구조이며 키를 통해 값을 빠르게 조회할 수 있습니다.O(1) 시간 복잡도를 가집니다. 키는 중복이 허용되지 않기 때문에 고유한 값으로 유지되어야 하는데 이 키를 해시함수를 활용해 구성합니다.

값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요? -> 가장 어려웠던 부분

참고 자료

Division Method : 값을 버킷 사이즈(테이블 사이즈)로 나누어 나머지를 전체 버킷사이즈에서 뺀값으로 사용, 이 때 버킷사이즈는 소수를 사용하고 2의 제곱수와 먼 값을 사용하는 것이 좋다.
Digit Folding : 값이 문자열일 때 아스키코드로 바꿔 합한 값을 사용, 이때 버킷사이즈를 넘어갈 수 있기 때문에 Divison Method를 함께 사용
Multiplication Method : floor(k*A mod 1) * m의 식을 사용한다. A는 0무과 1사이의 실수 m은 2의 제곱수를 사용한다.
Univiersal Hashing : 여러 해시함수를 무작위로 사용한다.

해시값이 충돌했을 때, 어떤 방식으로 처리할 수 있을까요?

참고자료

Chaining : 충돌 시 , 해당 키에 해당하는 값들을 리스트의 형태로 저장하는 방식
Open Addressing : 새로운 슬롯을 찾아주는 방식
- 선형 탐사법(Linear probing)
  - 충돌이 나면 빈 슬롯을 찾을 때까지 슬롯을 한칸씩 옮겨가며 찾는 방식
  - primary clustering 문제가 나올 수 있습니다.(특정 해시값 주변이 모두 채워지기 때문에!)
- 제곱 탐사법(Quadratic probing)
  - 충돌이 나면 빈 슷롯을 고정값이 아닌 제곱을 하는 방식으로 빈칸을 찾는 방식
  - primary clustering 문제는 해결되지만 캐시의 성능이 떨어집니다.
- 이중 해시(Double Hashing)
  - 충돌이 나지 않은 경우와 날 경우 사용할 별도의 해시 함수를 사용하는 방식
  - 가장 균일하게 배포가 된다.
  - 하지만 추가적인 연산으로 성능상 무리가 많이 가고 캐시 성능이 가장 안좋습니다.

캐시 적중률
캐시에 데이터를 조회할 때 원하는 데이터가 있는 비율
만약 배열이 넓어서 데이터들이 멀리 떨어진 메모리에 저장되어 있거나 캐시 용량을 넘어가면 캐시 적중률이 떨어집니다.

본인이 사용하는 언어에서는, 어떤 방식으로 해시 충돌을 처리하나요?

JAVA에서는 개별 Chaining 방식을 사용하며 HashMap의 각 슬롯별로 충돌이 나면 링크들 리스트 형태로 데이터를 저장합니다.

Java7까지는 LinkedList로만 저장했다면 Java8부터는 레드블랙트리로 저장합니다. 이는 링크드 리스트로 인해 시간 복잡도가 O(N)이 되는 문제를 트리로 변경해 O(log N)으로 완화하기 위함이며 노드 개수가 6개로 줄면 링크드리스트로 8개 이상이 되면 트리로 자료구조가 변환됩니다. 이렇게 2개 차이로 구성한 건 1개 차이로 인한 자료구조 변경은 방지하기 위합니다.

또한 하나의 링크드 리스트에서 정확한 Key를 조회하기 위해서 equals()를 사용하게 됩니다. 그래서 키값을 객체로 사용한다면 hascode()와 함께 equals()도 논리적 동일함을 보장할 수 있게 오버라이딩이 되어야한다고 하는 것입니다.

Double Hashing 의 장점과 단점에 대해서 설명하고, 단점을 어떻게 해결할 수 있을지 설명해 주세요.

장점 : 가장 균일한 슬롯 분배가 가능하다. 최대한 유니크하게!
단점 : 많은 연산량은 요구하고 캐시의 성능이 가장 안좋다. 서로소 이여야 한다..?

단점을 해결하는 방법

서로소를 맞춘다.
그래도 한계가 있다.
Re-hashing? 로드 팩터?

5. 트리와 이진트리, 이진탐색트리에 대해 설명해 주세요.

트리란 노드가 간선(Edge)로 구성되며 루트 노드로부터 자식 노드로 계층적인 형태로 데이터가 저장되는 비선형 자료구조입니다.

이진 트리란 하나의 노드가 두개의 자식노드만 가지는 형태의 트리 구조를 의미합니다.

이지탐색트리란 이진트리에서도 다음과 같은 특징을 가진 트리를 의미합니다.

모든 노드는 고유의 키를 가진다.
왼쪽 자식은 부모 보다 작은 값을 저장한다.
오른쪽 자식은 부모보다 큰 값을 저장한다.
모든 자식 노드 또한 이진탐색트리로 구성된다.

즉, 이진탐색 트리는 모든 노드가 고유한 키를 가지고, 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 형태로 저장된 이진트리를 의미합니다.

선형 자료구조 : 일렬로 저장된 구조 / 비선형 자료구조 : 계층적 형태로 저장된 구조
다진 트리 : 두개 이상의 자식 노드를 가지는 형태로 저장되는 트리

그래프와 트리의 차이가 무엇인가요?

참고자료

그래프의 종류 중 하나를 트리라고 할 수 있습니다.

하지만 트리는 계층 구조로 데이터를 저장하기 위해 루트 노드가 존재하고 노드별 자식 노드 개념으로 연결됩니다.

그래프는 노드간의 연결이 존재할수도 없을수도 있으며 순환이나 양방향 연결과 같은 형태로로 데이터가 저장될 수 있습니다.

순환성 : 그래프는 순환 구조가 나올 수 있다. / 트리는 순환 구조가 없다. 노드로 가능 방법은 정해져 있다.
계층구조 : 그래프 없을 수도 있다. / 트리는 무조건 계층을 가진다.
루트노드 존재 여부 : 그래프 존재가능 또는 아닐 수도 있다 / 트리는 무조건 존재한다.
연결성 : 그래프는 자유롭다 / 트리는 상대적으로 제한적이다.

이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

전위, 중위, 후위 탐색에 대해 간단히 설명하자면 다음과 같습니다.

전위 탐색 : 현재 노드 - 왼쪽 자식 노드 - 오른쪽 자식 노드
중위 탐색 : 왼쪽 자식 노드 - 현재 노드 - 오른쪽 자식 노드
후위 탐색 : 왼쪽 자식 노드 - 오른쪽 자식 노드 - 현재 노드

중위 트리로 데이터를 정렬된 순서대로 탐색 및 출력할 수 있습니다. 이는 이진 트리 탐색의 구조를 그대로 따라가면서 탐색하기 때문입니다.

이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해 주세요.

삽입, 삭제, 수정에 대한 시간 복잡도는 O(log N)으로 도출됩니다.

주요 연산을 위해 해당 데이터가 위치한 또는 위차할 노드로 이동 하는 과정에서 두개의 자식 노드에 대해서만 값을 비교해 추적해 나가기 때문입니다. 이진탐색트리로 데이터를 저장할 경우 트리의 높이가 log N으로 저장되기 때문입니다.

하지만 이건 균형이 잘 잡힌 형태로 저장된 트리의 한해서 해당되는 내용입니다. 만약 트리의 높이가 N에 가까워지면 가까워질수록 거쳐가야 하는 노드가 증가하므로 O(N)에 가까워질 수 있습니다. 이를 위해선 균형을 잘 지키는 형태로 트리에 데이터를 저장해야 합니다.

이진탐색트리의 한계점에 대해 설명해주세요.

균형이 잘 잡힌 형태의 트리가 아니라면 시간 복잡도가 O(N)으로 증가할 수 있습니다. 이는 트리의 높이가 올라가면서 탐색해야 하는 노드이 수가 N에 가까워지기 때문입니다. 이로 인해 연산의 효율성도 떨어지는 문제가 발생할 수 있습니다.

이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤식으로 값을 삽입하면 편향이 발생할까요?

삽입할 값과 루트 노드를 비교(Top-Down)
값이 작다면 왼쪽 자식 노드로 이동, 값이 크다면 오른쪽 자식 노드로 이동
리프노드에 도착할 때까지 1~2번 반복

삽입의 경우 위 방법으로 데이터를 추가할 노드를 찾아 삽입하면 됩니다. 하지만 삭제 작업은 삭제할 노드의 위치에 따라 달라집니다.

자식 노드가 없는 경우 : 그대로 삭제
자식 노드가 하나인 경우 : 삭제할 노드를 삭제하고 그 위치에 자식 노드를 이동
자식 노드가 두개인 경우 : 삭제할 노드를 삭제하고 왼쪽 서브트리에서 가장 큰값이나 오른쪽 서브트리에서 가장 작은 값을 이동

값이 편향되는 경우는 아래와 같을 수 있습니다.

특정 순서로 데이터가 순차적으로 추가되는 경우(오름차순, 내림차순) -> 입력되는 데이터가 일정하게 왼쪽 혹은 오른쪽 노드로 추가되면서 편향된 트리를 구성합니다.
삭제 시 위와 같은 규칙을 지키지 않는 경우

6. 힙에 대해 설명해 주세요.

이진 트리를 구현한 자료구조 중 하나로 완전이진트리에 해당합니다. 부모노드와 자식노드의 특정한 기준, 규칙을 가지고 데이터를 저장하는 자료구조입니다.

왼전 이진 트리란 마지막 레벨을 제외하고 모든 레벨의 노드가 가득 차 있는 형태를 의미합니다.

최대 힙 : 부모 노드가 자식 노드보다 크거나 같은 값을 가지는 형태

          9
        /   \
       7     6
      / \   / \
     5   3 2   4

최소 힙 : 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 형태

힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?

힙은 완전트리구조이기 때문에 중간에 빈값없이 배열로 저장할 수 있습니다. 저장하는 방식은 다음과 같습니다.

현재 노드 번호를 i라 할때,

루트 노드는 항상 인덱스 0 에 저장합니다.
다음과 같은 식을 통해 부모 노드와 자식 노드의 위치를 추적해 순서에 맞게 데이터를 저장할 수 있습니다.
- 현재 노드의 perent node의 번호 = (i - 1) / 2
- 현재 노드의 left child node의 번호 = i * 2 + 1
- 현재 노드의 right child node의 번호 = i * 2 + 2

힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.

힙의 삽입(Up-Heapify)

삽입할 값을 가장 마지막 노드에 추가합니다.
추가된 노드와 부모 노드의 값을 비교합니다.
(최대힙) 추가된 노드가 부모 노드보다 크다면 위치를 변경합니다. / (최소힙) 추가된 노드가 부모 노드보다 작다면 위치를 변경합니다.
1~3번을 반복해 더 이상 변경하지 않을 위치에 도착하면 끝납니다.

힙의 삭제(Down-Heapify)

노드값을 삭제합니다.
가장 마지막 노드를 루트노드로 이동합니다.
루트노드에서부터 자식 노드와 비교를 진행합니다.(최대힙이라면 두 자식 노드 중 큰 값, 최소힙이라면 두 자식 노드 중 작은 값)

삽입, 삭제 후 배열을 힙조정(Heapify)을 통해 완전트리구조를 계속 유지하기 때문입니다.

힙 구조 조회는 O(logN)으로 볼 수 있습니다. 하지만 루트 노드에 대한 조회는 O(1)입니다.

힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?

길이가 N인 배열을 힙조정하는데 O(logN)의 시간복잡도를 가집니다. 이 배열을 전체 힙조정한다면 시간복잡도는 O(NlogN)이 됩니다.

Stable : 동일한 값에 대해서 순서가 보장되는 정렬
Unstable : 동일한 값에 대해서 순서가 보장되지 않는 정렬

힙정렬은 정렬 과정에서 동일한 값에 대한 순서가 보장되지 않습니다. 그러므로 Unstable 합니다.

왜 굳이 힙을 쓰느냐?
자료구조 길이가 동적으로 변화하기 적합합니다.
빈 노드가 없이 완전 트리 형태로 저장되므로 메모리 사용의 효율성이 좋습니다.
최우선순위를 가진 노드만 가져오는 알고리즘에선 정렬과정에서만 Log N을 가지고 조회시에는 O(1)만큼의 시간복잡도를 가지므로 효율적입니다.
힙 정렬 알고리즘은 어떻게 동작하는가?
참고자료
N번째 수부터 루트 노드로 이동시켜 자식 노드들과 비교하면서 정렬을 진행
그래서 N Log N만큼의 시간복잡도를 가진다.
힙 편향 방지를 하는 방법?
빈 노드가 나오지 않도록 계속해서 힙조정 과정을 통해 완전 트리 형태를 유지하기 때문입니다.

7. BBST (Balanced Binary Search Tree) 와, 그 종류에 대해 설명해 주세요.

참고자료

균형 이진 탐색 트리라고도 할 수 있고 이진탐색 트리가 균형 있게 유지되어서 빠른 삽입, 수정, 삭제가 가능하도록 구현된 트리들을 의미합니다.

더 빠른 처리 수행이 가능한 것은 시간 복잡도를 O(Log N)으로 넘어가지 않도록 지켜낼 수 있기 때문입니다.

AVL 트리 : 참고 영상
Red-Black 트리 : 참고 영상
2-3-4 트리 : 노드의 자식노드를 4개까지 허용하는 방식의 트리이며 3개의 키와 4개의 자식 노드를 가질 수 있습니다. -> 4 자식을 가능한데 이진 트리?

Red Black Tree는 어떻게 균형을 유지할 수 있을까요?

AVL 트리에서는 삽입, 삭제가 발생할 때마다 균형률을 체크해 4가지 상황(LL, RR, LR, RL)에 대한 노드 회전을 진행해 균형률을 맞춥니다.

하지만 Red-Black 트리는 이러한 회전과 더불어 색 변환(Recoloring)을 통해 조금 더 간단한 형태로 균형을 맞춥니다.

색 변환(Recoloring) : 부모 노드의 형제가 있는 경우
회전(Rotation) : 부모 노드의 형제가 없는 경우

Red Black Tree의 주요 성질 4가지에 대해 설명해 주세요.

노드는 Red 아니면 Black이다.
루트 노드는 항상 black이다.
모든 리프 노드는 Black이다.
Red 노드의 자식 노드는 Black이다.

2-3-4 Tree, AVL Tree 등의 다른 BBST 가 있음에도, 왜 Red Black Tree가 많이 사용될까요?

균형도는 다른 두 트리에 비해 덜 균형적일지 몰라도 느슨한 조건으로 인해 삽입/삭제에 있어 재배치 가능성이 상대적으로 낮습니다. 그래서 동적 처리를 위한 자료구조로는 Red-Black Tree가 더 어울립니다. 하지만 데이터 조회의 속도가 중요하다면 조금 더 엄격한 균형을 지키는 AVL이 더 어울릴 수 있습니다.

로테이션 자체는 O(1)의 시간 복잡도를 가지지만 하나의 연산으로 인해 로테이션이 여러번 동작할 수 있다면 O(N)까지도 발생할 수 있습니다. 그래서 Red-Black 트리가 좀 더 느슨한 규제를 가지게 됩니다. —

8. 정렬 알고리즘에 대해 설명해 주세요.

정렬 알고리즘이란 주어진 데이터를 순서에 맞게 재배치 시키는 방식을 정의한 걸로 이해할 수 있습니다.

Quick Sort와 Merge Sort를 비교해 주세요. -> 분할 정보

Quick Sort : 참고 영상
- pivot값을 기준으로 pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 재배치를 시킨다.
- 재배치된 배열을 pivot을 기준으로 하위 배열로 구분하고 각각의 배열에서 동일하게 재배치를 진행한다.
Merge Sort : 참고 영상
- 입력받은 배열을 쪼개고 쪼개 길이가 2인 여러개의 배열로 나눈다.
- 각각의 배열을 정렬한다.
- 합친 배열들을 두개씩 합쳐나가며 정렬한다.
- 최종적으로 입력받은 배열이 정렬된 형태로 저장된다.

두 알고리즘 모두 평균적으로는 O(N log N) 의 복잡도(N개의 값을 logN만큼의 횟수로 정렬하기 때문에)를 가지지만 Quick 정렬의 경우 최악에 상황에선 O(N^2)의 복잡도를 가질 수 있습니다. 퀵 정렬은 내부 정렬로 추가적인 메모리가 필요하지 않지만 병합 정렬은 외부 정렬로 추가적인 메모리가 필요합니다.

추가로 작은 배열의 경우 퀵정렬이 더 빠르지만 큰 배열의 경우 병합 정렬이 더 빠릅니다.

Quick Sort에서 O(N^2)이 걸리는 예시를 들고, 이를 개선할 수 있는 방법에 대해 설명해 주세요.

참고자료

퀵정렬에서 O(N^2)이 나오는 경우는 지정하는 pivot이 항상 최소 혹은 최고값을 지정하면서 재귀가 깊어지기 때문입니다.

이를 해결하기 위해선 pivot을 최대한 중앙값으로 맞출 수 있어야 하며 이를 위해 제시해볼 방법은 아래와 같습니다.

난수를 사용하는 퀵 정렬 개선 : 난수를 pivot으로 지정해 확률적으로 성능적인 개선을 기대해 볼 수 있습니다.
삽입 정렬을 사용한 퀵 정렬 개선 : 특정 배열의 길이 이하에선 삽입정렬, 길이 이상에선 퀵정렬을 사용해 재귀의 깊이를 줄여주면서 성능 개선을 기대해 볼 수 있습니다.
세 값의 중위값을 사용한 퀵 정렬 개선 : 배열의 가장 왼쪽, 오른쪽, 중간에 위치한 값 중 중간값을 pivot으로 지정하는 방식입니다. 이를 활용하면 최소한 최악의 상황은 면할 수 있어 더 나은 시간 복잡도를 보장할 수 있습니다.

Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable 한지 설명해 주세요.

Stable Sort란, 같은 값에 대해서 입력된 순서를 보장하는 정렬 방식을 의미합니다. 즉 같은 숫자인 5가 배열에 여러번 포함되어 있을 때, 정렬 이후에도 초기에 배열에 저장된 5들의 순서는 보장되어야 한다는 것입니다.

Stable한 성격을 가진 정렬 알고리즘은 Merge sort, Insertion Sort, Bubble Sort, Radix sort 등이 있습니다.

퀵정렬은 가능하게 구현 가능

Unstable한 성격을 가진 정렬 알고리즘은 Quick sort, Heap sort, Sellect sort가 있습니다.

삽입 정렬(Insertion Sort)는 배열 두번째 값부터 키로 지정해 키보다 앞에 있는 값들을 순차적으로 비교해 정렬하는 방식입니다.

Merge Sort를 재귀를 사용하지 않고 구현할 수 있을까요?

Bottom-Up Merge Sort 방식으로 반복문을 통해 구현할 수 있습니다.

재귀를 사용하는 방식 : 분할 정복(Divide and Conquer) 알고리즘으로 전체 배열에서 쪼개는 방식으로 진행
반복문을 사용하는 방식 : 가장 작은 배열부터 점차적으로 커지는 배열을 정렬하고 합치는 방식

Radix Sort에 대해 설명해 주세요.

참고자료

기수 정렬이라고도 하며 자리수 별로 값을 배열하는 방식으로 동작합니다.

일의 자리에 대해서 정렬
십의 자리에 대해서 정렬
d의 자리에 대해서 정렬

시간 복잡도는 숫자의 자리수가 d인 경우, O(d*N)의 복잡도를 가집니다.

구현을 위해선 0~9까지의 큐가 필요합니다. 자리수 별로 값을 비교할 때 값에 따른 큐에 데이터를 순차적으로 삽입/추출하기 때문입니다.

이로 인해 Radix Sort는 Stable한 Sort입니다.

Bubble, Selection, Insertion Sort의 속도를 비교해 주세요.

참고자료

Bubble Sort : 배열의 앞에서부터 인접한 두 값을 차례대로 비교해 정렬하는 방식
- 모든 값에 대한 비교 및 교환을 해야 한다.
Selection Sort : 가장 작은 수의 인덱스 위치를 찾아내고 전체 배열 탐색이 종료될 때마다 해당 인덱스 위치의 값을 앞으로 옮겨주는 방식
- 비교할 값은 루프가 진행할 수록 줄어들지만 그 내에서 모든 값을 비교해야 한다.
Insertion Sort : 배열의 숫자를 차례대로 앞의 값들과 비교해 정렬하는 방식
- 비교할 값도 줄어들고 특정 지점에서 조건에 부합하면 빠르게 루프가 종료될 수 있다.

모두 동일하게 O(N^2)의 시간 복잡도를 가지지만 알고리즘의 동작 방식에 따라 속도의 차이가 존재합니다.

Insertion < Selection < Bubble

값이 거의 정렬되어 있거나, 아예 정렬되어 있다면, 위 세 알고리즘의 성능 비교 결과는 달라질까요?

Insertion Sort는 이미 정렬되어 있는 경우에 O(N)의 시간 복잡도를 가질 수 있습니다. 하지만 나머지 두 정렬의 경우에는 여전히 O(N^2)의 시간 복잡도를 가집니다.

다만 정렬이 역순으로 되어 있다면 세 알고리즘이 비슷한 성능을 낼 수도 있다고 생각을 합니다.

본인이 사용하고 있는 언어에선, 어떤 정렬 알고리즘을 사용하여 정렬 함수를 제공하고 있을까요?

참고자료

Arrays.sort()
- Dual-Pivot Quick Sort 방식을 사용했습니다. 간단하게 설명해 파티션을 2개가 아닌 3개로 나눠 재귀적으로 처리하는 방식입니다.
- 보통적으로 O(N log N)의 시간 복잡도를 보장하지만 최악의 경우 O(N^2)의 복잡도를 나타낼 수 있습니다.
Collection.sort()
- TimSort 방식을 사용합니다. TimSort 방식은 병합 정렬과 삽입 정렬을 하이브리드 형식으로 사용하는 방식입니다. 특정 배열의 길이 이하에는 삽입정렬, 이상인 경우에는 병렬 정렬을 통해 정렬을 수행합니다.
- O(N log N)의 시간 복잡도를 보장합니다.

삽입 정렬의 경우, O(N^2)의 복잡도를 가지지만 작은 크기의 배열에선 크게 적용을 받지 않습니다.

정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?

참고자료

외부 정렬 알고리즘을 사용할 수 있습니다. 메모리가 수용할 수 있는 크기만큼 데이터를 분활해 읽어오고 내부 정렬 알고리즘을 통해 정렬된 파일을 여러개로 저장합니다. 분리되어 저장된 파일들을 두개 이상씩 읽어와 정렬하고 합병하는 방법을 하나의 정렬된 데이터 파일이 나오기까지 반복하면 가능합니다.

내부적으로 정렬하는 방식은 적절한 알고리즘을 선택할 수 있을 것 같습니다. 퀵정렬이나 힙정렬과 같은..

시간 복잡도는 N 크기의 파일을 M 크기의 메모리로 동작할 경우 O(log (N/M))의 복잡도를 가집니다.

9. 그래프 자료구조에 대해 설명하고, 이를 구현할 수 있는 두 방법에 대해 설명해 주세요.

그래프 자료구조는 정점(vertex, 노드)들과 간선(edge, 링크)들로 이루어진 비선형 자료구조입니다. 정점은 개체를 나타내고, 간선은 정점들 사이의 관계를 나타냅니다. 노드 별 차수(degree)는 하나의 노드에 링크로 연결된 노드의 수를 의미합니다. 그래프는 네트워크 모델, 지도, 소셜 네트워크 등 다양한 문제를 표현하는데 사용됩니다.

구현 방법은 아래와 같습니다.

인접 행렬
- 노드간의 연결 여부를 배열로 표현
- 공간 복잡도 : O(N^2)
- 시간 복잡도
  - 두 노드의 연결 여부 확인 시 : O(1)
  - 하나의 노드 연결된 모든 노드 확인 시 : O(N)
인접 리스트
- 노드 간의 연결 여부를 링크드 리스트로 표현
- 공간 복잡도 : O(N+E) E는 간선의 총개수를 의미합니다.
- 시간 복잡도
  - 두 노드의 연결 여부 확인 시 : O(degree)
  - 하나의 노드 연결된 모든 노드 확인 시 : O(degree)

각 방법에 대해, “두 정점이 연결되었는지” 확인하는 시간복잡도와 “한 정점에 연결된 모든 정점을 찾는” 시간복잡도, 그리고 공간복잡도를 비교해 주세요.

인접 행렬
- 공간 복잡도 : O(N^2)
- 시간 복잡도
  - 두 노드의 연결 여부 확인 시 : O(1)
  - 하나의 노드 연결된 모든 노드 확인 시 : O(N)
인접 리스트
- 공간 복잡도 : O(N+E) E는 간선의 총개수를 의미합니다.
- 시간 복잡도
  - 두 노드의 연결 여부 확인 시 : O(degree)
  - 하나의 노드 연결된 모든 노드 확인 시 : O(degree)

정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까요?

인접 행렬의 경우, 노드간의 연결 상태를 확인하거나 간선의 수가 많을 경우 유리합니다.

간선의 개수가 많을 경우, 인접 리스트는 메모리 공간도 많이 차지하게 되며 정점간의 연결상태를 확인할때 노드별 차수만큼 조회해야 하는 필요가 있기 때문입니다.

이에 반해 인접 행렬로 구현할 경우 메모리는 N^2로 고정적이고, 두 노드의 연결 여부를 확인할 때에도 O(N)으로 고정적이기 때문에 인접 행렬이 좀 더 적합하다고 할 수 있습니다.

반대로 인접 리스트가 유리한 경우는 노드는 많지만 간선의 수가 적거나 노드의 연결된 리스트를 확인해야 하는 경우가 있습니다.

사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.

사이클이란 특정 정점으로 부터 시작한 간선들의 경로가 다시 시작 정점으로 돌아오는 경우를 의미합니다. 이는 무뱡항 그래프에선 해당하지 않고 방향 그래프에서 해댱하는 문제입니다.

이러한 사이클이 없다고 해서 모든 그래프가 트리라고 볼 수는 없습니다. 사이클 뿐만 아니라 다른 조건에도 만족해야 트리라고 할 수 있습니다.

사이클이 없이 모든 노드가 간선으로 연결되어야 한다.
간선의 수가 N개 라면 노드는 N+1만큼 존재해야 한다. 즉, 간선의 수가 노드의 수보다 1만큼 적어야 한다.

추가로 트리는 계층적인 구조를 가져야 하므로 무방향이나 양방향 간선를 가질 수 없습니다.

  
   A
  / \
 B---C

위 예시처럼 양방향으로 연결되거나 간선의 수가 노드의 수-1이 아니라면 트리라고 볼 수 없습니다.

무방향 그래프를 인접 행렬로 표현하면 대칭적인 구조가 나옵니다.

10. 그래프에서, 최단거리를 구하는 방법에 대해 설명해 주세요.

BFS(너비 우선 탐색)
- 가중치가 없거나 일정한 경우(최단거리 우선 탐색을 하지 않기 때문에 최단거리를 보장할 수 없습니다.)
- 큐 사용
- O(V+E)
다익스트라 알고리즘(참고자료)
- 양의 가중치가 있는 경우
- 우선순위 큐를 사용하는 경우 O(E Log V) / 아니면 O(V^2)
- 시작노드에서 다른 노드로 이동할 때 최저 가중치를 실시간으로 업데이트하는 방식으로 DP라고도 할 수 있고 그리디 알고리즘이라고도 할 수 있다.
- 최적의 노드로 우선 이동을 하기 때문에 음의 가중치에 대한 검증을 하기 전에 도착 노드에 도착해버리면 이를 고려하지 못하게 된다.
벨만-포드 알고리즘(참고자료)
- 음의 가중치에 대한 고려까지 필요한 경우, O(V*E)
- 다익스트라 알고리즘은 이미 거처간 노드에 대해선 더 이상 조회하지 않지만 벨만-포드 알고리즘은 음의 가중치에 대한 검증이 필요해 노드를 거쳐갈 때마다 모든 간선에 대한 검증을 거쳐야 합니다.
플로이드-워셜 알고리즘(참고 자료)
- 모든 노드들간의 최단거리를 구하는 방식으로 하나의 노드를 중간노드로 보고 다른 노드들이 서로 접근할 수 있는 최소거리를 업데이트하는 방식입니다.
- 시간 복잡도는 O(N * N^2)로 O(N^3)을 가지게 됩니다.
- 노드를 한번씩 중간 지점으로 지정 * 각각의 노드가 중간지점을 통해 갈 수 있는 최단거리 계산

우선 순위 큐를 사용하는 경우 시간 복잡도가 O(E Log E)가 아니라 O(E Log V)인 이유
모든 간선에 대해서 최소 가중치를 비교해야 한다.
각 간선을 우선순위큐에 삽입하고 정렬해야 한다.(큐의 길이가 V 이상으로 커질 수 없다.)
그래서 O(E Log V)가 된다.
O(V Log V)라고 볼 수도 있지만 보통 E가 V보다 크므로 E로 생각하는 것이 보편적이다.

트리에서는 어떤 방식으로 최단거리를 구할 수 있을까요? (위 방법을 사용하지 않고)

LCA(최소 공통 조상)라는 개념을 사용해 볼 수 있습니다.

LCA를 구하는 방식은 다음과 같습니다.

두 노드의 깊이를 계산한다.
계산된 노드 중 깊이가 더 깊은 노드의 깊이를 더 얕은 노드의 깊이 만큼 맞출때 까지 부모노드로 이동한다.
깊이가 맞아졌다면 동시아 부모 노드를 찾아가며 같은 노드가 나올 때까지 반복한다.
같은 노드에 도착했다면 해당 노드가 LCA에 해당한다.

이를 가지고 두 노드의 최단 거리를 계산하는 방법은 다음과 같습니다.

최단 거리 = (노드1의 깊이 - LCA의 깊이) + (노드2의 깊이 - LCA의 깊이)

즉 트리에서 최단거리는 노드들의 LCA에서 부터 시작되는 깊이를 더하면 되며 이 방식의 시간 복잡도는 O(log N)이라고 볼 수 있습니다.

다익스트라 알고리즘에서, 힙을 사용하지 않고 구현한다면 시간복잡도가 어떻게 변화할까요?

힙을 사용하는 경우, 전체 간선에 대한 조회를 하면서 우선순위 큐는 최악의 경우 모든 노드가 거쳐갈 수 있으므로 O(E log V)라고 할 수 있습니다.

하지만 힙을 사용하지 않고 큐를 사용하는 경우, 전체 노드에 대해 조회하고 각 노드에서 연결된 다른 노드로 가는 최저 가중치를 구해야하므로 O(V^2)가 됩니다.

정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 알고리즘이 효율적일까요?

만약 정점의 개수가 크지 않다면 플로이드-워셜 알고리즘을 고려해볼만 하다고 생각합니다.

위 플로이드-워셀 방식을 제외한 세 방식 모두 간선의 개수가 시간 복잡도에 영향을 주고 있습니다. 그렇기에 간선의 개수가 매우 많다면 그만큼 비효율적인 작업이 진행될 수 있습니다.

A* 알고리즘에 대해 설명해 주세요. 이 알고리즘은 다익스트라와 비교해서 어떤 성능을 낼까요? (참고자료)

에이 스타 알고리즘이라고 부르며 다익스트라 알고리즘을 발전시킨 형태입니다. 시작지점에서 모든 노드에 대한 최소거리를 측정하는 것이 아닌 도착지점까지 지정해 좀 더 효율적인 방식을 보여줍니다.

f(n) = g(n) + h(n)
     = 시작 노드에서 현재 위치한 노드까지의 가중치 + 현재 위치한 노드에서 도착지점까지의 예상 가중(휴리스틱 거리 측정값)

휴리스틱 거리 측정값은 도착지점에서 각각의 노드에 대한 거리를 참고해볼 수 있도록 임의로 지정하는 값이라고 볼 수 있습니다.(측정 방식 중에는 멘허튼 거리 라는 방법도 있습니다.)

도착 지점에 대한 값을 가지고 휴리스틱 거리 측정값을 계산한 다음, 이 값들을 가지고 출발지점에서 부터 이동할 노드들을 선택하는데 참고해볼 수 있어서 불필요한 노드에 대한 접근을 막아줍니다.

예를 들면 도착지점과 반대방향인 노드에 대해선 휴리스틱 측정값이 높아서 측정 대상에서 제외가 될 수 있습니다. 측정 범위를 축소시켜줌으로써 좀 더 효율적인 알고리즘 방식이 될 수 있습니다.

음수 간선이 있을 때와, 음수 사이클이 있을 때 각각 어떤 최단거리 알고리즘을 사용해야 하는지 설명해 주세요.

두가지 알고리즘을 선택할 수 있으며 상황에 따라 더 적합한 알고리즘을 선택하는 것이 좋다고 생각합니다.

벨만-포드 알고리즘 : 음수 간선에 대한 고려가 가능, 음수 사이클의 경우가 발생하는 것을 인지하고 추가적인 함수를 통해 별도 처리가 가능
플로이드-워셜 알고리즘 : 음수 간선과 음수 사이클 모두 데이터에 포함해서 처리 가능

그래서 특정 시작 지점에서 도착 지점에 대한 최저 거리를 구하고 싶다면 벨만-포드, 모든 노드들의 최저 거리를 구하고 싶다면 플로이드를 선택할 수 있습니다. 또한 간선의 크기가 길다면 플로이드가 시간 복잡도 면에선 조금 더 유리할 수 있습니다.

추가 작성 내용

Double Hashing에 대한 단점 해결 방법

키워드 : 서로소, Re-hashing, 로드 팩터

힙

힙을 사용하는 근본적인 이유
힙 정렬 알고리즘은 어떻게 동작하는가?
힙 편향 방지를 하는 방법?

음수간선과 음수 사이클 존재에 따라 사용 가능한 최단거리 알고리즘

음수 간선에 대해선 플로이드는 안된다. 음수 사이클의 경우에는 두 알고리즘 모두 된다.
음수 간선과 음수 사이클의 경우로 나눠서 고민해봐야겠다.

[CS 스터디] 자료구조 1

1. 시간복잡도와 공간복잡도에 대해 설명해 주세요.

Big-O, Big-Theta, Big-Omega 에 대해 설명해 주세요.

다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?

O(1)은 O(N^2) 보다 무조건적으로 빠른가요?

2. 링크드 리스트에 대해 설명해 주세요.

일반 배열과, 링크드 리스트를 비교해 주세요.

링크드 리스트를 사용해서 구현할 수 있는 다른 자료구조에 대해 설명해 주세요.

3. 스택과 큐에 대해서 설명해 주세요.

스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.

시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?

Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산/하는 방법에 대해 설명해 주세요.

Deque는 어떻게 구현할 수 있을까요?

(C++ 한정) Deque의 Random Access 시간복잡도는 O(1) 입니다. 이게 어떻게 가능한걸까요?

4. 해시 자료구조에 대해 설명해 주세요.

값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요? -> 가장 어려웠던 부분

해시값이 충돌했을 때, 어떤 방식으로 처리할 수 있을까요?

본인이 사용하는 언어에서는, 어떤 방식으로 해시 충돌을 처리하나요?

Double Hashing 의 장점과 단점에 대해서 설명하고, 단점을 어떻게 해결할 수 있을지 설명해 주세요.

5. 트리와 이진트리, 이진탐색트리에 대해 설명해 주세요.

그래프와 트리의 차이가 무엇인가요?

이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해 주세요.

이진탐색트리의 한계점에 대해 설명해주세요.

이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤식으로 값을 삽입하면 편향이 발생할까요?

6. 힙에 대해 설명해 주세요.

힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?

힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.

힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?

7. BBST (Balanced Binary Search Tree) 와, 그 종류에 대해 설명해 주세요.

Red Black Tree는 어떻게 균형을 유지할 수 있을까요?

Red Black Tree의 주요 성질 4가지에 대해 설명해 주세요.

2-3-4 Tree, AVL Tree 등의 다른 BBST 가 있음에도, 왜 Red Black Tree가 많이 사용될까요?

8. 정렬 알고리즘에 대해 설명해 주세요.

Quick Sort와 Merge Sort를 비교해 주세요. -> 분할 정보

Quick Sort에서 O(N^2)이 걸리는 예시를 들고, 이를 개선할 수 있는 방법에 대해 설명해 주세요.

Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable 한지 설명해 주세요.

Merge Sort를 재귀를 사용하지 않고 구현할 수 있을까요?

Radix Sort에 대해 설명해 주세요.

Bubble, Selection, Insertion Sort의 속도를 비교해 주세요.

값이 거의 정렬되어 있거나, 아예 정렬되어 있다면, 위 세 알고리즘의 성능 비교 결과는 달라질까요?

본인이 사용하고 있는 언어에선, 어떤 정렬 알고리즘을 사용하여 정렬 함수를 제공하고 있을까요?

정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?

9. 그래프 자료구조에 대해 설명하고, 이를 구현할 수 있는 두 방법에 대해 설명해 주세요.

각 방법에 대해, “두 정점이 연결되었는지” 확인하는 시간복잡도와 “한 정점에 연결된 모든 정점을 찾는” 시간복잡도, 그리고 공간복잡도를 비교해 주세요.

정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까요?

사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.

10. 그래프에서, 최단거리를 구하는 방법에 대해 설명해 주세요.

트리에서는 어떤 방식으로 최단거리를 구할 수 있을까요? (위 방법을 사용하지 않고)

다익스트라 알고리즘에서, 힙을 사용하지 않고 구현한다면 시간복잡도가 어떻게 변화할까요?

정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 알고리즘이 효율적일까요?

A* 알고리즘에 대해 설명해 주세요. 이 알고리즘은 다익스트라와 비교해서 어떤 성능을 낼까요? (참고자료)

음수 간선이 있을 때와, 음수 사이클이 있을 때 각각 어떤 최단거리 알고리즘을 사용해야 하는지 설명해 주세요.

추가 작성 내용

Double Hashing에 대한 단점 해결 방법

힙

음수간선과 음수 사이클 존재에 따라 사용 가능한 최단거리 알고리즘

Further Reading

[CS 스터디] 데이터베이스 1

CS 기초

[CS 스터디] 데이터베이스 2