[자료구조] 자료구조와 알고리즘

자료구조

• 다양한 자료를 효율적인 규칙에 따라 정리하고 보관하기 위해 조직화한 자료 형태
• 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조
• 자료(Data)는 저장 공간(Memory)과 연산(읽기, 쓰기, 삽입, 삭제, 탐색 등)으로 구성됨
  • 자료구조는 지원되는 연산에 따라 다양하게 존재

자료구조 분류

• 단순 자료구조와 복합 자료구조
  • 단순 자료구조: 숫자나 문자 등 기본적인 데이터 타입
  • 복합 자료구조: 여러 자료를 한꺼번에 보관하는 자료 형태
• 선형 자료구조 (Linear Data Structure)
  • 자료를 일렬로 나열할 수 있는 구조 (자료들 사이에 순서 존재)
  • 예: 스택(Stack), 큐(Queue), 덱(Deque), 리스트(List)
  • 집합(Set)은 원소 간 순서가 없어 선형 자료구조가 아님
• 비선형 자료구조 (Non-linear Data Structure)
  • 한 줄로 나열하기 어려운 복잡한 관계의 자료들을 표현
  • 예: 트리(Tree), 그래프(Graph), 집합(Set)

자료구조 구현 방법

• 배열 구조 (Array-based Structure)
  • 모든 자료가 인접한 메모리 공간에 저장됨
  • 특징: 접근 용이, 크기 고정 (확장 어려움)
• 연결된 구조 (Linked Structure)
  • 흩어져 있는 자료들을 연결하여 하나로 관리
  • 특징: 유연한 삽입/삭제, 관리 복잡성 증가

알고리즘

알고리즘 정의

• 주어진 문제를 해결하기 위한 단계적인 절차
• 특정한 일을 수행하는 명령어들의 집합
  • 프로그래밍 언어와는 독립적인 문제 해결 절차 자체를 의미
• 프로그램 = 자료구조 + 알고리즘

알고리즘의 조건

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

알고리즘 기술 방법

• 자연어 (Natural Language)
  • 장점: 읽기 쉽고 표현이 자유로움
  • 단점: 단어 정의가 부정확하면 의미 전달이 모호해질 수 있음
• 흐름도 (Flowchart)
  • 장점: 절차를 가장 정확하게 표현 가능, 직관적
  • 단점: 알고리즘이 복잡해지면 그림이 매우 복잡해짐
• 유사 코드 (Pseudo Code)
  • 장점: 자연어보다 체계적, 프로그래밍 언어보다 덜 엄격, 불필요한 표현 생략 가능, 핵심 내용 집중 용이
  • 이 강의 자료에서 주로 사용
  • 대입 연산자: ←, 비교 연산자: =
• 특정 프로그래밍 언어 (Specific Programming Language)
  • 장점: 바로 실행 가능
  • 단점: 언어 문법에 따른 불필요한 표현 포함, 핵심 이해 방해 가능성

추상 자료형 (ADT)

추상화 및 ADT 개념

• 추상화 (Abstraction): 시스템의 복잡한 내용 대신 필수적이고 중요한 특징만 골라 단순화하는 작업
• 추상 자료형 (ADT - Abstract Data Type):
  • 데이터 타입(데이터의 집합과 연산의 집합)을 추상적(수학적)으로 정의한 것
  • 자료형이 다루는 데이터(What)와 필요한 연산(What)을 간략히 정의

ADT의 특징

• 명세와 구현의 분리: 데이터나 연산을 어떻게(How) 구현할지는 정의하지 않음
  • 핵심 아이디어: 구현 세부 사항은 숨기고, 인터페이스(Interface)만 외부에 공개
• 정보 은닉: 응용 프로그램 개발자는 공개된 인터페이스만 사용하며 내부 구현 방식은 알 필요 없음
• 모듈성: 구현 방법이 변경되어도 인터페이스가 동일하면 기존 코드 수정 없이 사용 가능

ADT 예시

• 가방 (Bag) ADT:
  • 데이터: 중복된 항목을 허용하는 자료들의 저장소 (순서 없음)
  • 연산: Bag()(빈 가방 생성), insert(e)(항목 e 추가), remove(e)(항목 e 삭제), contains(e)(항목 e 존재 여부 확인), count()(항목 수 반환) 등
• 다항식 (Polynomial) ADT:
  • 데이터: 지수-계수의 순서쌍 집합 (예: $a_n x^n + ... + a_1 x + a_0$)
  • 연산:
    • 상태 검사: degree()(차수 반환), coefficient(i)(i차 항 계수 반환)
    • 다항식 간 연산: add(B), sub(B), multiply(B) (다른 다항식 B와의 합/차/곱)
    • 계산: evaluate(x) (주어진 x값에 대한 다항식 계산 결과 반환)

