기술 인터뷰 준비 - 자료구조

기술 인터뷰자료구조CS

기술 인터뷰 준비 - 자료구조

문제 출처 : https://github.com/VSFe/Tech-Interview

시간 복잡도 / 공간 복잡도

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

    시간 복잡도는 입력 크기 N이 증가할 때 알고리즘의 실행 시간이 어떻게 증가하는지를 나타내는 척도이고, 공간 복잡도는 입력 크기에 따라 알고리즘이 추가적으로 사용하는 메모리 양이 어떻게 증가하는지를 나타냄

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

    Big-O : 알고리즘의 성장 상한을 나타냄. 최대로 이 정도까지만 증가한다고 보장
Big-Theta : 상한과 하한이 같은 경우. 알고리즘의 정확한 증가율을 나타내는 tight bound
Big-Omega : 알고리즘의 성장 하한. 최소한 이 정도는 걸린다는 의미
-> 평균과 최악을 의미하는 개념이 절대 아님

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

    Big-O는 알고리즘의 성장 상한을 보장하기 때문에 "이 알고리즘은 최악의 상황에서도 이 정도 이하에서 동작한다"는 확신을 줌
또한 여러 알고리즘을 비교할 때 상수나 하드웨어 환경을 배제하고 증가율만으로 비교할 수 있어 실무와 설계에서 유용

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

    아니다. Big-O는 증가율을 나타내기 때문에 입력 크기가 충분히 커졌을 때의 경향을 비교
O(1)의 연산이 매우 큰 상수 비용을 가진다면, 작은 N에서는 오히려 O(N^2)이 더 빠를 수 있음

링크드 리스트

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

    링크드 리스트는 노드들이 포인터를 통해 연결된 선형 자료구조. 메모리 공간이 연속적일 필요가 없고, 각 노드는 값과 다음 노드를 가리키는 포인터를 포함.
특징으로는 Random Access가 불가능함. 특정 위치에 접근하려면 O(N)
삽입/삭제가 포인터만 변경하면 되므로 O(1)
배열처럼 메모리 재배치가 없어 메모리 효율 유리
리스트 병합이 head/tail 조작으로 O(1)

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

    배열은 메모리의 연속된 공간에 할당, 인덱스 접근이 O(1)로 빠르고 Random Access 가능. 중간 삽입/삭제가 O(N)으로 느리고 고정 크기로 메모리가 가득 차면 재할당 필요. 연속 메모리 구조로 캐시에 친화적임
링크드 리스트는 불연속적으로 노드와 포인트로 이루어져 있음. 순차 접근만 가능함. 위치 도달후 삽입 삭제는 O(1)로 빠름. 크기는 따로 확장할 필요가 없고 불연속적으로 캐시에 친화적이지 않음

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

    다양한 자료 구조 구성 가능
Stack : head에 삽입, 삭제
Queue : head/tail 관리
Hash Chaining : 동일한 버킷을 LinkedList로 연결
Graph Adjacency List
Deque, Priority Queue 등
    • Java의 LinkedList는 List<> 인터페이스와 Deque<> 인터페이스를 구현

스택 / 큐 / 데크

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

    스택은 LIFO 구조로 마지막에 들어온 데이터가 가장 먼저 나옴
큐는 FIFO 구조로 먼저 들어온 데이터가 먼저 나옴

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

    스택 2개로 큐를 만들려면 1개의 스택은 enqueue 전용으로, 나머지 스택은 dequeue 전용
push는 enqueue 스택에 push -> O(1), pop은 dequeue 스택이 비었을 경우 enqueue 스택의 모든 값을 dequeue 스택으로 옮기고 한 개씩 pop
최악은 O(N)이지만 평균적으로 amortized(1)

큐 2개로 스택을 만들 때 push를 비싸게 하거나, pop을 비싸게 선택 필요
push를 비싸게 하는 경우 빈 큐에 값을 넣고, 나머지 큐의 모든 요소를 이동 -> push는 O(N), pop은 O(1)

pop을 비싸게 하는 경우는 반대

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

    스택은 배열로 완벽히 구현 가능 -> top 변수를 통해 접근하면 O(1)

큐는 원형 배열로 front/rear를 회전시키면 enqueue, dequeue 모두 O(1)로 구현 가능

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

    각각 전위 표기법, 중위 표기법, 후위 표기법

prefix : + 3 5 연산자가 앞에 위치
infix : 3 + 5 연산자가 가운데 위치
postfix : 3 5 + 연산자가 뒤에 위치

postfix 계산 : 숫자는 push, 연산자를 만나면 스택에서 두 개 pop하고 계산 -> 다시 push -> 반복 후 마지막 남은 값이 결과

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

    Doubly linked list 기반 : head/tail 양쪽에서 삽입/삭제 가능 -> O(1)
Circular Buffer 기반 : front/rear 포인터를 원형으로 회전 -> O(1)
---
Java에서 Deque 인터페이스를 구현하는 주요 클래스는 2가지
1. ArrayDeque : 원형 배열
2. LinkedList : 이중 연결 리스트
Java에서도 공식적으로 ArrayDeque 사용을 권장
    • ArrayDeque가 원형 배열을 사용하면서 Random Access가 안되는 이유
      1. Deque의 추상적 의미를 지키기 위해서
      2. 구조상 O(1)로 접근 가능하지만, 의미적 일관성이 깨짐
        • Deque는 순서를 논리적으로 보장하지만 내부 head의 위치는 항상 0이 아님
        • 배열처럼 접근하는 것은 논리적 뷰와 물리적 뷰가 섞이므로 혼란을 피하기 위해
      3. 일반적인 List 처럼 중간에 삽입/삭제시 잘못된 성능 사용을 유도할 수 있음
      4. ArrayDeque가 List 인터페이스를 구현하지 않음

해시

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

    키(Key)를 고정된 크기의 인덱스(Hash Value)로 변환하여 빠르게 데이터에 접근하는 자료구조
평균 시간 복잡도
- 검색 : O(1)
- 삽입 : O(1)
- 삭제 : O(1)

  2. 값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요?

    1. Uniformity(균등성) : 입력 분포가 편향되더라도 해시 값은 버킷에 균등하게 퍼져야 한다.
2. Low clustering(군집 최소화) : 비슷한 키들이 비슷한 해시 값을 만들지 않아야 한다.
3. Deterministic(결정적) : 같은 입력은 항상 같은 출력이어야 한다.

충돌 최소화
1. 해시 공간이 클 수록 충돌은 감소
 - 메모리 낭비 & 해시 함수가 안좋으면 여전히 한쪽에 몰림
2. 정수의 경우 비트 섞기(Mixing), 곱셈 기반 해시
3. 문자열의 경우 Polynomial Rolling Hash 또는 MurmurHash, CityHash 같은 검증된 알고리즘 사용

    • Mixing

      • 비트 패턴을 섞어(Permute/Mix) 해시 값을 퍼뜨림

        uint64_t x = key;
