[자료구조] Chapter 01. 자료구조와 알고리즘

🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.

• 자료구조 : Data의 표현방식(=Data Type)과 그들의 연산(사용법, method)

• ADT(Abstract Data Type : 추상적 자료구조) : 구현 방법은 생략, 사용법(연산)만 암시
  => portability (이식성 : 서로 다르게 저장되어 있어도 사용하는 방법(메뉴얼)은 같음)

  

• 기억 장치의 구성(Main Memory)

  • 1-bit storage : Data(0 or 1) 저장의 최소 단위 (2진수)
  • 1-byte = 8-bits : memory의 기본 단위
    • 모든 byte가 고유 번호(주소) 부여 => Byte Addressing
  • 1-word : Data 저장의 기본 단위(최대 2^n 개의 data 저장 가능)

• 기본 Data Type

  • 수(number)
    1. 정수 (integer)
    2. 실수 (real number)
  • 문자 (character)
  • 주소 (address, pointer)

알고리즘(Algorithm)

problem(문제) -> Algorithm : 컴퓨터로 문제를 해결하는 유한한 단계적 방법

• 알고리즘의 조건
  1. Halt (유한해야함)
  2. Correct Answer (정확한 정답)
  3. Input 개수 >= 0 && Output 개수 >= 1
  

  ex) 페르마의 마지막 정리(Fermat's Last Theorem)
  

  

• 성능함수(성능을 나타내는 함수)
  Big-Oh 표기법(Asymtotic Rotation) -> 상한선의 의미