[자료구조] 1. 자료구조란 무엇인가

1. 자료와 정보의 관계

자료(Data)

• 현실 세계에서 관찰이나 측정을 통해 수집된 값(Value) 이나 사실(Fact).

정보(Information)

• 적절한 의사결정(decision)을 할 수 있도록 하는 지식(knowledge) 으로서, 자료의 유효한 해설(interpretation)이나 자료 상호관의 관계(relationship) 을 표현하는 내용

자료 ⇒ 처리(컴퓨터) ⇒ 정보 I = P(D)

---

2. 추상화의 개념

추상화

• 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것

---

3. 자료구조의 개념

자료구조(Data Structure) 란?

• 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해 실시하는 자료의 추상화

알고리즘

• 컴퓨터가 어떤 수행을 실시하기 위해 필요한 명령의 집합

복잡한 데이터와 알고리즘을 이용하기 위해 정밀한 자료구조 설계가 필요하다 개발자 → 추상화 → 자료구조 ← 구체화 ← 컴퓨터

자료구조의 형태

• 언어에서 제공하는 '미리 정의된 자료구조'
  • 기본 자료구조

    • 정수

    • 실수

    • 문자

    • 등..
  • 파생된 자료구조

    • 배열

    • 구조체

    • 포인터

    • 등..

• 개발자가 필요에 의해 정의하는 '사용자 정의 자료구조'
  • 리스트
  • 트리
  • 스택
  • 큐
  • 그래프
  • 등..

---

4. 자료구조와 알고리즘의 관계 및 알고리즘의 특성

추상화 된 알고리즘의 예시

• 집에서 학교에 가기 알고리즘
  1. 집에서 출발
  2. 차에 탄다
  3. 차에서 내린다
  4. 강의실에 들어간다

알고리즘은 추상화 시킨 동작들의 연속

알고리즘이 가지고 있어야 하는 조건

1. 출력 : 적어도 한 가지 이상의 결과를 생성해야 한다.

2. 유효성 : 모든 명령은 사람이 수행하나 컴퓨터가 수행하나 같은 결과가 나와야 한다(속도의 차이일 뿐)

3. 입력 : 외부에서 입력되는 자료가 있을 수 있다.

4. 명확성 : 각 명령은 명확하고 애매모호 하지 않아야 한다

5. 유한성 : 언젠가는 끝나야 한다

---

5. 알고리즘 성능의 분석과 측정

5.1 알고리즘 실행 시간의 예측

• 알고리즘 실행 예측시간 $O(n)$ 은 경향성에 대한 예측이다.

  (모든 알고리즘이 개별적으로 다른 실행 횟수를 가지기 때문에 정확한 시간을 의미하는것이 아님)

5.2 실행 메모리의 예측

• 알고리즘의 공간 복잡도(space complexity)는 프로그램을 실행시켜 완료하는데 필요한 총 메모리 공간을 의미한다.

💡

$S_p = S_c + S_e$

• $S_p$ (Space for Program) : 어떤 프로그램 P의 수행에 필요한 총 메모리 공간

• $S_c$ (Space for Compile) : 프로그램 크기나 입출력 횟수에 상관없이 컴파일할 때 결정되어 종료될 때 까지 고정적으로 필요한 메모리 공간 (고정 공간)

• $S_e$ (Space for Excution) : 프로그램의 실행 과정에서 동적으로 할당되어야 하는 자료구조와 변수들을 위해 필요한 메인 메모리 공간 (가변 공간)

알고리즘에 필요한 메모리 총량을 고려해야 함

5.3 실행 시간의 측정

• 실제 시간의 측정

Uploaded by Notion2Tistory v1.1.0