x ^= x >> 33;
x *= 0xff51afd7ed558ccd;
x ^= x >> 33;
x *= 0xc4ceb9fe1a85ec53;
x ^= x >> 33;

    • 곱셈 기반 해시

      h(k) = (k * A) >> (w - m)
      • k : 정수 입력값
      • A : 0~1 사이의 실수 (특정 상수)
      • w : CPU word size (보통 32/64)
      • m : 해시 테이블 크기 비트 수
      • 정수 k에 특정 상수 A를 곱하면 비트가 고르게 섞인다 → 균일 분포

    • Polynomial Rolling Hash

      h(s) = (s[0] * p^0 + s[1] * p^1 + s[2] * p^2 + ... ) % M
      • p : 보통 소수 (예: 31, 53, 131 등)
      • M : 매우 큰 소수(충돌 방지를 위해 사용)
      • s[i] : 문자 ASCII 또는 유니코드 값

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

    비둘기 집 원리에 의해 충돌은 피할 수 없음

1. Seperate Chaining(분리 연결법)
 - 예) table[3] : "dog" -> "cat" -> ...
 - 해시 버킷마다 Linked List / Tree 사용
 - 충돌된 값들을 해당 버킷의 리스트에 저장
 - 장점
  - 구현 간단
  - Load Factor 높아도 안정적
  - 삭제 쉬움
 - 단점
  - 추가 메모리 필요
  - 최악의 경우 O(N)
2. Open Addressing(개방 주소법)
 - 배열 내에서 빈 공간을 찾으며 저장
 - 대표 방식
  - Linear Probing
   - index, index + 1, index + 2, ... 차례대로 빈 칸 찾기
  - Quadratic Probing
   - index + 1^2, index + 2^2, ...
  - Double Hashing
 - 장점
  - 별도 메모리 안 듦
  - 캐시 친화적
 - 단점
  - Load Factor가 높아지면 탐색 비용 커짐
  - 삭제가 상대적으로 까다로움

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

    Java HashMap의 충돌 처리 방식 : 내부적으로 Sperate Chaining + Tree화를 사용

충돌 처리 단계
1. 같은 해시 버킷에 들어오면 기본적으로 LinkedList에 삽입
2. 한 버킷의 연결 리스트 길이가 8이상이면 Red-Black Tree로 전환
 - 탐색/삽입/삭제 : O(log N)
3. Load Factor 초과 시 -> Rehash(배열 2배 증가)

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

    Open Addressing 방식에서 h2(Key)라는 두 번째 해시 함수를 사용하여 다음 위치를 찾는 기법
h1(key) = 첫 번째 해시
h2(key) = 두 번째 해시(0이 되지 않게 설계)
index(i) = (h1(key) + i * h2(key)) % tableSize

장점
1. 클러스터링 최소화
2. 해시 분포가 매우 고르게 됨
3. 해시 테이블 크기 커지지 않아도 성능 안정적

단점
1. 두 번 hash 비용 -> overhead 증가
2. h2(key)와 table size를 잘못 설계하면 특정 버킷만 방문하고 다른 버킷에 접근하지 못할 수 있음 -> 서로소여야 모든 버킷 방문 가능
3. 삭제 구현이 어려움

단점 해결책
1. tableSize를 소수로 설정
2. h2(key) = 1보다 큰 홀수 또는 tableSize보다 작은 값으로 보장
3. 해시 함수는 경량화 사용

  6. Load Factor에 대해 설명해 주세요. 본인이 사용하는 언어에서 해시 자료구조는 Load Factor에 관련한 정책이 어떻게 구성되어 있나요?

    Load Factor = 저장된 데이터 개수 / 버킷 배열 크기
예) capacity = 16, size = 12 -> Load Factor = 0.75

Load Factor가 높을수록 충돌 확률 증가 -> 충돌이 많아지면 탐색 시간 증가

해시 테이블의 성능을 유지하려면 Load Factor를 일정 이하로 유지 -> Rehash 필요

Java의 Load Factor 정책
HashMap
- 기본 Load Factor : 0.75
- 이 값을 넘기면 capacity를 2배로 늘리고 Rehash
왜 0.75인가?
- 메모리 효율과 충돌 확률의 타협점
- 실제로 평균적으로 가장 성능 좋은 값으로 알려져 있음

  7. 다른 자료구조와 비교하여, 해시 테이블은 멀티 스레드 환경에서 심각한 수준의 Race Condition 문제에 빠질 위험이 있습니다. 성능 감소를 최소화 한 채로 해당 문제를 해결할 수 있는 방법을 설계해 보세요.

    해시 테이블은 내부적으로 배열 + 포인터 조작 + rehash 등이 있어서 여러 스레드가 동시에 만지면 쉽게 꼬임

예)
Thread A : put(k1, v1) -> bucket[5] 수정
Thread B : put(k2, v2) -> 같은 bucket[5] 수정

동시에 next 포인터를 건드리면
1. 데이터 손상(Data corruption)
2. Infinite loop
3. 잘못된 참조

rehash 도중에 다른 스레드가 접근하면
1. 같은 키를 두 번 넣거나
2. ArrayIndex 에러
3. 데이터 구조 전체가 깨질 수 있음

해결 전략
1. Segmented Locking(구간 잠금)
 - 해시 테이블을 여러 segment로 나누고 각 segment마다 lock을 둠 -> 전체 구조를 잠그지 않고 부분 잠금으로 동시성 상승
 - ConcurrentHashMap 1.x 방식
2. CAS(Compare-And-Swap)를 통한 Lock-Free 구조
 - 특정 버킷에 삽입/삭제 시 CAS로 경쟁 해결
 - Lock을 거의 안 사용 -> 성능 매우 높음
 - ConcurrentHashMap 2.x 이후 방식
3. Read-Write Lock
 - 읽기는 lock-free
 - 쓰기만 lock -> 읽기 많은 환경에서 성능 좋음
4. Immutable Bucket + Copy-on-Write
 - Hash Trie, COWHashTable 등
 - 매우 높은 안정성을 가지지만 메모리 비용 증가
