01 Data Structure & Algorithm

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. 알고리즘

• 알고리즘(Algorithm)
  • 주어진 문제를 해결하기 위한 단계적인 절차
  • (프로그래밍 언어와 무관)

3.1. 특성

1. 입력: 0개 이상의 입력이 존재해야 함
2. 출력: 1개 이상의 출력이 생성되어야 함
3. 명확성: 각 명령어의 의미가 모호하지 않아야 함
4. 유한성: 한정된 단계 후에는 반드시 종료되어야 함
5. 유효성: 실행 가능한 연산이어야 함

3.2. 표현 방법

• 알고리즘 표현 방법이 필요한 이유

  • 명확한 의사소통
  • 문제 해결 과정을 체계화

• 자연어(Natural Language)

  • 읽기 쉽지만 의미가 모호해질 수 있음

• 흐름도(Flowchart)

  • 알고리즘의 흐름을 도형과 화살표로 시각적으로 표현
  • 직관적이지만 복잡한 알고리즘 표현에 한계

• 유사 코드(Pseudo-code)

  • 프로그래밍 언어와 유사하지만 문법에 얽매이지 않고 핵심만 기술

• 프로그래밍 언어

  • 바로 실행 가능하지만 구현 세부 사항 때문에 알고리즘 핵심 이해를 방해할 수 있음

4. 알고리즘의 성능 분석

입력 자료의 개수	프로그램 A: $n^2$	프로그램 B: $2^n$
n=6	36초	64초
n=100	10000초	$2^{100}$초 = $4\times 10^{22}$년

• 효율적인 알고리즘
  • 실행 시간이 짧고(시간 효율성),
  • 컴퓨터 자원(메모리)을 적게 쓰는(공간 효율성) 것

4.1. 성능 분석 방법

1. 실행 시간 측정

   • 실행시간 = 종료 시각 - 현재 시각
     • clock() 함수 이용
   • 단점
     • 반드시 구현해야 함
     • 하드웨어/환경에 따라 달라짐
     • 성능 평가를 한 데이터에 대해서만 유효

2. 복잡도 분석(Complexity Analysis)

   • 연산 횟수를 입력 크기 $n$에 대한 함수로 표현

5. 복잡도 분석

• 알고리즘의 복잡도 분석(complexity analysis)
  • 처리시간을 직접 측정하는 대신에, 알고리즘의 연산 횟수를 대략적으로 계산

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

• e.g. 1부터 n까지의 합
  • 반복: 복잡도 함수 $T(n)=2n+1$
  • 합 공식: 복잡도 함수 $T(n)=4$

5.1. 점근적 분석

• 점근적 분석(asymptotic analysis)
• 점근적 표기법(asymptotic notation)
  • 복잡도 함수를 최고차항만 계수 없이 표기하는 방법
    • e.g. $n^2+2n\to n^2$
    • e.g. $65536n+2000000\to n$
  • 연산이 얼마나 빨리 증가하는가? (증가 속도만을 표현)

(1) big-o

• 빅오(Big-O, $O(n)$)
  • $O(g(n))$: 증가 속도가 $g(n)$과 같거나 낮은 모든 복잡도 함수
  • 최악의 경우(최대 얼마나 느린가) → 상한(upper bound)

(2) big-theta

• 빅세타($\theta (n)$)
  • $\theta (g(n))$: 증가 속도가 $g(n)$과 같은 모든 복잡도 함수
  • 정확한 성장 속도 → 상한인 동시에 하한

(3) big-omega

• 빅오메가($\Omega (n)$)
  • $\Omega (g(n))$: 증가 속도가 $g(n)$과 같거나 높은 모든 복잡도 함수
  • 최선의 경우(최소 얼마나 빠른가) → 하한(lower bound)

5.2. 입력별 분석

• 입력별 분석(instance-specific analysis)
• 입력의 구성에 따른 처리시간 변화
  • 같은 알고리즘도 입력의 집합에 따라 다른 실행 시간을 보일 수 있다.

(1) Best Case

• Best Case(최선의 경우)
  • 입력에 대한 알고리즘의 수행 시간이 가장 빠른 경우
  • 알고리즘 분석에서는 큰 의미가 없음 (참고용)

(2) Average Case

• Average Case(평균의 경우)
  • 입력에 대한 알고리즘의 수행 시간이 평균적인 경우
  • 계산하기가 상당히 어려움 (현실적인 판단)

(3) Worst Case

• Worst Case(최악의 경우)
  • 입력에 대한 알고리즘의 수행 시간이 가장 느린 경우
  • 알고리즘 평가의 척도로 주로 사용됨

5.3. 복잡도 분석의 예

(1) 순차 탐색 알고리즘

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 반환
}

• 복잡도 함수 $T(n)$

  • 입력의 크기 $n$
    • array의 크기 n
  • 가장 많이 수행되는 기준 연산
    • 비교 연산 A[i] == key

• 입력의 구성에 따른 처리시간 변화

  • best case
    • 첫 번째 element가 key인 경우, 한번 만에 탐색이 완료된다.
    • $T_{best}(n)=1$
  • average case
    • 무엇이 “평균”인가에 대한 정의가 명확하지 않기 때문에 계산하기 어렵다.
    • e.g. array의 모든 숫자가 한 번씩 key로 사용되는 경우
      • $T_{avg}(n)=\frac{1+2+\cdots +n}{n}=\frac{n(n+1)/2}{n}=\frac{n+1}{2}$
  • worst case
    • key가 array에 없거나 맨 뒤에 있는 경우, n번 비교해야 한다.
    • $T_{worst}(n)=n$

(2) 중복 요소 검사 알고리즘

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 반환
}

• 복잡도 함수 $T(n)$

  • 입력의 크기: array의 크기 n
  • 기준 연산: 비교 연산 A[i] == A[j]

• 입력의 구성에 따른 처리시간 변화

  • best case: A[0]와 A[1]이 중복된 경우 → $O(1)$
  • worst case: 중복된 element가 없는 경우 → $O(n^2)$

6. Overview

이 강의 자료는 자료구조의 기초부터 심화까지 다음 순서로 구성되어 있다.

1. 자료구조와 알고리즘: 기초 개념, ADT, 성능 분석
2. 배열과 구조체: 배열, 행렬, 구조체, 희소 행렬, 다항식
3. 스택(Stack): 배열/구조체 스택, 괄호 검사, 계산기, 시스템 스택
4. 큐(Queue): 원형 큐, 덱(Deque), 피보나치, 미로 탐색(BFS/DFS)
5. 포인터와 연결된 구조: 동적 할당, 연결 리스트 기초
6. 리스트(List): 단순 연결 리스트, 이중 연결 리스트
7. 트리(Tree): 이진 트리, 순회, 이진 탐색 트리, 힙(Heap)
8. 그래프(Graph): 그래프 표현, 탐색, 신장 트리(MST), 최단 경로
9. 정렬(Sorting): 선택, 삽입, 버블, 병합, 퀵, 기수 정렬
10. 탐색(Search): 순차, 이진, 해싱, 트리 이용 탐색