자료 구조 공부 중

부끄럽게도 프로젝트를 몇번 진행하면서도 자료구조에 대해 공부할 필요성을 크게 느끼지 못했다. 자료구조에 대한 큰 고민 없이 배운대로 만든

기능들은 잘 작동하였고 느리지도 않았기 때문이다.

​

하지만 작동하는 코드를 만드는 것 뿐 을 넘어서 코드의 퀄리티를 높이고 효율적인 코드를 만드는 것에도 신경을 쓰는 좋은 개발자가 되고싶다면

자료구조 공부는 필수적이다.

​

코드를 하면서 몇번 들어보기만 했던 여러 자료구조에 대해 다시 공부하고 정리를 해보려 한다

------------------------------------------------------------------------------------------------------------------------------------------

시간복잡도(Time Complexity) 란 데이터 구조의 알고리즘이 얼마나 빠르고 느린지 측정하는 방법

실제 시간을 재는 것이 아닌, 몇 단계로 이루어져 있는지로 판단

​

Array (배열)

구조를 보면 아래와 같은 형태로 이루어져있음

Array = [ { name : "choi", age : 27}, { name : "kim", age : 30}, { name : "jyung", age : 32} ]

​

Read, Searching, Insert, Deleter 에 따른 시간 복잡도

Read : Random Access임

즉, 인덱스 번호만 알면 그 해당 인덱스 값을 바로 불러올 수 있음 데이터가 몇개가 들어있는 배열이든 상관없음, 매우빠름

시간 복잡도 O(1)

​

Searching : Linear Search(선형검색) 하나하나 다 찾아야함,

찾으려는 값의 위치에 따라 바로 찾을수도 맨 마지막에 찾을 수도 있음

시간 복잡도는 최대 O(N)

​

Insert : 여러 경우의 수로 나뉨

배열에 끝에 빈 공간에 삽입 할 경우 빠름, 시간 복잡도 O(1)

배열의 중간에 넣고 한칸씩 미뤄야 할 경우 보통

배열의 첫자리에 삽입하려 할 경우 모든 데이터를 뒤로 미뤄야함, 배열의 자리가 부족하다면 배열 자체를 새로만들고 기존 데이터를 카피 한 뒤 추가 데이터가 삽입됌, 느림, 시간 복잡도 O(N)

​

​

Delete : 삽입과 비슷함

배열의 끝을 삭제 할 경우 빠름, 시간 복잡도 O(1)

배열의 중간을 삭제 할 경우, 빈 공간을 채우기 위해 뒤에 값 들을 떙겨야함 보통

배열의 첫 번째 요소를 삭제할 경우 모든 데이터를 땡겨야함, 느림, 시간 복잡도 O(N)

​

결론: 배열은 읽기에서 매우 빠름

검색,추가,삭제는 경우의 수에 따라 빠름-보통-느림이 결정.

​

------------------------------------------------------------------------------------------------------------------------------------------

Hash Table(해시 테이블)

Hash Table 이란 Key Value System 으로 Key : Value 형태로 이루어져 있음

​

Hash Table = { choi : 27, kim : 30, jyung : 32}

​

검색 시

Array 의 시간 복잡도는 O(N) 이고,

Hash Table의 시간 복잡도는 O(1)

​

추가로

Hash Table 에선 추가, 삭제도 시간복잡도는 O(1)

​

결론: 해시테이블은 배열과 비교하여 검색, 삽입 ,삭제 시 더 빠른 속도를 기대할 수 있음

​

​

------------------------------------------------------------------------------------------------------------------------------------------

Queues(큐), Stack(스택)

​

스택과 큐는 일종의 규칙임, 자료 구조가 '큐'혹은 '스택'으로 구분되기 위한 규칙들

이러한 것들을 추상적 자료구조 (Abstract Data Type) 'ADT' 라고 부름

​

형태는 배열과 같으며 배열에 추가적인 규칙을 더한 것이 스택과, 큐

​

스택의 규칙

(Last In, First Out) LiFo, 나중에 들어온 것이 먼저 나감

​

큐의 규칙

(First in, First Out) FiFo,먼저 들어온 것이 먼저 나감

​

스택의 예시로는 인터넷 브라우저에 '뒤로감기' , Crtl + Z 기능인 '되돌리기' 등이 있음

큐의 예시로는 이메일 전달, 쇼핑몰 주문 순서 등 다양하게 존재

​

이러한 추상덕 자료 구조를 통해 자료를 이해하는데 좀 더 구조적으로 생각해 볼 수 있음

​

------------------------------------------------------------------------------------------------------------------------------------------

Search algorithm 에는