---
멀티스레드 환경에서 해시 테이블은 put/rehash 과정에서 Race Condition에 취약합니다. 성능 저하를 최소화하면서 해결하려면, 테이블을 여러 segment로 나누고 segment별로 락을 걸거나, Java ConcurrentHashMap처럼 버킷 단위로 CAS 연산을 활용해 lock-free 또는 low-lock 구조를 설계하는 방식이 효과적입니다.
  • CAS(Compare-And-Swap)

    • 멀티스레드 환경에서 락을 걸지 않아도 데이터를 안전하게 수정하기 위한 원자적 CPU 연산

    • CAS 동작 방식

      • CPU가 수행하는 기본 Operation은 다음 3가지 입력을 받음
      1. 메모리 주소(변경할 값이 있는 위치)
      2. 기대한 값(Expected Value)
      3. 새로 넣을 값(New Value)

    • 알고리즘 흐름

      if (메모리의 현재 값 == expected) {
    메모리 값을 newValue로 교체
    return true (성공)
} else {
    아무것도 하지 않고 실패 반환
    return false (실패)
}
      • 전체가 원자적(Atomic)으로 수행되므로 다른 스레드가 끼어들 수 없음

    • 예시

      • 값이 10인 변수 x
      • Thread A → “x가 10이면 11로 바꿔라”
      • Thread A 실행
        1. x의 실제 값 : 10
        2. expected : 10 → 일치
        3. 새로운 값으로 교체 : x = 11
        4. 성공 반환
      • Thread B 실행
        • B와 A는 거의 동시에 CAS를 실행하려고 시도
        1. x의 현재 값 : 11
        2. expected = 10 → 불일치
        3. 교체하지 않고 실패
      • 경쟁하지 않고도 데이터 무결성이 보장

    • 멀티 스레드에서 CAS가 중요한 이유

      1. Lock을 사용하지 않음
        • synchronized, mutex 같은 락은 Blocking됨
        • 스레드가 기다려야 하므로 성능 저하
      2. Non-blocking
        • 실패해도 그냥 “실패 반환”
        • 스레드가 sleep / wait 하지 않음
        • 재시도(Spin)만 하면 됨
      • 위 이유로 매우 빠름

    • 단점

      1. Busy Waiting (Spin) 오버헤드
        • 재시도 반복이 많아지면 CPU가 계속 반복해서 성능 저하
      2. ABA 문제
        • 값이 A → B → 다시 A가 되어도 CAS는 “변경되었다 돌아온 것”을 감지하지 못함
        • 해결 방법
          • AtomicStampedReference(버전 번호 함께 비교)
      3. CPU 지원
        • 현재 CPU는 CAS 명령어를 제공

    • 잘못하면 무한 루프 도는거 아닌가?

      • 이론적으로는 가능하지만, 실제로는 대부분 금방 성공

        • 극단적으로 계속 다른 스레드가 value를 바꾸고 있으면 starvation
        • starvation을 보완하기 위한 전략
          • backoff
            • 연속으로 실패하면 잠깐 sleep하거나 yield해서 경쟁 줄이기
          • 재시도 횟수 제한
            • 너무 많이 실패시 lock으로 fallback

      • value 자체가 안맞아서 forever false

        do {
    oldValue = value;          // 여기서 최신 상태 다시 읽음
    newValue = oldValue + 1;
} while (!CAS(value, oldValue, newValue));
        • expected 값을 매 루프에서 새로 읽음
        • 읽었을 때 기대한 값이었는데, CAS 하기 전 누군가 바꿔서 실패한 것

트리 / 이진 탐색 트리

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

    1. 트리
 - 노드와 간선으로 구성된 계층적 자료구조
 - 사이클이 없고, 모든 노드는 정확히 하나의 부모를 가짐(루트 제외)
 - 루트라는 출발점이 존재
 - 노드가 N개일 때 간선은 항상 N - 1개
2. 이진 트리
 - 모든 노드가 최대 2개의 자식만을 갖는 트리
3. 이진 탐색 트리(BST, Binary Search Tree)
 - 이진 트리의 종류
 - Left Subtree의 모든 값은 현재 노드보다 작다.
 - Right Subtree의 모든 값은 현재 노드보다 크다.

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

    1. 그래프
 - 노드와 간선의 집합
 - 방향 그래프와 무방향 그래프 모두 존재
 - 사이클 존재 가능
 - 루트 없음
2. 트리
 - 사이클 없음
 - 루트 존재
 - 노드는 항상 하나의 부모만을 가짐
 - 모든 노드는 연결됨

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

    항상 오름차순 정렬된 결과를 얻음

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

    탐색/삽입/삭제 : 평균 O(log N), 최악 O(N)

높이가 log2 N 정도인 균형 상태에서는 트리를 내려갈 때마다 검색 범위가 절반씩 감소
입력이 정렬된 상태로 들어오면 트리가 한쪽으로 기울어진 트리가 되기 때문에 O(N)

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

    1. 균형을 보장하지 않음
 - 특정 입력 패턴(정렬된 값 반복 삽입)에서 트리가 한쪽으로 편향됨
2. 트리의 균형 유지를 위한 추가 작업이 없음
3. 메모리 사용량이 큼(포인터 2개 필요)
4. 삭제 구현이 일반 트리보다 복잡

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

    1. 삽입
 - 루트부터 시작해서 삽입할 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동
 - NULL이 되면 삽입
2. 삭제
 - 삭제할 노드의 자식 수에 따라 3가지로 나뉨
 1. 자식이 없는 경우
  - 그냥 삭제
 2. 자식이 1개인 경우
  - 자식 노드를 부모와 연결하고 삭제
 3. 자식이 2개인 경우
  - 오른쪽 subtree의 최솟값 or 왼쪽 subtree의 최댓값으로 대체

계속 오름차순 데이터를 삽입하거나 계속 내림차순 데이터를 삽입하는 경우, 동일하거나 유사한 값을 삽입하는 경우 편향 발생

  7. 이진탐색트리와 동일한 로직을 사용하면, 삼진탐색트리도 정의할 수 있을까요? 안 된다면, 그 이유에 대해 설명해 주세요.

    불가능
BST가 가능한 이유는 루트 값 1개로 데이터 공간을 2개 공간으로 명확하게 나눌 수 있기 때문

삼진 탐색 트리를 사용하면 데이터 범위를 3개 구간으로 나누어야 하는데, 노드에 값이 하나만 있을 경우 구간 기준이 1개뿐이라 불가능

삼진탐색트리를 만들려면 노드당 key 개수를 늘려야 함

힙

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

    완전이진트리 기반의 우선순위 큐 자료구조
특성
 - Min-Heap : 부모 <= 자식
 - Max-Heap : 부모 >= 자식
특징
 - 전체가 정렬된 구조는 아님
 - 루트가 최소/최대 값임을 보장

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

    부모 인덱스를 i라 하면
left child = 2 * i
right child = 2 * i + 1

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

    1. 삽입
 - 마지막 위치에 값 추가
 - 부모와 비교하며 올라감
 - 시간 복잡도 : O(log N)
2. 삭제
 - 루트 값을 제거
 - 배열의 마지막 값을 루트로 가져옴
 - 자식 중 더 작은(또는 큰) 값과 비교하며 내려감
 - 시간 복잡도 : O(log N)

힙은 항상 완전이진트리 구조를 유지하기 때문에 새로운 노드는 항상 왼쪽 -> 오른쪽 -> 다음 레벨 순으로 채워짐
트리 높이는 항상 O(log N) 유지

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

    - 과정
 1. N개의 요소로 힙 구성 -> O(N)
 2. N번 연속으로 "루트 제거 -> heapify" -> N * O(log N)
 -> 전체 시간 복잡도 : O(N log N)
 
- Stable 하지 않음
 - 힙 정렬은 힙의 재배치 과정에서 동일한 값의 상대적 순서를 보존할 수 없음

균형 이진 탐색 트리 (BBST)

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

    BBST란 항상 높이를 O(log N)수준으로 유지하도록 균형을 잡는 이진 탐색 트리 계열
기본은 BST와 동일하지만 균형 조건을 추가해 탐색, 삽입, 삭제가 항상 O(log N)이 되도록 보장

1. AVL Tree
	- 각 노드마다 높이 정보를 저장하고 왼·오른쪽 서브트리 높이 차이가 최대 1이 되도록 유지
	- 매우 balanced인 트리 -> 탐색 빠름, 삽입/삭제시 회전 많음
