자료구조 기초

Data Structure

• 자료구조란?
  자료를 효율적으로 저장하고 관리하기 위한 방법과 구조를 의미.

• 자료구조의 필요성
  • 데이터를 효율적으로 저장하고 검색하여 성능을 향상시킬 수 있음.
  • 메모리 사용을 최적화하고, 프로그램의 실행 속도를 개선할 수 있음.
  • 복잡한 문제를 단순화하고, 코드의 가독성과 유지보수성을 높일 수 있음.
• 효율성
  • 비용(Cost)
    어떤 문제를 해결하는 soultion이 요구하는 시간 & 공간
  • 효율적인 자료구조와 알고리즘을 선택해야만 주어진 cost 내에서 문제를 풀 수 있음
• 자료구조 선택 방법
  1. 문제 분석을 통해 필요한 기초 연산 정의
  2. 각 연산의 자원 제약을 정량화
  3. 요구사항을 제일 만족하는 자료구조 선택
     • 각 구조마다 장점과 비용이 존재
     • 모든 상황에서 다른 구조보다 우월한 자료구조는 거의 없음
     • 자료구조가 요구하는 자원
     • 시간 & 공간
     • 프로그래밍 복잡도 - 선택 전 고려할 사항
     • 데이터는 처음에 모두 삽입되는가? 아니면 중간 삽입도 있는가?
     • 삭제 가능한가?
     • 순차 처리인가, 무작위 접근이 필요한가?

Abstract Data Types

• 추상 자료형(Abstract Data Type, ADT)
  • 데이터와 데이터에 수행할 수 있는 연산을 정의한 수학적 모델.
    • 연산은 입력과 출력으로 정의
  • Encapsulation:
    구현 세부 사항은 숨기고, 인터페이스만 제공.
• 자료구조는 ADT의 물리적 구현
• 구현과 사용을 분리해 복잡성 추상화
• 논리적 형태
  • 데이터를 ADT를 이용해 정의 (e.g. 정수형, 실수형)
• 물리적 형태
  • 정의된 자료 구조 안에서 구현된 데이터 (e.g. 4바이트 정수)

Problem, Algorithm, Program

• 문제
  • 해결해야 할 과제나 질문. 입력과 출력이 명확히 정의되어야함.
    • 예 : 검색 문서 찾기(입력: 쿼리, 출력: 문서)
  • 잘못된 문제 정의 :
    • 입력 - 언어 데이터
    • 출력 - 감성 분석 결과
    • 문제 - 딥러닝 알고리즘 구현하기
      ❌ -> 구현 방법을 문제 단계에 선언
      언어 데이터를 긍정, 부정으로 구분하는 분류기 구현 ✅
• 알고리즘
  문제를 해결하기 위한 단계적 절차나 방법.
  • 특징 :
    • 정확성
    • 명확한 단계
    • 유한성(명확한 종료 조건 명시)
  • 예 : 이진 탐색 알고리즘
• 프로그램
  알고리즘을 특정 프로그래밍 언어로 구현한 것.
  • 예 : Python으로 구현된 이진 탐색 코드

---

해당 포스트는 서울대학교 컴퓨터공학부 강유 교수님의 자료구조 25-1학기 강의를 정리한 내용입니다.