CS 학습 - 9월 2주차

자료구조와 알고리즘

알고리즘 성능 분석

알고리즘의 효율성을 객관적으로 평가하는 방법을 배우는 단계이다. 모든 자료구조와 알고리즘을 이해하는 데 기반이 된다.

• 시간 복잡도 (Time Complexity): 알고리즘이 문제를 해결하는 데 걸리는 시간을 입력 데이터의 크기와 연관 지어 표기하는 방법이다. (예: O(1), O(log n), O(n), O(n log n), O(n²))
• 공간 복잡도 (Space Complexity): 알고리즘이 실행되는 동안 사용하는 메모리의 양을 표기하는 방법이다.

시간 복잡도(Time Complexity)

알고리즘을 실행하는데 필요한 연산횟수를 측정하는 것이다. 실제 실행시간이 아니고 빅오 표기법으로 사용하는데, 이는 데이터 크기(n)가 무한히 커졌을 때의 최악의 경우(worst-case)를 기준으로 성능을 표기하는 방법이다.

• O(1) - 상수 시간 (Constant Time)
  • 설명: 입력 데이터의 크기와 상관없이 항상 일정한 수의 연산만 수행한다. 가장 빠른 속도이다.
  • 예시: 배열의 특정 인덱스(arr[i])에 접근하는 것.
• O(log n) - 로그 시간 (Logarithmic Time)
  • 설명: 연산을 한 번 수행할 때마다 탐색해야 할 데이터의 양이 절반씩 줄어든다.
  • 예시: 정렬된 배열에서 이진 탐색(Binary Search)을 하는 경우.
• O(n) - 선형 시간 (Linear Time)
  • 설명: 입력 데이터의 크기(n)에 비례하여 연산 횟수가 증가한다.
  • 예시: 배열의 모든 요소를 한 번씩 순회하는 for 반복문.
• O(n log n) - 로그 선형 시간 (Log-Linear Time)
  • 설명: 데이터의 크기(n)에 log n을 곱한 만큼 연산 횟수가 증가한다. 대부분의 효율적인 정렬 알고리즘이 여기에 속한다.
  • 예시: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort).
• O(n²) - 이차 시간 (Quadratic Time)
  • 설명: 입력 데이터의 크기(n)의 제곱에 비례하여 연산 횟수가 증가한다. 데이터가 커지면 성능이 급격히 저하됩니다.
  • 예시: 이중 for 반복문을 사용하여 배열의 모든 요소 쌍을 비교하는 경우 (예: 버블 정렬).

공간 복잡도(Space Complexity)

알고리즘 실행될 때, 추가적으로 사용되는 메모리 양을 측정한다. 입력데이터 자체를 저장하는 공간은 계산에서 제외하며, 문제 해결을 위해 별도로 사용하는 메모리 공간을 기준으로 한다.

• 주요 공간 복잡도 예시
  • O(1) - 상수 공간(Constant Space)
    • 설명 : 입력 데이터의 크기와 상관없이 일정한 양의 메모리 사용
  • O(n) - 선형 공간(Linear Space)
    • 설명 : 입력 데이터 크기(n)에 비례하여 추가적인 메모리 공간이 필요하다.

시간과 공간의 관계(Trade-off)

알고리즘을 설계할 때 시간과 공간은 종종 상충관계를 가진다.

• 시간을 단축하려면 더 많은 메모리를 사용해야할 수 있다.
• 메모리를 아끼려면 더 많은 연산을 수행해야 할 수도 있다.

핵심은 그렇기에 문제의 요구사항이나 시스템 제약을 고려하여 시간 복잡도와 공간복잡도 사이의 균형을 맞추는게 중요하다.

복잡도 계산 방법

복잡도 계산은 코드의 연산 횟수를 n에 대한 함수로 표현한 뒤, 빅오 표기법 규칙에 따라 단순화하는 과정이다.

3단계 계산법

1. 기본 연산 단위 찾기: 알고리즘의 핵심이 되는 반복적인 연산을 찾는다. (주로 반복문 내부)
2. 연산 횟수를 ‘n’으로 표현하기: 입력 크기 n에 따라 기본 연산이 몇 번 수행되는지 식으로 표현한다. (예: n² + n)
3. 빅오 표기법으로 단순화하기: 아래 두 규칙을 적용한다.
   • 규칙 1: 최고차항만 남긴다. n² + n에서 가장 영향력이 큰 n²만 남긴다.
   • 규칙 2: 상수 계수를 제거한다. 2n에서 계수 2를 제거하여 n으로 표기한다.