2. Red-Black Tree
	- 각 노드에 색을 두어 균형 유지
	- 완벽한 균형은 아니지만 가장 긴 경로는 가장 짧은 경로의 길이에 최대 2배를 넘지 않음
	- 삽입/삭제가 AVL보다 단순, 회전 횟수 적음
3. 2-3 Tree, 2-3-4 Tree(Multi-way Search Tree)
	- 한 노드에 key를 2개 혹은 3개 가지고, 자식을 3개, 4개 가지는 다진 탐색 트리
	- 항상 완전 균형
	- 레드블랙 트리는 사실상 2-3-4 트리와 동치인 구조를 이진 트리로 표현한 것
4. Treap
	- BST + Heap의 합성
	- key 기준 ST, priority 기준 heap을 동시에 만족
	- 삽입 시 랜덤 priority -> 랜덤하게 균형 잡힌 트리 형성
5. Splay Tree
	- 접근할 때마다 그 노드를 루트 근처로 splay(회전)
	- 자주 쓰는 노드에 대한 접근을 빠르게 만들기 좋은 구조
	- 균형을 엄밀히 저장하지 않지만, 평균적으로 O(log N) 보장

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

    노드 색과 회전(Rotation), Recoloring을 이용해 트리 높이를 적당히 균형 있게 유지

1. 트리 전체에 색깔 규칙을 강하게 걸어 둠
2. 삽입/삭제 시 이 불변식이 깨지면
	1. 일부 노드의 색을 바꾸고(Recoloring)
	2. 경우에 따라 좌/우 회전(Rotate)을 수행해서
	3. 다시 규칙을 만족하도록 만듦

루트에서 리프까지 가는 어떤 경로도 다른 경로 길이의 2배를 넘지 않게 유지 -> 탐색/삽입/삭제가 O(log N) 보장

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

    1. 각 노드는 Red 또는 Black이다.
	- 모든 노드는 반드시 두 색 중 하나
2. 루트는 항상 Black이다.
	- 루트가 Black이 아니면 Recoloring 등으로 맞춤
3. Red 노드는 Red 자식을 가질 수 없음(No Red-Red)
	- 즉 Red 노드의 부모와 자식은 모두 Black -> 빨간 노드가 연속해서 두 개 이상 이어질 수 없음
4. 각 노드에서 그 노드의 모든 리프(NIL 노드)까지 가는 경로에는 항상 같은 개수의 Black 노드가 존재
	- 이를 Black Height라고 함
	- 어떤 경로든 Black 노드 수가 같기 때문에, 어느 한쪽으로 길게 치우친 경로가 생기기 어려움
5. 모든 리프(NIL 노드)는 Black으로 간주
---
이 성질이 균형을 보장하는 이유
1. Red 노드가 연속하면 안되니까 Black 노드들 사이에 낄 수 있는 Red 노드의 수가 제한됨
2. 모든 경로의 Black 노드 수가 같기 때문에
	- 어떤 경로가 Black 노드 기준으로 심하게 길어질 수 없음
	- Red 노드는 끼어들 수 있어도 최대 한 칸씩만 끼어드니 전체 길이 차이가 크게 벌어지지 않음

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

    1. AVL vs Red-Black : 회전 횟수 & 구현 난이도
	- AVL Tree 장점
		- 어마어마하게 균형이 잘 맞음
		- 탐색만 보면 Red-Black보다 약간 더 유리할 수 있음
	- AVL Tree 단점
		- 삽입/삭제 시 밸런스 인덱스 재계산 + 회전이 자주 발생
		- 코드 구현이 더 복잡, 삭제 로직이 특히 어려움
	- Red-Black Tree 장점
		- 약간 느슨한 균형이지만 삽입/삭제에서 회전 수가 적고 구현이 단순
		- 실사용에서 "탐색 + 삽입/삭제"가 같이 존재하는 경우가 많기 때문에 더 효율적
	- AVL의 조금 더 잘맞는 균형보다 Red-Black의 단순함 + 전체적인 평균 성능이 더 매력적
2. 2-3-4 vs Red-Black : 메모리 & 구현
	- 2-3-4 Tree는 multi-way search tree라서 한 노드에 여러 key와 child 포인터가 들어감
	- 메모리 레이아웃이 C/C++ 같은 언어에서 구현하기 다소 번거롭고, 포인터 관리도 복잡함
	- Red-Black Tree는 2-3-4 Tree와 거의 동치인 구조를 "이진트리 + 색 정보"로 구현한 것이라 2-3-4 Tree의 이론적 장점 + 상대적으로 낮은 구현 난이도

Red-Black Tree는
1. 탐색/삽입/삭제시 모두 O(log N)을 보장하고
2. AVL-Tree보다 삽입/삭제 회전 횟수가 적고
3. 2-3-4 Tree보다 구현하기 쉽고 메모리 레이아웃이 단순함

정렬 알고리즘

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

    데이터를 특정 기준에 따라 순서를 재배열하는 과정이며 크게 두 종류로 나뉨

1. Comparision Sort(비교 기반 정렬)
	- 요소들 간의 대소 비교를 통해 정렬
	- 하한선 : 최선의 알고리즘도 O(N log N)이하로는 불가능
	- 예
		- Quick Sort
		- Merge Sort
		- Heap Sort
2. Non-Comparision Sort(비교하지 않는 정렬)
	- 데이터를 분류하거나 자릿수 기반으로 처리
	- 비교 기반의 O(N log N) 한계를 넘어설 수 있음
	- 예
		- Radix Sort
		- Counting Sort
		- Bucket Sort
정렬 알고리즘은 시간 복잡도, 공간 복잡도, 안정성 기준으로 비교

  2. Quick Sort와 Merge Sort를 비교해 주세요.

    1. Quick Sort
	- 분할 정복
	- 평균 시간 : O(N log N)
	- 최악 시간 : O(N^2)
	- 공간 복잡도 : O(log N)
	- 안정성 : Unstable
2. Merge Sort
	- 분할 정복
	- 평균 시간 : O(N log N)
	- 최악 시간 : O(N log N) -> 항상 안정적
	- 공간 복잡도 : O(N) -> 추가 배열 필요
	- 안정성 : Stable

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

    피벗 선택이 잘못될 때 O(N^2) 발생
피벗을 항상 가장 왼쪽 요소로 선택하는 구현에서 이미 정렬된 배열, 역순 배열, 중복 많은 배열을 넣을 경우
개선 방법
	- Random Pivot 선택(Randomize Quick Sort)
	- Median of Three(첫 요소, 중간 요소, 끝 요소 중 가운데 값 선택)
	- IntroSort 사용
		- Quick Sort 사용 중 개귀 깊이가 일정 이상이면 Heap Sort로 전환

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

    동일한 키 값을 가진 요소들의 기존 상대적 순서를 유지하는 정렬
1. Stable Sort
	- Merge Sort
	- Insertion Sort
	- Bubble Sort
	- Counting Sort
	- Radix Sort
	- Timsort
2. Unstabble Sort
	- Quick Sort
	- Heap Sort
	- Selection Sort

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

    가능함. 이를 Bottom-Up Merge Sort(Interative Merge Sort)라고 함

방법
1. 구간 크기 1부터 시작
2. 인접한 두 구간을 Merge
3. 구간 크기 2, 4, 8, ... 늘려가며 반복
4. 더 이상 병합할 구간이 없으면 종료

