We.TIL 16 : 자료구조 01

자료구조란?

자료구조란 데이터에 편리하게 접근하고 조작하기 위해 데이터를 저장하거나 조직하는 방법이다.
각 언어가 가진 자료구조의 종류와 그것에 대한 사용 방법을 익히는 것도 중요하지만, 무엇보다 각 자료구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료구조를 선택하는 것이 매우 중요하다.

왜 자료구조인가?

자료구조란, 상황과 문맥에 맞게 데이터를 담을 수 있는 적절한 구조를 말한다. 데이터에 맞는 적절한 자료구조를 사용하는 것은 전체 개발 시스템에 굉장히 큰 영향을 끼친다.

자료구조의 분류

• 단순구조 : 프로그래밍에서 사용되는 기본 데이터 타입
• 비 단순구조 : 단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료구조
  1) 선형구조 : 저장되는 자료의 전후관계가 1:1(ex: List, Stacks, Queues)
  2) 비선형구조 : 데이터 항목 사이 관계가 1:n 또는 n:m(ex: Graphs, Trees)

일반적으로 가장 많이 사용되는 자료구조

Array, Tuple, Set, Dictionary, Stack&Queue, Tree

Array(list)

JavaScript에서는 Array, Python에서는 List
Array(List)는 가장 기초적이고 단순하면서도 가장 자주 사용되는 자료 구조. 이미 Repl.it 문제를 풀면서 여러분들이 많이 접해본 자료구조다.

Array 특징
순차적으로 데이터를 저장하는 자료구조

• Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점이다.
• 자료구조에 저장하는 데이터는 일반적으로 요소(element)라고 한다.
• Array는 주로 서로 연결된 데이터를 순차적으로 저장할 때 사용한다.
• 순서가 상관 없더라도 서로 연결된 데이터를 저장할 때 일반적으로 사용한다.
• 그래서 array가 가장 자주 사용되는 자료구조 중 하나가 되는 것이다.

기타 특징

• 삽입 순서대로 저장된다.(즉, 새로 삽입되는 요소는 array의 새로운 꼬리가 됩니다.)
• 이미 생성된 리스트도 수정 가능하다.(mutable)
• 동일한 값도 여러번 삽입 가능하다.
• Multi-dimensional Array(다중차원배열)
• array의 요소가 array가 될 수 있다. 이러한 array를 다중차원 array라고 합니다. 일반적으로 2D(2차원) array가 많이 사용된다.

Array 내부구조

• Array의 가장 큰 특징은 순차적으로 데이터를 저장하는 것이다.
• 이렇게 순서가 잇다보니 당연히 순차적으로 번호를 지정할 수 있다. 마치 학교에서 이름을 부르지 않고 번호를 부르는 것과 동일한 개념이다. 이 번호를 인덱스(index)라고 한다.
• Index는 0부터 시작된다. Index는 마이너스 부호를 가질 수 있다. 마이너스 index는 마지막 요소부터 시작된다. 예를 들어, -1은 맨 마지막 요소다.

왜 Array는 순차적으로 데이터를 저장할까?

• 그건 바로 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 때문이다.
• 데이터에 순서가 있기 때문에
  1) index가 존재하며 : 0부터 시작
  2) indexing : indexfㅡㄹ 사용해 특정 요소를 array로 부터 읽어 들이는 것이 가능하고
  3) slicing : 요소의 특정 부분, 즉 n번째 index부터 m번째 index까지 따로 분리해 조작하는 것이 가능하다.

단점
앞서 본대로 Array는 메모리의 실제 주소도 순차적으로 되어있다. 그렇기 때문에 indexing이 가능한 것을 비롯하여 여러 가지 장점이 있지만 반대로 단점도 존재한다. 이번에는 몇 가지의 단점에 대해 배워보자.

<1> Removing or Adding Elements

• 중간의 특정 요소를 삭제해야 하는 경우를 가정해보자.

  