알고리즘 성능 분석

성능 분석의 필요성

• 효율적인 알고리즘: 실행 시간이 짧고, 컴퓨터 자원(특히 메모리)을 적게 사용하는 알고리즘
• *일반적으로 실행 시간을 더 중요하게 고려

실행 시간 측정 방법

• 가장 단순하고 확실한 방법: 알고리즘을 실제 구현하여 실행 시간 측정
  • C언어 clock() 함수 등 사용 가능 (실행시간 = 종료 시각 - 시작 시각)
• 문제점:
  • 반드시 구현 필요 (복잡한 알고리즘은 구현 어려움)
  • 동일한 하드웨어/소프트웨어 환경에서 측정해야 함
  • 동일한 프로그래밍 언어 및 컴파일/인터프리트 방식 사용 필요
  • 측정에 사용된 특정 데이터에 대해서만 유효

복잡도 분석 (Complexity Analysis)

• 구현 없이 알고리즘의 효율성을 평가하는 방법
• 알고리즘이 수행하는 연산의 횟수를 대략적으로 측정하여 비교
  • 연산 횟수가 많을수록 더 복잡한(덜 효율적인) 알고리즘
• 시간 복잡도 (Time Complexity): 수행 시간 분석 (연산 횟수 측정)
• 공간 복잡도 (Space Complexity): 수행 시 필요한 메모리 공간 분석

시간 복잡도 함수 (T(n))

• 알고리즘 수행에 필요한 연산의 수를 입력 크기 n에 대한 함수로 표현
• 기본 연산(산술, 대입, 비교, 이동 등)의 개수를 계산
• 알고리즘 실행 시간은 T(n)에 비례한다고 가정

점근적 표기법 (Asymptotic Notation)

• 입력 크기 n이 충분히 클 때, 복잡도 함수 T(n)의 증가 추세를 나타내는 표기법
• 핵심 아이디어:
  • 정확한 연산 횟수보다 "얼마나 빨리 증가하는가?"(증가 속도)에 초점
  • 최고차항만으로 복잡도를 표현 (다른 항과 계수는 무시)
    • 예: $T(n) = n^2 + n + 1$ 에서 $n$이 충분히 크면 $n^2$ 항이 절대적인 영향을 미침
• 종류:
  • 빅오 (Big-O) 표기법 (O(g(n))):
    • $T(n)$의 증가 속도가 $g(n)$의 증가 속도와 같거나 낮은 모든 함수들의 집합
    • 알고리즘 수행 시간의 **상한(Upper Bound)**을 나타냄 (아무리 늦어도 이 정도)
    • *일반적으로 최소 차수의 상한을 사용 (예: $T(n)=2n+1$ 이면 $O(n^2)$도 맞지만 $O(n)$으로 표기)
  • 빅오메가 (Big-Omega) 표기법 (Ω(g(n))):
    • $T(n)$의 증가 속도가 $g(n)$의 증가 속도와 같거나 높은 모든 함수들의 집합
    • 알고리즘 수행 시간의 **하한(Lower Bound)**을 나타냄 (아무리 빨라도 이 정도)
  • 빅세타 (Big-Theta) 표기법 (Θ(g(n))):
    • $T(n)$의 증가 속도가 $g(n)$의 증가 속도와 같은 함수들의 집합
    • 알고리즘 수행 시간의 상한과 하한이 동일함을 의미 (Tight Bound)

• 주요 빅오 표기법 종류 (성능 좋은 순):
  • $O(1)$: 상수 시간 (입력 크기와 무관)
  • $O(\log n)$: 로그 시간
  • $O(n)$: 선형 시간
  • $O(n \log n)$: 로그 선형 시간
  • $O(n^2)$: 이차 시간
  • $O(n^3)$: 삼차 시간
  • $O(2^n)$: 지수 시간
  • $O(n!)$: 팩토리얼 시간

실행 시간 분석 (최선, 평균, 최악의 경우)

• 알고리즘 실행 시간은 입력 데이터 구성에 따라 달라질 수 있음
• 최선의 경우 (Best Case): 수행 시간이 가장 빠른 경우 (알고리즘 분석에서 큰 의미는 없음)
• 평균적인 경우 (Average Case): 모든 가능한 입력에 대한 평균 수행 시간 (계산이 매우 어려움)
• 최악의 경우 (Worst Case): 수행 시간이 가장 오래 걸리는 경우
  • 가장 중요하게 사용됨 (어떤 입력에도 보장되는 성능의 상한선 제공)
  • 예: 비행기 관제, 게임, 로보틱스 등 실시간 응답이 중요한 분야에서 필수적

레퍼런스

“이 글은 『쉽게 배우는 C 자료구조』(최영규 및 천인국, 2024)의 내용을 토대로 재구성된 자료입니다.”​