주로 외부 정렬이나 메모리 제한 환경에서 사용
    • Bottom-up Merge Sort
      • 길이가 1짜리 정렬된 덩어리(run)부터 시작해서 길이 2, 4, 8, …으로 점점 키우며 merge
      • 재귀하지 않고 구간 크기를 1, 2, 4, … 키워가며 돌림
      • 동작 과정
        • [5, 2, 9, 1, 6, 3]
        1. 길이 1짜리 구간은 정렬되어 있다고 가정
          • [5], [2], [9], [1], [6], [3]
        2. 인접한 두 개씩 합쳐 길이 2짜리로 merge
          • [5, 2] → [2, 5]
          • [9, 1] → [1, 9]
          • [6, 3] → [3, 6]
        3. 다시 길이 4짜리로 merge
          • [2, 5] + [1, 9] → [1, 2, 5, 9]
          • [3, 6]은 혼자 남음
        4. 마지막으로 전체 merge
          • [1, 2, 5, 9] + [3, 6] → [1, 2, 3, 5, 6, 9]

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

    비교를 하지 않는 정렬로 숫자 또는 문자열의 자릿수를 기준으로 정렬

방법
1. 가장 낮은 자릿수 또는 높은 자릿수부터
2. Stable Sort를 사용하여 자릿수 별로 정렬을 반복

시간 복잡도
	- O(kN)
	- k는 자릿수 길이 -> 자릿수가 작다면 사실상 O(N)

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

    1. Bubble
	- 평균 : O(N^2)
	- 최악 : O(N^2)
	- 최선 : O(N)
2. Selection
	- 평균 : O(N^2)
	- 최악 : O(N^2)
	- 최선 : O(N^2)
3. Insertion
	- 평균 : O(N^2)
	- 최악 : O(N^2)
	- 최선 : O(N)

평균 속도 : Insertion > Selection > Bubbble
최선 속도 : Insertion이 가장 빠름

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

    거의 정렬된 배열에서는 Insertion Sort -> O(N), Bubble Sort -> O(N)에 가까움, Selection Sort -> O(N^2)

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

    1. Primitive 타입 배열
	- Dual-Pivot Quick Sort : O(N log N), Unstable
2. Object 타입 배열
	- Timsort : Merge Sort + Insertion Sort 기반 하이브리드 정렬, Stable Sort
    • Dual-Pivot Quick Sort

      • 피벗을 2개 사용해서 배열을 3개 구간으로 나누는 것

        [p1]  ...  < p1
       mid... p1 <= x <= p2
[p2]  ...  > p2
        • p1 < p2로 정해진 두 피벗 사용
        • 데이터를 3개 그룹으로 분리
          • left : p1보다 작은 값
          • middle : p1과 p2 사이의 값
          • right : p2보다 큰 값

      • 왜 더 빠른가?

        1. 분할 품질 향상 → 더 균등한 분할 가능
          • 한 번의 partition으로 3-way 분할
            • 더 고르게 나누기 쉬움
            • 재귀 깊이 감소
            • 평균 비교/교환 횟수 감소
        2. 실제 데이터 분포에서 더 효율적
          • JDK 팀에서 실험 결과 Quick Sort보다 10% ~ 30% 향상된 성능

      • 3-pivot, 4-pivot은 왜 없을까?

        • pivot을 늘리면 분할 수도 늘지만, 비용도 함께 증가
          • 비교 횟수 증가
          • CPU 분기 증가
            • branch misprediction 증가
            • pipeline flush 발생
            • 성능 급격히 떨어짐
        • Dual-Pivot이 성능에서 가장 좋음
    • Timsort(Tim Peters Sort)
      • 실제 데이터가 완전히 랜덤이 아닌 경우가 많다는 것을 이용해서 이미 어느 정도 정렬된 구간(run)을 최대한 활용하는 하이브리드 정렬 알고리즘
      • Insertion Sort + Merge Sort
      • Stable하고 실제 데이터에서 아주 빠름
      • 동작 과정
        • [1, 2, 3, 10, 9, 8, 20, 21, 22]
        1. 배열에서 이미 정렬돼 있는 구간(run)을 찾는다.
          • [1, 2, 3, 10] (오름차순 run)
          • [10, 9, 8] (내림차순 run → 뒤집어서 [8, 9, 10])
          • [20, 21, 22] (오름차순)
        2. minirun & Insertion Sort
          • 너무 작은 run은 비효율적이므로, 최소 길이(minirun)을 정함 → 보통 32 ~ 64
          • run의 길이가 minirun보다 짧으면 그 부분만 Insertion Sort로 정렬해서 작지만 완전히 정렬된 구간으로 만듦
        3. Run을 Merge
          • 막 합치지 않고 run의 길이 패턴(스택 규칙)을 가지고 어떤 run끼리 먼저 병합할지 결정하며 효율을 높임
      • 특성
        • 시간 복잡도 : 평균/최악 → O(N log N), 이미 거의 정렬된 데이터에서는 O(N)에 가깝게 동작
        • Stable
      • 왜 Quick Sort가 아닌 Insertion Sort를 사용하는걸까?
        1. 작은 구간에서는 Insertion Sort가 더 빠르기 때문
          • 비교 횟수가 적음
          • swap 비용이 적음
          • 단순 비교/이동으로 CPU branch prediction이 뛰어남
          • 메모리 접근이 연속적 → L1/L2 CPU 캐시 효율 ↑
          • 오버헤드(재귀 호출, pivot 선택 등)가 거의 없음
        2. 정렬된 run을 사용하기 때문에 Insertion Sort가 적합
        3. Stability 문제
        4. Quick Sort는 작은 구간에서 정렬 품질이 떨어짐

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

    외부 정렬(External Sorting) 사용
1. 데이터를 적당한 크기(예 : 1GB)로 나누어 부분 정렬
	- 각 chunk를 메모리 안에서 정렬
	- 결과를 디스크에 저장 : O(N log N)
2. 정렬된 chunk를 K-way Merge로 병합
	- 최소 힙을 사용해서 각각의 청크에서 최솟값을 가져옴 : O(N log K)
    • External Merge Sort 동작 과정
      1. Run 생성(Chunk 정렬)
        1. 디스크에서 데이터를 메모리에 들어갈 수 있을 만큼 읽어옴
        2. 메모리 안에서 일반적인 정렬 알고리즘으로 정렬
        3. 정렬된 데이터를 다시 디스크에 임시 파일(run)로 기록
      2. Multi-way Merge(K-Way Merge)
        • 여러 개의 run을 하나의 큰 정렬된 파일로 합치는 작업
        1. 각 run에 대해 입력 버퍼를 조금씩 메모리에 잡음(예 : 각 run당 1MB 씩)
        2. 각 버퍼의 맨 앞 원소들만 모아서 최소 힙을 만듦
        3. 힙에서 가장 작은 값을 꺼내서 결과 파일에 기록
        4. 그 값이 속해 있던 run의 버퍼에서 다음 값을 읽어와 힙에 다시 넣음
        5. 이를 모든 데이터가 소진될 때까지 반복
    • 시간 복잡도
      • Run 생성 단계 : N개를 메모리 안에서 정렬 → O(N log N)
      • K-way Merge 단계 : N개 데이터를 K개의 run에서 뽑아가며 mege → 각 원소마다 힙 연산 log K → O(N log K)
      • 전체적으로 O(N log N)
    • 추가 최적화 아이디어
      • Replacement Selection
        • Run을 만들 때 단순히 1GB씩 자르지 않고 힙을 사용해서 run 길이를 평균 2배 정도로 늘리는 기법
      • Multi-pass Merge
        • 한 번에 K개씩만 merge할 수 있다면 여러 레벨에 걸쳐서 (K-way Merge → 그 결과로 또 K-way Merge) 반복

