자료구조

프로그램 혹은 알고리즘이 컴퓨터상에서 효율적으로 동작 할 수 있도록 자료를 저장하는 방법 잘설계된 자료구조와 그에 따른 프로그램 혹은 알고리즘 수행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 프로그램이 효율적으로 수행 될 수 있도록 해줌

자료구조의 개념

- 추상자료형(Abstract Data Type) : 자료들과 그 자료들에 대한 연산을 명기한 모델. 구체적인 구현과 무관함 (ex: 정수, 전화번호부, 스택, 큐 등)
- 자료형(Data Type) : 프로그래밍 언어에서 제공하는 자료 객체(원소, DataObject)외 그에 유효한 연산들 (ex: 정수형, 실수형, Boolean형, 문자형 등)
- 자료구조 (Data Structure) : 자료들끼리의 관계를 반영하여 자료를 효율적으로 처리할 수 있도록 컴퓨터에 저장하는 방법. 구체적인 구현까지 포함할 수 있음 (ex: 스택, 큐, 이즌 트리, 그래프 등)

자료구조의 분류

• 단순구조
  • 프로그래밍언어에서 제공하는 기본적인 데이터타입
  • 정수, 실수, 문자와 문자열 등
• 선형구조
  • 자료들 사이의 앞뒤 관계가 일대일(1:1)인 경우
  • ex) 리스트, 스택, 큐, 덱
• 비선형 구조
  • 자료들사이의 앞뒤 관계가 계층구조 혹은 망 구조를 가지는 경우
  • ex)트리, 그래프
• 파일구조
  • 보조기억장치에 저장되는 파일에 대한 자료구조

자료구조와 알고리즘 관계

자료구조와 알고리즘은 따로 떼어서 생갈할 수 없는 불가분의 관계
프로그램 = 자료구조 + 알고리즘

알고리즘과 알고리즘 분석

1. 알고리즘의 정의

주어진 문제를 효율적으로 해결하기 위한 단계별 명령의 집합

2. 알고리즘 5가지 조건

-입력조건(input) : 외부에서 제공 가능
-출력조건(output) : 하나 이상의 출력을 생성해야 함
-명확성(definiteness) : 각 명령은 모호하지 않아야 함
-유한성(finiteness) : 유한 스텝 후 종료
-효과성(effectiveness) : 모든 명령어들은 원칙적으로 종이와 연필 만으로도 수행될 수 있는 기본적인 것이어야함

3. 알고리즘 성는 분석

• 공간복잡도

• 시간복잡도

  • 실제 걸리는 시간을 측정
  • 입력 값에 따른 실행 연산의 빈도수

• 빅-오(O) 표기법

  • 시간복잡도 함수 중에 가장 큰 영향력을 주는 n에 대한 표시

  • 계수는 생략하여 표시

     ex) O(3n+2) = O(3n) = O(n)
     1. 계수 생략 -> O(3n)
     2. 가장큰 영향력 n에 대한 표시 -> O(n)