[알고리즘] 자료구조, 배열, linked list

자료구조

특정 자료구조는 삽입/삭제가 빠르고, 특정 자료구조는 조회가 빠르다.

이렇게 어떤 경우에 이 자료가 좋고, 어떤 경우는 저 자료가 좋은 것 처럼

경우에 따라 다양한 자료구조와 알고리즘을 사용해야한다.

비유

못을 박을때는 망치가 필요, 나사를 뺄 때는 뺀치가 필요한것처럼, 다양한 공구들의 사용법을 배우는것이다.

Array

• 순차적으로 데이터를 저장

• 배열은 크기가 정해진 데이터의 공간. 한번 정해지면 바꿀수 없다.

->원소를 새로 추가하려면, 새로운 공간을 할당을 해야하기때문에 매우 비효율적 자료구조

 

• index를 통해 원소에 즉시 접근할수있다. Ex rooms[3]

-> 즉시 접근 가능하다는것은 상수 시간내에 접근할수있으므로 O(1)내에 접근 할수있다고 말한다.

 

배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야한다. Ex) G의 데이터를 D로 옮길때 F와 G를 바꾸고 G와 E바꾸고 D와 G를 바꾼다. 이렇게 되면 3번의 과정과 각각의 원소들이 한칸씩 계속해서 바꿔줘야했다.

Linked List

= 리스트 라는 단어와 혼용되서 사용

다음 노드(Next node)라고 불리는 공간에 저장, 그 다음 공간을 지목하는 포인터라는 공간이 있다.

조회를 하기위해선 한칸한칸 거쳐서 이동하여 찾는다.

-> 즉 리스트 길이에따라 O(N) 의 시간복잡도를 가진다.

중간에 삽입/삭제 할때 연결하는부분의 연결고리를 끊고 추가/삽입후 다시 연결한다

-> 삽입/삭제를 위해선 앞뒤 포인터만 변경하기때문에 O(1)의 시간복잡도를 가진다.

추가시

삭제시

 

따라서 표를 이용하여 차이를 비교

경우	Array	Linked List
특정 원소 조회	O(1)	O(N)
중간에 삽입/삭제	O(N)	O(1)
데이터 추가	데이터 추가시 모든 공간이 다 찼다면 새로운 메모리 공간을 할당 받아야한다.	모든 공간이 다 찼어도 맨뒤에 노드만 동적으로 추가하면 된다.
정리	데이터 접근이 빈번한 경우 Array사용	삽입/삭제가 빈번하다면 Linked List 사용

동적 배열

실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다.

너무 작은 영역을 할당하여 모자라거나, 너무 많은 영역을 할당하여 낭비될 때도 있다

크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열이 등장

 

파이썬의 경우 append 메서드를 사용하여 데이터를 추가하게 되는데 이때 파이썬의 경우는 내부적으로 동적 배열이라고 하여 배열의 길이가 늘어나도 O(1)의 시간복잡도를 갖도록 설계하여 파이썬의 배열은 배열/링크드 리스트로 쓸수있도록 효율적인 자료구조 라고한다.

 

그럼 자바스크립트는?

Push,unshift 메서드, splice,pop 메서드 사용등 추가/삭제/교체 가능

->이때 push, pop 메서드 사용하면 배열 맨끝에 추가 및 삭제 이기때문에 O(1)의 시간복잡도를 가진다.

->반대로 unshift, splice 메서드 사용시 배열의 맨앞에 추가 및 삭제 하기때문에 기존에 있던 데이터들의 위치가 차례로 밀리기 때문에 O(N)의 시간복잡도를 가진다.

->즉 앞에서 이야기한것처럼 앞이냐 뒤냐에 따라 시간복잡도의 효율성이 달라지고 빅오(최악)이 될수도 있고 오메가1(최선) 이 될수도있다. 하지만 앞에서 이야기한것처럼 우리는 최악을 고려하여야하지만(즉 O(N)+O(1)=O(N)이다), 동적배열이므로 앞에 넣냐 뒤에 넣냐에 따라서 알면된다고 생각한다.

 

고려/생각 접근해볼것

->그렇다면 unshift나 splice 사용하여 맨앞에 추가/삭제 하기보단 뒤에서 추가한후 sort 하는 방식이 더 빠른가?

 

정적배열/동적배열

위에서 동적 배열이라는 단어를 언급했는데 이때 마한 동적배열이 있다면 이건 무엇이고 정적배열은 무엇인지 설명하자면

배열의 크기가 고정되어있는것이 정적배열, 크기가 고정되어있지 않다면 동적 배열인것이다.

c++같은경우의 배열은 정적인 개념이지만 자바스크립트(위에서처럼 파이썬도) 배열의 경우는 동적 배열의 개념인것이다. 

 

정적배열 과 동적배열을 표로 차이를 나타내보자.

	정적 배열 시간복잡도	동적배열 시간복잡도
접근(조회, access)	O(1)	O(1)
탐색(search)	O(N)	O(N)
중간삽입(insert)	O(N)	O(N)
중간삭제(delete)	O(N)	O(N)
추가(add)	N/A 새로운 추가되는 인덱스일때 새로운 메모리를 만들어야함	O(N), 맨뒤O(1)