그래프 최단 거리

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

    1. 가중치 X : BFS
2. 가중치 양수만 있을 경우 : 다익스트라
3. 음수 가중치 존재, 음수 사이클 X : 벨만-포드
4. 모든 정점 쌍 최단 거리 : 플로이드-워셜
5. 탐색 최적화 + 휴리스틱 : A*

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

    1. 루트 기준 depth 계산
2. 공통 최소 조상 구하기
3. 공통 최소 조상까지의 거리를 더함

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

    힙
	- 우선순위 선택 : O(log N)
	- 시간 복잡도 : O((V + E) log V)
배열 / 선형 탐색
	- 우선순위 선택 : O(V)
	- 시간 복잡도 : O(V^2 + E) ≒ O(V²)
Fibonacci Heap
	- 우선순위 선택 : O(1) amortized
	- 시간 복잡도 : O(E + V log V)

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

    완전 그래프보다 더 큰 밀도인 경우

다익스트라 : O(E log V) = O(N^3 log N)
벨만포드 : O(VE) = O(N^4)
플로이드-워셜 : O(N^3)

따라서 플로이드-워셜이 압도적으로 유리함

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

    A*
- 다익스트라 + 휴리스틱을 이용한 최단 경로 탐색 알고리즘
- 다익스트라는 모든 방향으로 넓게 퍼지는 탐색
	- 우선순위 큐 기준 : 시작점 s에서 x까지의 현재까지의 최단 거리 추정 값
	- 비용이 싼 곳부터 넓게 퍼지므로 목표 지점이 어디 있는지 모르는 것처럼 탐색
- A*는 목표를 알고 있는 다익스트라
	- 다익스트라에 추정값(휴리스틱, h(x))를 더해 탐색을 목표 쪽으로 유도
	- 우선 순위 큐 기준 : f(x) = g(x) + h(x)
		- g(x): 실제로 지금까지 온 비용(시작점 s ~ x)
		- h(x): x에서 목표까지의 추정 비용 (heuristic)
	- 예
		- 2D 격자 지도
			- g(x) : 시작점부터 x까지의 실제 이동 거리
			- h(x) : x에서 목표까지의 맨해튼 or 유클리드 거리
		- 단순히 "현재까지 비용이 최소인 노드"가 아니라
		- "현재까지 비용 + 앞으로 예상 비용"이 가장 작은 노드를 먼저 확장
	- A*가 진짜 최단 경로를 보장하려면 h(x)가
		1. Admissible : 실제 거리보다 절대 과대추정하면 안 됨
			- 항상 h(x) <= 실제 최소 거리여야 함
		2. Consistent(or Monotonic)
			- h(x) <= cost(x, y) + h(y)를 만족

A* vs 다익스트라
- 다익스트라
	- 성능 : 범용적이지만 느림
	- 특징 : 목표 정보를 사용하지 않음
- A*
	- 성능 : 훨씬 빠름
	- 특징 : 목표 방향으로 탐색을 집중

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

    1. 음수 간선이 있고, 음수 사이클 없음 : 벨만-포드
2. 음수 간선 & 모든 정점 쌍 최단 거리 탐색 : 플로이드-워셜
3. 음수 사이클 있음 : 벨만-포드로 감지 가능 but 최단 거리 정의 X

재귀

  1. 재귀 함수에 대해 설명해 주세요

    함수가 자기 자신을 호출하는 형태의 함수. 문제를 더 작은 동일한 형태의 하위 문제로 쪼갠 뒤, 가장 단순한 경우에서 값을 반환해 전체 문제를 해결하는 방식

1. Base Case(기저 사례)
	- 재귀를 더 이상 진행하지 않고 바로 결과를 반환하는 조건
2. Recursive Case(재귀 호출 부분)
	- 문제를 더 작은 하위 문제로 나누고 자기 자신을 호출
	
쓰임새
- 분할 정복
- 그래프 탐색(DFS)
- 백트래킹

  2. 재귀 함수의 동작 과정을 Call Stack을 활용해서 설명해 주세요.

    프로그램에서 함수를 호출할 때마다 스택 프레임이라는 메모리 블록 생성. 이 프레임에는 매개 변수, 지역 변수, 반환 주소 등 저장. 함수를 호출할수록 스택 위에 쌓이고 return시 맨 위 프레임 제거

  3. 언어의 스펙에 따라, 재귀 함수의 최적화를 진행해주는 경우가 있습니다. 어떤 경우에 재귀 함수의 최적화가 가능하며, 이를 어떻게 최적화 할 수 있을지 설명해 주세요.

    Tail Recursion : 함수의 마지막 연산이 자기 자신에 대한 호출인 재귀 형태
- return factTail(n - 1, acc * n);  // 마지막 연산이 재귀 호출 -> 꼬리 재귀 O
- return n * fact(n - 1);  // 재귀 호출 뒤에 '* n' 연산이 남아 있음 -> 꼬리 재귀 X

TCO
- Tail Call Optimization : 꼬리 재귀 최적화
- 꼬리 재귀 형태일 때, 일부 언어는 이 재귀를 반복문처럼 최적화
- 현재 함수의 할 일이 끝났으므로 새 stack frame을 만들지 말고, 현재 frame 사용
- 사실상 while문으로 돌아가는 것과 동일

- Java/C : 표준 스펙에서 TCO를 보장하지 않음
    • Memoization, Pruning과의 차이
      • Tail Recursion Optimization(TCO)
        • 컴파일러/언어 차원에서 최적화
        • 대상 : 형태가 꼬리 재귀인 함수
      • Memoization
        • 이미 계산한 결과를 캐시에 저장해 같은 입력에 대한 재계산을 피하는 방법
        • 시간 복잡도 최적화
      • Pruning
        • 탐색 중 더 가도 답이 안 나오는 분기 종료
        • 백트래킹, DFS에서 사용

MST / Union-Find

  1. MST가 무엇이고, 어떻게 구할 수 있을지 설명해 주세요.

    MST(Minimum Spanning Tree)란
1. 가중치 그래프에서 모든 정점을 연결하면서
2. 사용된 간선의 총 가중치가 최소가 되도록 만든 트리
- 조건
	1. 모든 정점이 연결되어 있어야 함
	2. 사이클이 없어야 함
	3. 정점의 개수가 N개면 간선은 항상 N-1개
	4. 여러 개의 MST가 존재할 수 있음(가중치가 동일한 경우)

알고리즘
1. Kruskal : O(E log E) = O(E log V)
	- 간선을 가중치 오름차순으로 정렬
	- 사이클이 생기지 않는 간선을 하나씩 선택
	- Union-Find를 통해 사이클 검사
	- Greedy 접근
