자료구조 배경지식

CHAN LIM·2022년 8월 2일
0

DS&Algorithm

목록 보기
1/11

자료구조

  • 자료(데이터)에 효율적으로 접근하고 수정할 수 있도록 저장, 조직, 관리하는 방법에 관한 이론.
  • 운영체제, 네트워크, 인공지능, 시스템 프로그래밍, 컴파일러 등 컴퓨터 과학의 거의 모든 주제를 구현하기 위한 사고의 빌딩 블록을 제공.

알고리즘

  • 문제 해결 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다.
  • 자료구조는 이 과정에서 부품과 같은 역할을 수행.

알고리즘, 자료구조, 프로그래밍, 이산 수학의 관계

알고리즘 수행 시간

  • 입력의 크기에 대해 시간이 얼마나 걸리는지 표현
  • 알고리즘의 시간 복잡도를 분석할 때는 수행 시간을 지배하는 부분이 어디인지 파악하는 것이 중요하다.
    • for 루프의 회전 횟수
    • 특정 라인의 수행 횟수
    • 함수의 표출 횟수

알고리즘 복잡도

  • Big-O (점근적 상한)

    • big-O는 점근적 상한으로, 복잡도 함수 f(n)에 대해 g(n)∈Ο(f(n))이면 n>N인 모든 정수 n에 대해서 0≤g(n) ≤c×f(n)이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재하게 됩니다.
  • small-O

    • 주어진 복잡도 함수 f(n)에 대해서 g(n) ∈o(f(n))이면 모든 양의 실수 c에 대해, n≥N인 모든 n에 대해서 0≤ g(n)≤c×f(n) 이 성립하는 음이 아닌 정수 N이 존재합니다.
  • Ω(점근적 하한)

    • 오메가는 점근적 하한으로, 복잡도 함수 f(n)에 대해 g(n) ∈Ω(f(n))이라면 n>N인 모든 정수 n에 대해서 g(n) ≥c*f(n) ≥0이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재하게 됩니다.
  • ω(small omega)

    • 복잡도 함수 f(n)에 대해 g(n) ∈Ω(f(n))이라면 모든 양의 실수 c에 대해 n>N인 모든 정수 n에 대해서 g(n) ≥c*f(n) ≥0이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재하게 됩니다.
  • Θ(차수)
    • Θ는 Θ(f(n))= O(f(n))∩ Ω(f(n))로 정의할 수 있습니다.

재귀 (자기호출)

  • 내 안의 나를 찾는 것
  • 컴퓨터 과학 이론의 근간을 이루는 중요 개념
  • 수열의 점화식
  • 자료구조에서 생각하는 방법 중 가장 중요한 구조
  • 어떤 문제가 자신과 성격이 똑같지만 크기만 더 작은 문제를 포함하고 있는 구조
  • 큰 의미 매듭이 같은 모양의 더 작은 매듭을 1개 이상 포함하고 있는 것

추상

  • 애매하다, 난해하다
  • 사고의 수준이 높다.
  • 미술: 사물의 사실적 재현이 아닌 순수하게 점, 선, 면, 색체의 순수한 조형적 요소로 구상한 것.
  • 음악: 특정한 이미지나 상징적 의미를 표출하려 하지 않고 음과 음의 관계와 조합을 통해 순수한 예술성을 추구하는 것.
  • 관점이 계층화되어 상승한 것
  • 인간의 사고가 진화해온 과정 자체가 추상의 역사이다.
  • 모듈
    • 의미의 단위
    • 먼저 추상적인 레벨에서 설계되고, 후에 구체화된다.

추상 데이터 타입 (Abstract Data Type)

  • 세부 사항에서 벗어나 추상적으로 정의한 데이터 타입.
  • 어떤 데이터 타입이 어떤 작업으로 이루어지는지만 표현한 것.
  • 작업을 나열해 표현하는 것을 "추상적으로 표현한다."라고 한다.
  • 객체 지향 언어에서 추상 데이터 타입은 대략 하나의 클래스에 대응한다.
  • ADT는 어떤 데이터 타입이 어떤 작업으로 이루어지는지를 세부 사항으로 표현한다.
  • 내부에서 작업을 "어떻게"하는지 신경 쓰지 않게 하며 "무엇을"하는지만 신경 쓰게 해준다.

자료구조의 종류

선형 자료구조

  • List (리스트)
  • Queue (큐)
  • Stack (스택)

색인 자료구조

  • Search Tree (검색 트리)
    • Binary Search Tree (이진 검색 트리)
    • AVL (균형 검색 트리)
  • Hash Table (해시 테이블)

관계 처리 자료구조

  • Graph (그래프)
profile
클라우드, 데이터, DevOps 엔지니어 지향 || 글보단 사진 지향

0개의 댓글