Binary Search (이진 검색 알고리즘), Linear Search(선형 검색 알고리즘)이 존재

​

Linear Search (선형 검색 알고리즘)

찾는 것이 나올 때 까지 처음부터 하나하나 찾음

배열이 커질수록 검색 시간이 길어짐 , 이러한 것을 Linear Time Complexity(선형 시간 복잡도)라고 함

​

Binary Search (이진 검색 알고리즘)

Sorted Array(정렬된 배열) 에서만 사용가능함

(Sorted Array 란 오름차순, 내림차순 등 정렬된 배열을 뜻함)

​

여기서 Binary는 0과 1이 아닌 반으로 쪼개는 걸 의미함

​

이진 검색 알고리즘은 검색 시

찾고자 하는 값과 인덱스 중간 값을 비교하여 왼쪽, 오른쪽으로 이동 하게 되며 이걸 반복하게 됌

우리가 숫자 맞추는 업다운 게임을 할 때랑 비슷한 느낌이라 보면 됌

​

Binary Search는

검색은 Linaer Search보다 빠르다는 이점이 있지만,

Sorted Array인 것을 감안하면 데이터 삽입 시 정렬되지 않은 배열보다 느릴 수 밖에 없음

------------------------------------------------------------------------------------------------------------------------------------------

Sorting algorithm

sorting은 정렬을 뜻한다. 큰 수에서 작은 수나 알파벳 순 등으로 정렬을 하는 것을 얘기함

​

Sort에는

Bubble Sort, Selection Sort, Insertion Sort 로 나누어져 있다. 모두 같은 BIG O를 가지지만 성능은 다르다​​

​

Bubble Sort

버블 솔트는 배열에 값을 2개씩 서로 비교하여 위치를 바꾸는 식으로 모든 인덱스를 하나하나 다 비교하는 것이다.

​

오름차순 정렬로 예시를 들면

첫 번째 사이클 : 인덱스0, 인덱스1 값을 비교하여 작은 값을 왼쪽으로 위치시킴 -> 인덱스 1과 인덱스 2 비교하여 작은 값을 왼쪽으로 위치시킴 -> 이 작업을 인덱스 끝까지 반복

​

두 번째 사이클 : 위와 동일하게 반복

​

인덱스 수 만큼 사이클이 반복

​

좋은 알고리즘은 아니며, 자주 사용하지는 않는다고 함

시간 복잡도는 O(N^2)이다.

​

Selection Sort

오름차순 정렬로 예시를 들면

첫 번째 사이클 : 배열을 전부 돌아 가장 작은 값 위치를 저장하여, 가장 앞쪽인 인덱스0과 Swap을 진행

​

두 번째 사이클 : 인덱스0을 제외하고 배열을 전부 돌아 가장 작은 값 위치를 저장하여, 가장 앞쪽인 인덱스1과 Swap을 진행

​

그 다음 반복에서는 인덱스0과 인덱스1을 제외하고 작업을 수행,

계속해서 Swap 후 작업을 진행한 앞쪽 인덱스를 제외하면서 반복시킴으로 오름차순을 구현

​

버블 솔트와 비교 시 이것은 Swap을 1번씩 밖에 하지 않는 다는 것. 이로 인해 버블보다 훨씬 속도가 빠름

시간 복잡도는 O(N^2)이다.

​

Insert Sort

오름차순 정렬로 예시를 들면

첫 번째 사이클 : 인덱스 1, 인덱스 0 비교하여 작은 값을 왼쪽으로 위치시킴

​

두 번째 사이클 : 인덱스2, 인덱스1 비교하여 작은 값을 왼쪽으로 위치시킴 -> 인덱스 1, 인덱스 0 비교하여 작은 값을 왼쪽으로 위치시킴

​

세 번째 사이클 : 인덱스3, 인덱스2 비교하여 작은 값을 왼쪽으로 위치시킴 -> 인덱스 2,인덱스 1 비교하여 작은 값을 왼쪽으로 위치시킴

-> 인덱스 1, 인덱스 0 비교하여 작은 값을 왼쪽으로 위치시킴

​

계속해서 반복

​

삽입정렬은 필요한 아이템만 스캔을 하는 방식으로, 선택정렬보다 빠름 (선택 정렬은 모든 아이템을 스캔함)

시간 복잡도는 O(N^2)이다.

​

삽입 정렬, 선택 정렬 둘 다 최악의 경우 시간복잡도는 O(N^2)이지만,

최고 시나리오인 경우 삽입 정렬이 O(N)이 발생하여 평균적으로 성능이 좋다고 여김

​

그 외에 Quick Sort, Merge Sort 등이 있다고 함..