2. Prim : O(E log V)
	- 하나의 정점에서 시작
	- 현재 구성된 트리와 가장 가까운 정점을 계속 선택
	- min-heap을 이용해 최단 간선 선택

  2. Kruskal 알고리즘에서 사용하는 Union-Find 자료구조에 대해 설명해 주세요.

    여러 원소들을 서로 겹치지 않는 집합으로 관리하는 자료구조
두 원소가 같은 집합에 속하는지 여부를 빠르게 판별하고 두 집합을 하나로 합칠 수 있음

연산
1. find(x)
	- x가 속한 집합의 대표를 찾음
	- 경로 압축을 이용하면 거의 O(1)
2. union(a, b)
	- a와 b가 속한 집합을 합침
	- union-by-rank/size를 적용해 트리를 편향되지 않게 유지
	- 시간 복잡도 거의 O(1)

Kruskal은 간선을 정렬된 순서로 선택하면서
find(u) == find(v)
	- 둘이 이미 같은 집합에 있으면 사이클 생기므로 skip
	- 다르면 union(u, v)로 같은 MST 집합에 포함

  3. Kruskal과 Prim 중 어떤 것이 빠를까요?

    Sparse Graph(E ≈ V) : Kruskal
Dense Graph(E ≈ V^2) : Prim(Binary Heap)
Dense + Adjacency Matrix 사용 : Prim(O(V^2))

Kruskal
- 간선을 정렬해야 해서 O(E log E)
- sparse graph에서는 E가 작으므로 정렬 비용이 작아 효율적

Prim
- heap 기반의 Prim은 O(E log V)
- dense graph에서는 E log V와 E log E 간 차이가 커짐
- adjacency matrix와 함께 쓰면 O(V^2)로 최적

  4. Kruskal과 Prim 알고리즘을 통해 얻어진 결과물은 무조건 트리인가요? 만약 그렇다면 증명해 주세요. 그렇지 않다면 반례를 설명해 주세요.

    그래프가 연결 그래프라면 Kruskal과 Prim이 만드는 결과물은 항상 MST이고, 항상 트리이다.

1. Prim 알고리즘이 트리가 되는 이유
	- 처음에 정점 하나에서 시작
	- 매 단계마다 트리에 연결된 간선 중 가장 가중치가 작은 간선 하나만 추가
	- 이 간선은 트리 내부 정점과 트리 외부 정점을 잇는 간선으로 사이클이 생길 수 없음
	- 정점을 하나씩 포함시키므로 최종 간선의 개수 = V - 1
	- 따라서 Prim 결과물은 항상 트리
2. Kruskal 알고리즘이 트리가 되는 이유
	- 간선을 가중치 순으로 하나씩 고려
	- 각 간선(u, v)를 선택할 때 find(u) == find(v)인 경우 선택하지 않음
	- Kruskal은 사이클이 생기지 않는 간선만 선택함
	- V개의 정점이 모두 연결될 때까지 반복
	- 선택되는 간선은 정확히 V-1개
	- 따라서 Kruskal 결과물은 항상 트리

- 그래프가 비연결 그래프인 경우 MST는 존재하지 않고 MSF(Minimum Spanning Forest)를 만들 수 있음

Thread-Safe 자료구조

  1. Thread Safe한 자료구조가 있을까요? 없다면, 어떻게 Thread Safe하게 구성할 수 있을까요?

    Java 예시
1. 레거시 동기화 컬렉션(Synchronized)
	- Vector
	- Hashtable
	- Stack(Vector 기반)
	- StringBuffer
	-> 메서드 전체에 synchronized가 걸려 있어서 멀티스레드에 안전하지만, 락 범위가 커서 성능은 좋지 않음
2. java.util.concurrent 패키지
	- ConcurrentHashMap
	- CopyOnWriteArrayList
	- ConcurrentLinkedQueue
	-> 더 정교한 동기화 전략(세그먼트 락, CAS, 락 분할 등)을 사용해 성능 개선
3. Wrapper 기반 동기화
	- Collections.synchronizedList
	- Collections.synchronizedMap
	-> 내부 컬렉션 자체는 thread-unsafe지만 wrapper로 synchronized를 씌워 thread-safe
	
Thread Safe하게 만드는 방법
1. Coarse-grained Lock(굵은 락)
	- 자료구조 전체에 Synchronized를 걸어 모든 연산 보호
	- 장점 : 구현 쉽고 직관적
	- 단점 : 락 경합이 심하므로 성능 낮음
2. Find-grained Lock(세분화된 락)
	- 노드/버킷/세그먼트 별로 락을 나누어 사용
	- 장점 : 병렬성은 높고, 락 경합 낮음
	- 단점 : 구현 복잡
3. CAS 기반 Lock-Free
	- AtomicInteger, AtomicReference 등에서 사용
	- 현재 값이 기대 값과 같으면 새 값으로 바꾼다는 연자적 원산 사용
	- 락을 잡지 않으므로 교착상태 없고 높은 병렬성
4. Immutable / Copy-On-Write
	- CopyOnWriteArrayList
	- 쓰기가 적고 읽기가 많은 경우 유리
	- 변경 시 전체 배열을 복사 -> 쓰기 비용 ↑, 읽기는 락 없이 가능
    • Atomic Operation
      • 쪼갤 수 없고, 중간 상태가 외부에 보이지 않는 연산
      • 하나의 스레드가 수행하는 동안 다른 어떤 스레드도 간섭할 수 없는 연산
        • 한 번에 한 스레드만 수행할 수 있고, 연산이 완전히 수행되거나 아얘 수행되지 않거나 둘 중 하나
      • Atomic ≠ Thread-Safe

        • Atomic한 연산은 오직 그 연산 하나만 원자적인 것

        • AtomicInteger.incrementAndGet()은 atomic

        • 하지만 두 개의 atomic 연산을 조합하면 atomic하지 않음

          if (atomicInt.get() < 10) {
    atomicInt.incrementAndGet();
}
          • 위 코드는 thread-safe하지 않음

        • 두 개의 atomic 연산 사이에 다른 스레드가 끼어들 수 있기 때문 → 여러 atomic 연산의 조합은 atomic하지 않음

  2. 배열의 길이를 알고 있다면, 조금 더 빠른 Thread Safe한 연산을 만들 수 있을까요?

    전체 길이를 알면 스레드 별 안전하게 분할 가능

1. 인덱스 범위를 스레드 별 분리(락 없음)
	- 길이가 1000인 배열과 4개의 스레드가 있다면
	- T1[0, 249], T2[250, 499], T3[500, 749], T4[750, 999]
	- 각 스레드는 자기 구간만 읽고 쓰므로 데이터 경쟁이 발생하지 않음 -> 락이 필요 없음
	- 가장 빠른 Thread-Safe 방법
2. Lock Striping / Segment Locking
	- 배열을 일정 길이의 세그먼트로 나누고, 세그먼트마다 별도 락
	- 길이가 1000인 배열, 세그먼트 크기 100
	- segment[0] = index 0 ~ 99, lock L0 ...
	- 각 스레드는 특정 인덱스를 접근할 때 해당 세그먼트의 락만 집으면 됨
	- 전체 배열에 대해 하나의 전역 락을 쓰는 것보다 병렬성이 좋음
	- 서로 다른 세그먼트를 접근하는 스레드끼리는 동시에 작업 가능
