1. 다음 재귀식의 시간 복잡도를 Mater Theroem을 이용해 분석하시오

    1. T(n) = 2T(n/2) + n

      → a=2, b=2, k=1이므로 θ(N * log N)

    2. T(n) = 3T(n/2) + n^2

      → a=3, b=2, k=2 이므로 θ(N^2)

  2. 정렬된 배열에서 Binary Search의 수행 시간 복잡도를 수식으로 유도하시오.

    → 매 Step 마다 탐색 범위가 절반으로 줄어든다 N → N/2 → N/4 → … → 1

    → 이 과정을 k번 반복해서 1이 된다면, 2^k = N이고, k = log_2 N 이다.

    → O(log N)

  3. AVL Tree에서 발생 가능한 불균형 유형 4가지와 각각의 회전 방법을 서술하시오.

    → LL (left-left) : Right Rotation

    → RR (right-right) : Left Rotation

    → LR (left-right) : ①Left Rotation ②Right Rotation

    → RL (right-left) : ①Right Rotation ②Left Rotation

    → AVL Tree는 삽입/삭제 후 BF를 점검하여 |BF| > 1이되면 위와 같은 회전을 통해 Balance를 잡는다.

  4. Dijkstra 알고리즘과 Bellman-Ford 알고리즘의 차이점을 설명하고, 각각의 시간복잡도를 기술하시오.

    → 다익스트라는 음수 가중치가 불가능하다

    → 다익스트라는 Greedy 기반이고, Bellman-Ford는 DP 기반이다.

    → 다익스트라는 priority queue 기반 (or 2차원 배열?)으로 진행되고 Bellman-Ford는 모든 edge를 최대 V-1번 확인하는 구조

    → 다익스트라의 시간 복잡도는 O((V + E)logV), 벨만포드는 O(V x E)

  5. Matrix Chain Multiplication 문제에 대한 점화식을 유도하고, DP 적용 이유를 설명하시오

    → m[i][j] = min_i≤k≤j-1 (m[i, k] + m[k + 1, j] + pi_1p_kp_j) (i < j 일때, i=j면 그냥 0)

    → Optimal Substructure 구조일 때 Overlapping Subproblem을 간단하게 해결할 수 있기 때문

    → MCX의 경우 O(n^3)

  6. 두 문자열의 Longest Common Subsequence(LCS)를 찾기 위한 동적 계획법 점화식을 제시하고, 역추적(Back-tracking) 방식도 설명하시오

    → (i나 j가 0일 때) L[i][j] = 0

    → (xi = yi 일 때) L[i][j] = L[i-1][j-1] + 1

    → (나머지) L[i][j] = max( L[i-1][j], L[i][j-1] )

    역추적은 알아서 잘 할게

  7. Greedy Algorithm과 Dynamic Programming의 차이점을 기술하시오

    → Greedy는 현재 상태에서 최선을 다할 뿐이고, Memorization 없어서 Back-tracking 안되고, 최적 해를 보장하지 않음

  8. Tabu Search, Genetic Algorithm, Simulated Annealing의 탐색 전략과 지역 최적해 회피 방식에 대해 비교 설명하시오

    → Tabu는 이웃 기반 탐색하고 일부 금지 list 메모리 갖고 탐색해나가며, 금지 리스트를 통해 지역 최적해를 피한다

    → GA의 경우 해 집단의 진화 기반으로 탐색해나가며, 돌연변이, crossover 등을 통해 다양성을 유지하며 최적해를 피한다.

    → SA의 경우 단일 해 기반 확률 탐색인데, 확률적으로 나쁜 해를 수용하며(uphill probability) 지역 해를 피한다.

  9. 가장 느리게 증가하는 순서대로 정렬하시오. - O(N), O(logN), O(NlogN), O(2^N), O(N^2), O(N!)

    → O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

  10. Quick Sort 알고리즘에서 pivot 선택이 성능에 미치는 영향을 설명하시오. 최악의 시간 복잡도 상황도 함께 제시하시오

    → 피벗이 항상 최소/최대값으로 선정될 경우 분할이 비대칭하게 이뤄지며 재귀 depth가 N까지 늘어날 수 있다 ⇒ O(N^2)

    → 일반적인 경우 O(N log N)으로 잡힌다

  11. Floyd-Warshall 알고리즘에서 사용되는 점화식을 유도하고, 시간 복잡도를 분석하시오.

    → dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]), O(V^3)