• 순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간의 요소가 삭제되는 경우에 항상 메모리가 순차적으로 이어져있어야 하기 때문에, 삭제된 요소로부터 뒤에 있는 모든 요소들을 앞으로 한칸씩 이동시켜 줘야 한다.
  +이 뜻은 배열에서 요소를 삭제하는 것은 다른 자료구조에 비해 느릴 수 있다.

• 요소를 삭제하는 과정이 코드 상에서는 한 줄 이지만 실제 메모리상에서 이뤄지는 작업(operation)은 훨씬 커집니다.

• 중간에 요소가 추가 되는 경우도 마찬가지다. 특정 위치에 새롭게 요소가 추가되는 경우에는 그 뒤의 요소들이 하나씩 밀리게 된다.

• 그렇기 떄문에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.

<2> Array Resizing

• Resizing이란, 말 그대로 사이즈를 다시 조정한다는 뜻이다.
• 배열은 메모리가 순차적으로 채워지기 때문에 배열이 처음 생성될 때 어느정도 메모리를 미리 할당한다
• 이를 전문 용어로 pre-allocation이라고 한다.
• 메모리를 pre-allocation 함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장될 수 있습니다.
• 하지만 요소들이 처음 할당한 메모리 이상으로 많아진다면 resizing이 필요하다.
• 즉, 메모리를 더 할당해야 한다.
• 그리고 추가적으로 할당된 메모리 또한 순차적이어야 한다.
• 그럼으로 배열의 resizing은 상대적으로 오래걸리는 operation이다.

100개의 메모리 공간이 다 차서 100개를 추가해야 되는 경우

그렇기 때문에 Array는 사이즈 예측이 잘 안되는 데이터를 다루기에는 적절하지 않다. 일반적으로 대부분의 언어에서는 배열의 메모리 pre-allocation과 resizing을 자동으로 실행한다. 하지만 이러한 점을 알고 있어야 사이즈가 급격하게 자주 늘어날 확률이 있는 데이터는 array말고 더 적합한 자료구조를 선택해야 한다는 것을 알 수 있다.

언제 사용하면 좋을까?

• 순차열적인 데이터를 저장할 때(ex: 주식가격 : 어제 2만원과 오늘의 2만원이 다름>>값보다는 순서가 중요한 데이터)
• 다차원 데이터를 다룰 때
• 어떠한 특정 요소를 빠르게 읽어야 할 때(index를 통해 곧바로 읽을 수 있기 때문)
• 데이터의 사이즈가 급변하게 자주 변하지 않을 때
• 요소가 자주 삭제되거나 추가되지 않을 때

튜플(Tuple)

정의
튜플이란?

• List와 마찬가지로 데이터를 순차적으로 저장할 수 있는 순열 자료구조
• 하지만 리스트와 다르게 한 번 정의되고 나면 수정할 수 없다.(immutable)
• 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 때 자주 쓰인다.

Tuple의 장점

• 튜플은 간단한 값을 빨리 표현하고 싶을 때 많이 사용한다
• 예를 들면 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 경우(ex:지도 좌표)

Tuple의 단점

• 튜플의 단점은 데이터가 무슨 의미인지 명확하지 않다는 점이다.
• 데이터의 의미를 문맥을 보고 가정해야 한다.
• 예를 들어 객체의 경우 key-value 쌍으로 이루어진 데이터이기 때문에 무슨 데이터인지 파악이 쉽지만, 튜플의 경우 괄호 안에 데이터만 담겨있기 때문에 문맥에 맞게 의미를 추측해야 한다.
• 그렇기 때문에 튜플은 소규모 데이터를 다루기에 적합하다.
• 이러한 단점을 극복하기 위해 Named Tuple 이란 것도 존재한다.

언제 사용하면 좋을까?

• Array(List)를 쓰기에는 간단한 데이터를 표현할 때 사용한다.
• Tuple이 Array보다 더 가볍고 메모리를 더 적게 먹는다
• 예를 들어, 좌표 데이터의 경우 :