01_Data Structures & Algorithms

1. 추상 자료형

1.1. 자료형

• 자료형(Data Type)
  • 데이터의 종류와 저장 방법을 정의한 것
  • cf. C 언어의 기본 자료형: int, float, double, char 등

1.2. 추상 자료형

• 추상 자료형(ADT; Abstract Data Type)

  • 데이터와 그 데이터에 수행할 수 있는 연산을 추상적으로 정의한 것
  • 구현 방법(How)은 숨기고 무엇(What)을 하는지만 명시함 (기능 중심)

• 구조

  • 사용자에게는 인터페이스(공개된 연산)만 제공하고,
  • 내부 데이터나 구현은 감춤(정보 은닉)

• 예시 (다항식 ADT)

  • 데이터: 지수-계수의 쌍
  • 연산: 차수 구하기, 계수 반환, 다항식 덧셈/뺄셈/곱셈, 값 계산 등

2. 자료구조

• 자료구조(Data Structure)

  • 컴퓨터에서 자료를 효율적으로 정리하고 조직화하는 구조

• 생활 속 예시

  • 리스트(List): 배달할 선물 목록
  • 스택(Stack): 접시 쌓기 (나중에 넣은 것이 먼저 나옴)
  • 큐(Queue): 매표소 줄 서기 (먼저 온 사람이 먼저 나감)
  • 트리(Tree): 회사 조직도
  • 그래프(Graph): 지하철 노선도

2.1. 데이터 간 관계에 따른 분류

• 선형 자료구조(Linear Data Structure)

  • 데이터가 일렬로 나열된 구조 (자료들 사이 순서)
  • 예: 스택, 큐, 덱, 리스트 등

• 비선형 자료구조(Non-linear Data Structure)

  • 데이터가 계층적이거나 복잡한 관계(1:N, N:N)를 가지는 구조
  • 예: 트리, 그래프, 집합 등

2.2. 저장 방식에 따른 분류

구분	배열 구조	연결된 구조
요소 접근	$O(1)$	$O(n)$
크기 변경	어려움	쉬움
삽입/삭제	$O(n)$	$O(1)$

• 배열 구조(Array-based Structure)

  • 연속된 메모리 공간에 데이터를 저장하는 자료구조
  • 장점: 접근 속도가 빠름($O(1)$), 메모리 효율(추가 포인터 없음)
  • 단점: 삽입/삭제가 느림($O(n)$), 크기 변경이 어려움

• (원형) 단순/이중 연결된 구조(Linked Structure)

  • 데이터를 저장하는 노드들이 포인터(링크)를 통해 연결된 자료구조
  • 장점: 삽입/삭제가 빠름($O(1)$), 크기 제한 없음
  • 단점: 접근 속도가 느림($O(n)$), 메모리 낭비(추가 포인터 있음)

3. 알고리즘

• 1. 알고리즘

4. 알고리즘의 복잡도 분석 예시

• 2. 알고리즘의 복잡도 분석

4.1. 1부터 n까지의 합

# pseudo-code
calc_sum1(n)
    sum = 0
    for i = 1 to n:
        sum += i
    return sum
 
calc_sum2(n)
    sum = n * (n + 1) / 2
    return sum

복잡도 함수는 어떤 연산을 기준 연산으로 선택하는지에 따라 달라질 수 있다.

여기서는 반복 방식의 sum += i를 기준 연산으로 사용한다.

1. 반복 방식

   • sum += i가 n번 실행된다.
   • 복잡도 함수: $T(n)=n$
   • 시간 복잡도: $\Theta (n)$

2. 합 공식

   • 입력 크기와 관계없이 일정한 수의 산술 연산을 수행한다.
   • 시간 복잡도: $\Theta (1)$

대입, 덧셈, 곱셈, 나눗셈, 반환 등을 각각 하나의 연산으로 계산하면 정확한 $T(n)$은 달라질 수 있다. 따라서 정확한 연산 횟수를 제시할 때는 연산을 세는 기준을 먼저 명시해야 한다.

4.2. 순차 탐색 알고리즘

int sequential_search(int A[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (A[i] == key)
            return i;  // 탐색 성공 시 인덱스 반환
    }
 
    return -1;  // 탐색 실패 시 -1 반환
}

복잡도 분석 기준

• 입력의 크기 $n$

  • 배열 A의 원소 개수

• 기준 연산

  • 비교 연산 A[i] == key

입력 구성에 따른 처리 시간

• 최선의 경우(best case) 첫 번째 원소가 key인 경우이다. 한 번의 비교만으로 탐색이 완료된다.

$$T_{\text{best}}(n)=1=\Theta (1)$$

• 평균의 경우(average case) 평균 수행 시간을 계산하려면 입력에 대한 확률분포를 정의해야 한다.

다음 조건을 가정한다.

• 탐색은 항상 성공한다.
• key가 배열의 각 위치에 존재할 확률은 동일하다.

이때 평균 비교 횟수는 다음과 같다.

$$\begin{array}{rl}{T}_{\text{avg}}(n)& =\frac{1+2+\cdots +n}{n}\\ & =\frac{n(n+1)/2}{n}\\ & =\frac{n+1}{2}\\ & =\Theta (n)\end{array}$$

탐색이 실패할 확률을 $q$라고 하면 평균 비교 횟수는 다음과 같이 나타낼 수 있다.

$$T_{\text{avg}}(n)=(1-q)\frac{n+1}{2}+qn$$

• 최악의 경우(worst case) key가 배열에 없거나 마지막 원소에 있는 경우이다. 총 n번의 비교가 필요하다.

$$T_{\text{worst}}(n)=n=\Theta (n)$$

4.3. 중복 요소 검사 알고리즘

int has_duplicate_elem(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (A[i] == A[j])
                return 1;  // 중복 요소가 있으면 TRUE 반환
        }
    }
 
    return 0;  // 중복 요소가 없으면 FALSE 반환
}

복잡도 분석 기준

• 입력의 크기

  • 배열 A의 원소 개수 n

• 기준 연산

  • 비교 연산 A[i] == A[j]

입력 구성에 따른 처리 시간

• 최선의 경우(best case) $n\ge 2$이고 A[0]과 A[1]이 같은 경우이다. 첫 번째 비교에서 중복을 발견한다.

$$T_{\text{best}}(n)=1=\Theta (1)$$

• 최악의 경우(worst case) 중복된 원소가 없거나 마지막 비교에서 처음으로 중복이 발견되는 경우이다. 모든 원소 쌍을 비교해야 한다.

$$\begin{array}{rl}{T}_{\text{worst}}(n)& =(n-1)+(n-2)+\cdots +1\\ & =\frac{n(n-1)}{2}\\ & =\Theta (n^2)\end{array}$$

따라서 중복 요소 검사 알고리즘의 시간 복잡도는 최선의 경우 $\Theta (1)$, 최악의 경우 $\Theta (n^2)$이다.