자료구조 기초 정리

유튜브 강의를 듣고 개인적으로 정리한 내용입니다  

 

자료구조란?

-컴퓨터 프로그래밍에 있어, 가장 기초적인 학문분야이다

-컴퓨터 프로그램의 기본골격으로 프로그램이 효율적이고 안전하게 동작하기 위해서 반드시 필요하다.

>>프로그램의 크기가 작거나 대형 프로젝트의 초기단계에서 이를 간과할 경우 구조적인 결함이 발생한다

 

프로그램의 수행시간 혹은 저장공간을 고려한 효율적인 자료구조의 설계

->프로그램이 어떻게 사용되는지에 따라 목적 및 기능에 부합하는 자료구조를 설계한다.

설계의 예시) 윈도우 탐색기의 경우 폴더구조 = 트리 / 파일목록 = 리스트

 

자료구조의 분류

단순구조 : 프로그래밍 언어에서 제공하는 기본적인 데이터 타입으로 정수(int) 실수(float) 문자와 문자열(char)이 있다.

선형구조 : 자료들 사이의 앞-뒤관계가 1:1로 순차적인 경우 (리스트, 스택, 큐, 덱 등이 있다)

비선형구조 : 자료들 사이의 앞-뒤 관계가 계층구조 혹은 망 구조를 가지는 경우(병렬적) (트리, 그래프 등)

파일구조 : 보조기억장치(하드디스크)에 저장되는 파일에 대한 자료구조 

 

추상자료형 : 추상적으로 정의된 자료형으로 자료구조를 기술하는 가장 대표적인 방법 중 하나이다 

//여기서 말하는 추상이란? 세부적이고 복잡한 것을 생략하고 대표적인, 중요한 것만을 나타낸다

 

이러한 자료구조를 이용하는 사용자는 내부 구현 소스에 대한 분석없이 인터페이스를 보고 신속하게 이용이 가능하고

개발자는 설계도를 미리 그려봄과 동시에 사용자 사이의 간섭 문제가 해결된다는 장점이 있다.

 

 

+ 05/20 내용 추가

- 리스트에 있는 데이터를 정렬할 때, 어떻게 정렬을 할 것인지 고려해야 한다

Out-of-place 정렬

데이터 구조의 복사본을 만든 후 정렬하는 방법이다 //용량이 늘어난다

in-place 정렬
내부에서 데이터 구조들의 위치를 바꾸어 정렬하는 방법이다 

 

- 리스트에 중복된 요소가 있는지 체크해야한다 

안정 정렬 : 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는 방법이다 
-> 순차적이고, 규칙적이다 
불안정 정렬 :  중복된 숫자의 순서를 보장할 수 없다 
-> 비 순차적, 불규칙적이다 

 

 

- 해당 정렬 알고리즘을 썼을때 걸리는 시간을 체크해야 한다

시간 복잡도
최악의 경우, 평균적인 경우, 최선의 경우의 복잡도가 존재한다
최악 : 정렬 전 요소들이 큰 수에서 작은 수로 있는 경우를 의미한다
최선 : 이미 정렬되어 있는 경우를 의미한다
평균 : 완전히 임의의 순서로 되어있는 리스트를 정렬하는 경우를 의미한다

시간복잡도는 Big O(빅 오) 표기법으로 표기하며, 

O(1) -> O(log n) -> O(n) -> O(n logn) -> O(n^2) 의 순서대로 오래걸린다

//n^2는 n의 2제곱이라는 의미이다