[Data Structure] 1. 자료구조와 알고리즘

rany·2020년 5월 26일
0

자료구조

목록 보기
1/4
post-thumbnail

자료구조 복습이 절실히 필요해서 오늘부터 다시 공부하면서 벨로그에 기록해보려고 한다. 전공 수업 때 자료구조 수업을 프린트로 나가서 집에 전공책도 없었다는게 새삼 놀라웠다 😅
그래서 이번에 한 권 구입했다ㅎㅎ 검색해보니 책이 엄청 많던데 내가 고른 책은 생능출판사의 'C언어로 쉽게 풀어쓴 자료구조'이다. 책 자체가 크고 여백이 많고.. 무엇보다!! 올컬러라 아주 마음에 든다 😍
어쨌든, 이 시리즈는 책을 보고 공부하며 요약하는 글이라고 보면 되겠다.

Data Structure(자료구조)

정의

컴퓨터 프로그램에서 자료들을 정리하여 보관하는 여러 가지 구조

종류

  • 스택
  • 리스트
  • 그래프
  • 트리

    스택, 큐, 리스트는 선형구조이고 트리, 그래프는 비선형구조이다.


Algorithm(알고리즘)

정의

주어진 문제를 풀기 위한 단계적인 절차

알고리즘이 되기 위한 조건들

  • 입력 : 0개 이상의 입력
  • 출력 : 1개 이상의 출력
  • 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 함
  • 유한성 : 한정된 수의 단계 후에 반드시 종료되어야 함
  • 유효성 : 각 명령어들은 컴퓨터로 실행 가능한 연산이어야 함

ADT(Abstract Data Type; 추상 자료형)

정의

추상적, 수학적으로 자료형을 정의한 것

추상화?

어떤 시스템의 간략화된 기술 또는 명세로서 핵심적인 구조, 동작에만 집중하는 것


알고리즘 성능 분석

알고리즘의 분석 측면

  1. Time Complexity(시간 복잡도) : 알고리즘의 수행 시간 분석
  2. Space Complexity(공간 복잡도) : 알고리즘이 사용하는 기억공간 분석

빅오 표기법

시간복잡도 함수에서 최고차항의 차수만을 사용. 계수도 고려하지 않음.

중간고사 공부할 때 시간 복잡도 함수 계산하던 기억이 떠오른다..

그 외

알고리즘의 시간 복잡도 척도로 최악의 경우 수행시간을 쓴다. 최악의 경우란 입력 자료 집합을 알고리즘에 최대한 불리하도록 만들어서 얼마만큼의 시간이 소모되는지 분석하는 것.
효율적인 알고리즘은 알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧고 메모리를 덜 사용하는 알고리즘이다.

profile
컴퓨터는 나의 베프

0개의 댓글