3. AtomicArray / LongAdder 스타일
	- 내부적으로는 배열 + CAS를 이용해 Thread-Safe하게 값을 변경

  3. 사용하고 있는 언어의 자료 구조는 Thread Safe한가요? 그렇지 않다면 Thread Safe한 Wrapped Data Structure를 제공하고 있나요?

    Java의 기본 자료구조들은 대부분 thread-unsafe

Java에서 사용하는 Thread-Safe Wrapped Data Structure -> 1번 참고

문자열 탐색 알고리즘

  1. 문자열을 저장하고 처리하는 주요 자료구조 및 알고리즘에 대해 설명해 주세요.

    1. 문자열을 저장하는 처리구조
	1. 문자 배열(char[])
	2. 불면 문자열 구조(String)
	3. 가변 문자열 구조(StringBuilder / StringBuffer)
	4. 트라이(Trie, Prefix Tree)
	5. 접미사 배열(Suffix Array)
	6. 접미사 트리 등
	
2. 문자열 검색 알고리즘
	1. Brute Force : 최악 O(NM)
	2. KMP
		- 패턴 P에 대해 Longest Proper Prefix 배열을 미리 만들고 실패시 뒤로 최대한 멀리 점프하는 방식
		- 시간 복잡도
			- LPS 구성 : O(M)
			- 검색 : O(N)
	3. Rabin-Karp
		- 문자열의 해시값을 이용해 비교 -> Rolling Hash
		- 장점
			- 여러 패턴 탐색에 매우 유리
			- 해시 재계산이 O(1)
		- 단점
			- 해시 충돌 가능
			- 충돌시 다시 문자열 비교 필요
		- 시간 복잡도
			- 평균 : O(N + M)
			- 최악 : O(NM)
	4. Boyer-Moore
		- 문자열 검색에서 실제로 가장 빠르게 동작하는 알고리즘 중 하나
		- 뒤에서 앞으로 비교
		- "bad character rule", "good suffix rule" 등을 통해 점프량을 크게 유지
		- 일반 텍스트에서 매우 효율적
		- 시간 복잡도
			- 평균 : O(N/M)
			- 최악 : O(NM)
    • Boyer-Moore 알고리즘
      • 핵심 알고리즘
        1. 오른쪽부터 비교
        2. 틀렸을 때 많이 건너뛰기 위해 미리 점프 테이블 생성
          • Bad Character Rule
          • Good Suffix Rule

이진 탐색

  1. 이진 탐색이 무엇인지 설명하고, 시간 복잡도를 증명해 보세요.

    정렬된 배열에서 탐색 구간을 절반씩 줄여가며 원하는 값을 찾는 알고리즘

한 번 비교할 때마다 탐색 구간의 길이가 절반으로 줄어듦
N / (2 ^ k) < 1 -> N < 2 ^ k -> k > log2 N
필요한 비교 횟수 k는 O(log N)
전체 시간 복잡도는 최악/평균/최선 모두 O(log N)

  2. Lower Bound, Upper Bound는 무엇이고, 이를 어떻게 구현할 수 있을까요?

    Lower Bound : 정렬된 배열에서 x 이상이 처음으로 나오는 인덱스
Upper Bound : 정렬된 배열에서 x 초과가 처음으로 나오는 인덱스

왜 사용할까?
- 어떤 값 x가 정렬된 배열에서 몇 번 등장하는지 구할 때
- 구간 [L, R] 안에 있는 값들 개수를 구할 때
- 첫 번째 이상 / 마지막 이하 / 구간 검색 등

  3. 이진 탐색의 논리를 적용하여 삼진 탐색을 만든다고 가정하면 시간 복잡도는 어떻게 변화할까요?(실제 존재하는 삼진탐색 알고리즘은 무시)

    이진 탐색처럼 동작하지만 매번 탐색 구간을 3등분 해서 중앙 2개의 지점과 비교하며 다음 탐색 구간을 줄여 나간다고 가정
- 이진 탐색 : 매 스텝마다 N -> N / 2
- 삼진 탐색 : 매 스텝마다 N -> N / 3
따라서 시간 복잡도는 O(log3 N) -> 상수배 차이이므로 O(log N)

이론적으로 조금 더 적은 스텝을 요구할 수 있지만, 각 단계에서 비교를 더 많이 해야 하고 구현도 복잡하므로, 이진 탐색이 보통 더 빠르고 실용적이라고 할 수 있음

  4. 기존 이진 탐색 로직에서 부등호의 범위가 바뀐다면(eg. ≤에서 <, <에서 ≤) 결과가 달라질까요?

    1. 이진 탐색은 Invariant(불변 조건)이 핵심
	- 부등호를 대충 바꾸면 invariant가 깨져서
		1. 값이 있는데 못찾거나
		2. 무한 루프를 돌 수 있음
2. 설계를 바꾸면 부등호에 따라 의미가 달라지는 이진 탐색 구현 가능
	- lower_bound, upper_bound 등

구현 전체의 invariant, 목적에 맞게 부등호를 설계하면 결과는 알고리즘이 의도한 대로 달라질 수 있음

그리디 알고리즘 vs 동적 계획법

  1. 그리디 알고리즘과 동적 계획법을 비교해 주세요.

    1. 그리디
	- 매 단계에서 당장 최선의 선택을 함
	- 이 선택이 전체 문제에서 전역 최적해를 보장해야 함 -> "지금 최선 = 전체 최선"이 되어야 함
	- 조건
		1. 탐욕 선택 속성 : 현재 최적 선택이 전체 최적해로 이어져야 함
		2. 최적 부분 구조 : 문제의 최적해가 부분 문제의 최적해로 구성됨
2. 동적 계획법
	- 전체 문제를 작은 부분 문제로 나누고, 그 결과를 저장하여 재사용하는 방식
	- 조건
		1. 중복 부분 문제 : 같은 부분 문제가 여러 번 반복
		2. 최적 부분 구조

  2. 그렇다면, 어떤 경우에 각각의 기법을 사용할 수 있을까요?

    1. 그리디
	- 탐욕 선택 속성이 있어야 함 -> 현재 국소 선택이 전체 최적해로 이어짐
	- 최적 부분 구조가 있어야 함
	- 거스름돈 문제, 활동 선택, MST, 다익스트라 등
2. 동적 계획법
	- 최적 부분 구조
	- 중복 부분 문제
	- 피보나치 수열, LCS, LIS, Knapsack 등

  3. 그렇다면, 동적 계획법으로 풀 수 있는 모든 문제는 재귀로 변환하여 풀 수 있나요?

    DP는 항상 재귀적 정의를 기반으로 하지만, 모든 DP 문제를 실제로 재귀로 구현할 수 있는 것은 아님

1. DP 식은 재귀적으로 정의할 수 있지만 스택 깊이 문제로 불가능 할 수 있음
2. 일부 DP는 재귀 구조 없이도 풀 수 있음
	- Bottom-up, DAG 등