파이썬 코드로 보는 계산 예시

예시 1: O(n)

def linear_example(arr, n):
    total = 0
    for i in range(n):
        total += arr[i] # 1. 기본 연산
    return total

• 연산 횟수: 기본 연산이 n번 반복되므로, 연산 횟수는 n이다.
• 빅오 표기: O(n)이다.

예시 2: O(n²)

def quadratic_example(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1 # 1. 기본 연산
    return count

• 연산 횟수: 기본 연산이 n * n번 반복되므로, 연산 횟수는 n²이다.
• 빅오 표기: O(n²)이다.

예시 3: O(log n)

def logarithmic_example(n):
    i = 1
    while i < n:
        # ... O(1) 연산 ...
        i = i * 2 # 1. 핵심 연산 (탐색 범위가 절반씩 줄어드는 효과)

• 연산 횟수: i가 2의 거듭제곱으로 증가하므로, 반복 횟수는 log₂n에 비례한다.
• 빅오 표기: O(log n)이다.

---

심화 및 실용적 고려사항

• 시간과 공간의 상충 관계(Trade-off): 시간을 단축하기 위해 더 많은 메모리를 사용하거나(예: 메모이제이션), 메모리를 아끼기 위해 더 많은 연산을 수행할 수 있다.
• 캐시 효율성 (Cache Locality): 이론적인 복잡도가 같더라도, 데이터가 메모리에 연속적으로 배치된 배열이 비연속적인 연결 리스트보다 CPU 캐시 효율이 높아 실제 속도는 더 빠르다.
• 재귀의 공간 복잡도: 재귀 함수는 호출될 때마다 콜 스택(Call Stack)에 메모리를 사용하므로, 재귀의 최대 깊이가 공간 복잡도가 된다. (예: n 깊이의 재귀는 O(n) 공간을 사용)

주요 자료구조

데이터를 목적에 맞게 효율적으로 저장하고 관리하는 방법에 대한 학습 단계이다.

• 선형 자료구조
  • 배열(Array)
  • 연결 리스트(Linked List)
  • 스택(Stack)
  • 큐(Queue)
• 비 선형 자료구조
  • 해시 테이블(Hash Table)
  • 트리(Tree) : 이진트리, 이진 탐색 트리, AVL 트리, 레드블랙 트리 등
  • 힙(Heap) : 우선순위 큐
  • 그래프(Graph)

선형 자료구조

배열과 연결 리스트

가장 기본적이면서 면접에서 비교 질문으로 자주 나오는 자료구조이다.

구분	배열(Array)	연결리스트(Linked List)
핵심 개념	데이터가 메모리 상에 연속적으로 저장된다.	각 데이터(노드)가 다음 데이터의 주소를 가지는 형태로 연결된다.
탐색(접근)	인덱스를 통한 O(1) 시간의 빠른 임의 접근이 가능하다.	처음부터 순차적으로 탐색해야 하므로 O(n) 시간이 소요된다.
삽입/삭제	중간에 데이터를 추가/삭제 시, 뒤따르는 모든 데이터를 이동시켜야 하므로 O(n) 시간이 걸린다.	포인터(주소) 연결만 변경하면 되므로 O(1) 시간의 빠른 삽입/삭제가 가능하다. (단, 해당 위치를 탐색하는 시간은 별도)
메모리	크기가 고정되어 있고, 연속된 메모리 공간을 할당받는다.	크기가 가변적이며, 필요할 때마다 메모리를 할당하여 비연속적인 공간을 사용한다.

스택과 큐

데이터의 입출력 순서를 제어하는 특징을 가진 자료구조이다.

• 스택
  • 개념: 후입선출(LIFO, Last-In First-Out) 구조이다. 가장 마지막에 넣은 데이터가 가장 먼저 나온다.
  • 주요 연산 : push(데이터 추가), pop(데이터 제거)
  • 활용 예시 : 함수 호출 스택, DFS(깊이 우선 탐색), 괄호 검사, 뒤로 가기 기능
  • Python 구현 : 파이썬의 기본 리스트(list)와 append(), pop() 메서드를 사용하면 스택을 쉽게 구현할 수 있다.

    # 스택 예시 코드
    stack = []
    stack.append(1) # push
    stack.append(2)
    stack.append(3)
    
    print(stack.pop()) # 3 출력
    print(stack.pop()) # 2 출력
    

• 큐(Queue)
  • 개념 : 선입선출(FIFO, First-In First-Out) 구조이다. 가장 먼저 넣은 데이터가 가장 먼저 나온다.
  • 주요 연산 : enqueue(데이터 추가), dequeue(데이터 제거)
  • 활용 예시 : 너비 우선 탐색(BFS), 프린터 작업 큐, 메시지 큐
  • Python 구현 : 리스트의 pop(0)은 O(n)의 비효율을 야기하므로, 양방향 입출력이 O(1)인 collections.deque를 사용하는 것이 표준이다.

    from collections import deque
    
    # 큐 예시 코드
    queue = deque()
    queue.append(1) # enqueue
    queue.append(2)
    queue.append(3)
    
    print(queue.popleft()) # 1 출력 (dequeue)
    print(queue.popleft()) # 2 출력
    

비선형 자료구조

데이터가 계층적 또는 네트워크 형태로 저장되는 구조이다.

• 해시테이블
  • 개념: 키(Key)와 값(Value)을 한 쌍으로 저장하는 자료구조이다. 내부적으로 해시 함수를 사용하여 키를 배열의 인덱스로 변환하여 데이터를 저장하므로, 매우 빠른 데이터 탐색이 가능하다.
  • 시간 복잡도: 평균적으로 삽입, 삭제, 탐색 모두 O(1)이다.
  • 해시 충돌 (Hash Collision): 서로 다른 키가 해시 함수를 통해 같은 인덱스로 변환되는 상황이다. 이 경우 성능 저하가 발생하며, 최악의 경우 O(n)까지 시간이 걸릴 수 있다.
  • 충돌 해결 방안: 체이닝(Chaining, 해당 인덱스에 연결 리스트를 사용)과 개방 주소법(Open Addressing, 다른 빈 공간을 찾아 저장)이 대표적이다.
  • Python 구현: 파이썬의 딕셔너리(dict)가 해시 테이블로 구현되어 있다.

    # 해시 테이블 예시 코드 (Dictionary)
    hash_table = {}
    hash_table['name'] = 'jarvis'
    hash_table['age'] = 10
    
    print(hash_table['name']) # 'jarvis' 출력 (O(1)에 가까운 속도)
    

• 트리 계층적인 관계를 표현하는 데 사용되는 자료구조이다.
  • 이진 탐색 트리 (Binary Search Tree, BST)
    • 특징: 부모 노드를 기준으로 왼쪽 서브 트리에는 부모보다 작은 값, 오른쪽 서브 트리에는 부모보다 큰 값이 저장된다.
    • 성능: 평균적으로 탐색, 삽입, 삭제에 O(log n)의 시간이 걸리지만, 트리가 한쪽으로 치우쳐진 최악의 경우 O(n)이 될 수 있다.
• 자가 균형 이진 탐색 트리 (Self-Balancing BST)
  • 개념: 데이터의 삽입 및 삭제 시 자동으로 트리의 균형을 맞추어 최악의 경우에도 O(log n)의 성능을 보장하는 트리이다.
  • 종류: AVL 트리, 레드-블랙 트리 등이 있으며, 레드-블랙 트리는 데이터베이스 인덱싱 등에서 널리 사용된다.
• 힙
  • 개념: 최댓값이나 최솟값을 빠르게 찾아내기 위해 고안된 완전 이진 트리 기반의 자료구조이다. 부모 노드는 항상 자식 노드보다 크거나(최대 힙) 작아야(최소 힙) 한다.
  • 시간 복잡도: 데이터 삽입 및 삭제 시 O(log n)이다. 최댓값/최솟값 확인은 O(1)이다.
  • 활용 예시: 우선순위 큐(Priority Queue)를 구현하는 데 주로 사용된다.
  • Python 구현: heapq 모듈은 최소 힙을 제공한다.

    import heapq
    
    # 최소 힙 예시 코드
    min_heap = []
    heapq.heappush(min_heap, 4)
    heapq.heappush(min_heap, 1)
    heapq.heappush(min_heap, 7)
    
    print(heapq.heappop(min_heap)) # 가장 작은 값인 1 출력
    print(heapq.heappop(min_heap)) # 다음으로 작은 값인 4 출력
    

• 그래프 정점(Vertex)과 그 정점을 연결하는 간선(Edge)으로 이루어진 자료구조이다.
• 그래프 표현 방식
  • 인접 행렬: 2차원 배열을 사용하여 정점 간 연결 관계를 표현한다. 구현이 간단하지만 O(V²)의 공간이 필요하다(V: 정점 수).
  • 인접 리스트: 각 정점에 연결된 정점들을 리스트로 표현한다. O(V+E)의 공간이 필요하여 효율적이다(E: 간선 수).
• 대표적인 탐색 알고리즘
  • 너비 우선 탐색 (BFS): 큐를 사용하여 가까운 정점부터 탐색한다. 최단 경로 찾기에 사용된다.
  • 깊이 우선 탐색 (DFS): 스택(또는 재귀)을 사용하여 한 방향으로 끝까지 탐색한다. 모든 경로 탐색에 사용된다.

핵심 알고리즘

알고리즘은 문제 해결 능력을 직접적으로 보여주는 지표이다. 면접에서는 특정 알고리즘의 구현 능력뿐만 아니라, 문제 상황에 가장 적합한 알고리즘과 설계 기법을 선택하고 그 이유를 설명하는 능력이 중요하다.

• 주요 알고리즘 유형
  • 정렬(Sorting) : 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등
  • 탐색(Searching) : 이진 탐색, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 등
• 알고리즘 설계 기법(패러다임)
  • 분할 정복(Devide and Conquer) : 큰 문제를 작은 단위로 나누어 해결하는 기법 (예: 병합 정렬, 퀵 정렬)
  • 탐욕법(Greedy Algorithm) : 매 순간 최선의 선택을 하여 최종 해답을 찾는 기법
  • 동적 프로그래밍(Dynamic Programming) : 작은 문제의 해를 저장하고 재활용하여 큰 문제를 해결하는 기법
  • 백트래킹(Backtracking) : 해를 찾는 도중 막히면 이전으로 돌아가 다른 경로를 탐색하는 기법

주요 알고리즘 유형

정렬 (Sorting)

데이터를 특정 순서에 따라 나열하는 알고리즘이다. 각 정렬 방식의 시간 복잡도와 공간 복잡도, 그리고 안정성(stable) 여부를 비교하여 이해하는 것이 핵심이다.

• O(n²) 정렬 알고리즘: 선택, 삽입, 버블 정렬
  • 개념: 구현이 비교적 간단하지만, 데이터의 크기가 커질수록 성능이 급격히 저하된다.
  • 삽입 정렬 (Insertion Sort): 정렬된 부분 배열에 새로운 원소를 적절한 위치에 삽입하는 방식이다. 이미 대부분 정렬된 데이터에 대해서는 매우 효율적이다.

  # 삽입 정렬 예시 코드
  def insertion_sort(arr):
      for i in range(1, len(arr)):
          key = arr[i]
          j = i - 1
          while j >= 0 and key < arr[j]:
              arr[j + 1] = arr[j]
              j -= 1
          arr[j + 1] = key
      return arr
  

• O(n log n) 정렬 알고리즘: 병합, 퀵, 힙 정렬
  • 개념: 분할 정복 등의 기법을 사용하여 효율성을 높인 알고리즘이다. 일반적인 상황에서 주로 사용된다.
  • 퀵 정렬 (Quick Sort): 하나의 피벗(pivot)을 기준으로 작은 값과 큰 값을 나누어 정렬을 반복하는 방식이다. 평균적으로 매우 빠르지만, 피벗 선택에 따라 최악의 경우 O(n²)이 될 수 있다.

  # 퀵 정렬 예시 코드
  def quick_sort(arr):
      if len(arr) <= 1:
          return arr
      pivot = arr[len(arr) // 2]
      less = [x for x in arr if x < pivot]
      equal = [x for x in arr if x == pivot]
      greater = [x for x in arr if x > pivot]
      return quick_sort(less) + equal + quick_sort(greater)
  

탐색 (Searching)

데이터 집합에서 원하는 값을 찾아내는 알고리즘이다.

• 이진 탐색 (Binary Search)
  • 개념: 정렬된 데이터에서만 사용 가능한 탐색 기법이다. 탐색 범위를 계속해서 절반으로 줄여나가며 O(log n)의 시간 복잡도를 가진다.
  • 동작: 중앙값(mid)과 찾고자 하는 값을 비교하여, 작으면 왼쪽, 크면 오른쪽 부분 배열을 대상으로 탐색을 반복한다.

  # 이진 탐색 예시 코드 (재귀)
  def binary_search(arr, target, start, end):
      if start > end:
          return None
      mid = (start + end) // 2
      if arr[mid] == target:
          return mid
      elif arr[mid] > target:
          return binary_search(arr, target, start, mid - 1)
      else:
          return binary_search(arr, target, mid + 1, end)
  

• 그래프 탐색: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
  • BFS (Breadth-First Search): 큐(Queue)를 사용하여 시작 정점과 가까운 정점부터 차례대로 탐색한다. 최단 경로를 찾는 문제에 주로 활용된다.
  • DFS (Depth-First Search): 스택(Stack)이나 재귀 함수를 사용하여 한 방향으로 최대한 깊게 들어간 후, 더 이상 갈 곳이 없으면 이전 정점으로 돌아와 다른 방향을 탐색한다. 모든 경로를 탐색하는 문제에 적합하다.

---

알고리즘 설계 기법 (패러다임)

문제 해결을 위한 접근법이자 사고의 틀이다.

분할 정복 (Divide and Conquer)

• 개념: 해결하기 어려운 큰 문제를 해결 가능한 작은 문제들로 나눈 뒤(Divide), 각 작은 문제를 해결하고(Conquer), 그 결과를 합쳐(Combine) 원래 문제의 답을 구하는 전략이다.
• 대표 예시: 퀵 정렬, 병합 정렬

탐욕법 (Greedy Algorithm)

• 개념: 각 단계에서 그 순간에 가장 최적이라고 생각되는 선택을 하는 방식이다. 이렇게 만들어진 지역적인 최적해의 연속이 전역적인 최적해로 이어진다고 가정한다.
• 특징: 항상 최적의 해를 보장하지는 않으므로, 탐욕법을 적용할 수 있는 문제인지 정당성을 분석하는 과정이 필수적이다.
• 대표 예시: 최소 신장 트리를 찾는 크루스칼/프림 알고리즘, 거스름돈 문제

동적 프로그래밍 (Dynamic Programming, DP)

• 개념: 큰 문제를 작은 하위 문제들로 나누어 푸는 점은 분할 정복과 같지만, 하위 문제들의 해가 중복되는 경우 그 결과를 메모이제이션(Memoization)하여 재활용함으로써 계산 횟수를 줄이는 기법이다.
• 적용 조건: 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)라는 두 가지 속성을 만족하는 문제에 적용할 수 있다.
• 구현 방식: 하향식(Top-down, 재귀 + 메모이제이션), 상향식(Bottom-up, 반복문 + 테이블)

• 대표 예시: 피보나치 수열, 최장 공통 부분 수열(LCS)

  # 동적 프로그래밍 예시 (피보나치 수열 - 메모이제이션)
  memo = {0: 0, 1: 1} # 계산 결과를 저장할 딕셔너리
  
  def fib_dp(n):
      if n in memo:
          return memo[n]
      memo[n] = fib_dp(n-1) + fib_dp(n-2)
      return memo[n]
  

백트래킹 (Backtracking)

• 개념: 모든 가능한 경우의 수를 탐색하는 완전 탐색 기법을 기반으로 하되, 해가 될 가능성이 없는 경로는 더 이상 탐색하지 않고 이전 단계로 되돌아가(backtrack) 다른 경로를 탐색하는 전략이다.
• 특징: 불필요한 탐색을 줄여(가지치기, Pruning) 탐색의 효율을 높인다. DFS와 구현 방식이 유사하다.
• 대표 예시: N-Queens 문제, 미로 찾기, 스도쿠 풀이