자료구조 - 자료구조, 데이터 구조

1.자료구조(Data Structure)

• 문제 해결이 쉽도록, 손쉬운 접근, 변경, 처리가 가능하게, 데이터를 조직화, 저장, 표현하는 방법
  • 구조화된 데이터에 특정한 연산들을 용이하게 할 수 있는 구조
• 알고리즘 적용시, 효과적으로 처리 가능하도록 만들어진 특화된 데이터 체제/형태
  • ex) 배열, 링크드 리스트, 스택, 큐, 트리, 그래프 등
• 자료 및 그 처리를 합계 고려하는 데이터 형식
  • 즉, 자료와 그 작동을 합계 고려하면서
    • 이를 컴퓨터에 효과적으로 표현, 저장, 처리하는 기술
  • 특히, 이 둘을 잘 감싸는(캡슐화) 것을, 추상자료형이라고 한다.

2.자료구조의 목적/이유

• (추상화) 현실 세계에 존재하는 개념, 구조의 표현
  • 약속된 자료구조를 쓰면 좀 더 높은 단계의 프로그래밍이 가능
• (효율성) 효율적으로 데이터를 사용하기 위함
  • 통상, 좋은 자료구조는 연산의 횟수를 작아지게 할 수 있지만,
    • 모든 목적에 적합한 단일한 자료구조는 없으며, 응용에 따라 달라진다.
  • 또한, 사칙연산 이외에도,
    • 읽기, 삽입, 삭제, 비교, 교환, 검색 등의 용이성, 효율성도 고려 필요
• 즉, 문제 마다 적절한 자료구조를 사용함으로써,
  • 사용 편의성, 메모리 효율성, 코드 성능, 버그 감소 등 측면에서 유리하다.

3.자료구조의 종류

• 단순 구조 (통상, 자료구조로써 구분 포함시키지 않음)
  • 문자형, 문자열형, 숫자형, 논리형 등
• 자료 간의 연결 형태/모양에 따른 구분
  • 선형 자료구조 (linear, 전후 1:1 연결 형태)
    • 기본 선형 자료구조 : 리스트, 연결 리스트, 배열, 레코드 등
      • 특히 배열, 리스트 이 둘로부터, 대부분의 다른 자료구조들을 구현 가능
    • 제한 선형 자료구조 : 스택, 큐, 데크(스택과 큐가 혼합된 형태) 등
      • 자료의 입출력이 정해진 위치에서 만 가능
  • 비선형 자료구조(nonlinear, 전후 다대다 연결 형태)
    • 트리, 그래프 등
• 자료 간에 연속, 연결 구조에 따른 구분
  • 배열에 기반한 연속 방식 구조(continuation) : 리스트 등
  • 포인터 기반의 연결 방식 구조(link) : 연결 리스트 등
• 기타 자료구조 구분
  • 입출력 순서를 중심으로 성립되는 자료구조 : 스택, 큐 등
  • 자료들 간에 입출력 순서가 중요하지 않은 자료구조 : 집합, 딕셔너리/사전 등
  • 키 값의 연산에 의해 직접 접근이 가능한 자료구조 : 해시 테이블
  • 파일 구조에 따른 구분 : 순차 파일, 색인 파일, 직접 파일

4.자료구조의 선택 (고려 사항)

• 데이터의 양
• 데이터 사용 횟수 및 방법
• 요구되는 기억장치의 양
• 데이터 수정에 필요한 시간
• 알고리즘 복잡도 등

5.자료구조의 관점 (저장, 처리)

• 데이터의 저장/접근 관점
  • 데이터를 컴퓨터 메모리에 저장/접근할 때,
  • 데이터의 순서 및 위치관계 등이 명확하게 정해져야 올바른 처리 가능 하다.
• 데이터 및 연산을 다루는 관점
  • 자료형(Data Type) : 데이터 중심으로 만 고려
    • 자료(변수)가 갖는 값의 종류를 표현
    • 이때, 연산은 그 자료형에 맞도록, 별도/부가적/부차적으로 수행되는 관점이다.
  • 추상 자료형(Abstract Data Type) : 데이터와 연산을 함께 고려
    • "자료" 및 "연산"을 모두 하나로 묶어 하나의 단위로 표현
    • 자료 저장 및 처리보다는 문제 해결 지향적인 자료형이다.
• 예) 자료구조별 대표적인 연산들
  • 스택 : push(), pop(), createStack() 등
  • 큐 : inqueue(), dequeue(), createQueue() 등

6.자료구조의 표현 (구현)

• 사전 정의형 (프로그래밍 언어에서 기본 내장 제공)
  • C언어 (배열, 구조체 등)
  • 파이썬 (리스트, 튜플, 집합 등)
• 사용자 정의형 (프로그래머가 응요에 따라 직접 구현)
  • 다루는 데이터들에 대해,
    • 단순히 적절한 자료형을 선택하는 것 이상으로,
  • 종합적으로 고려하면서,
    • 어떤 연산들이 필요하고,
    • 데이터를 효율적으로 저장하는 방법은 어떻고,
    • 유효한 연산들은 무엇인지 등
  • 자료구조 및 알고리즘 등을 설계 구현해야 한다.

 

 

참고 : ktword.co.kr