자료 구조란?

• 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조작하는 방법
• 자료 구조의 종류는 여러가지가 있다. 하지만 모든 목적에 부합하는 자료 구조는 없다. 각각의 자료 구조가 갖는 장점과 한계를 잘 이해하고 본인의 개발 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요하다.
• 무엇보다 중요한 것은 각 자료 구조의 본질과 컨셉을 이해하고 상황에 맞는 적절한 자료 구조를 선택하는 것이다.

Why Data Structure?

그래서 자료 구조를 왜 알아야할까? 자료 구조를 잘 이해하고 있다면 어떤 자료가 어디에 있는지 예측하는 것이 훨씬 쉬워진다. 즉, data가 어떤 원칙으로 배열되어 있는지를 알면 그 데이터를 찾기 쉽다는 것이 핵심이다. 따라서 data를 사용하는 효율이 훨씬 높아지게 된다.

자료 구조의 분류

자료 구조는 다음과 같이 분류된다.

• Primitive Data Structure ( 단순 구조 )

  → 프로그래밍에서 사용되는 기본 데이터 타입

• None-Primitive Data Structure ( 비단순 구조 )

  → 단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조

  • Linear Data Structure ( 선형 구조 ) : 저장되는 자료의 전후 관계가 1:1 ( ex. List, Stacks, Queues )
  • Non-Linear Data Structure ( 비선형 구조 ) : 데이터 항목 사이의 관계가 1:n or n:m (ex. Graphs, Trees )

가장 자주 사용 되는 자료 구조

• Array ( List )
• Tuple
• Set
• Dictionary
• Stack & Queue
• Tree

Array

• JavaScript 에서는 Array, Python에서는 List
• 가장 기초적이고 단순하면서도 가장 자주 사용 되는 자료 구조.

일반적으로 Python 에서는 Array보다 List가 더 많이 사용 되고 대부분의 경우 큰 차이가 없기 때문에 그냥 List를 사용하면 된다.

엄밀히 따졌을 때, Python에서 Array와 List가 같은 것은 아니다. 메모리 효율면에서는 Array가 더 유리하지만 사용하기에 List가 훨씬 편리하기 때문에 List를 대부분 사용한다.

Array 특징

순차적으로 데이터를 저장하는 구조

• Array의 가장 큰 특징은 순차적(ordered)으로 데이터를 저장한다.
• 자료 구조에 저장하는 데이터는 일반적으로 요소(element)라고 한다.
• Array는 주로 서로 연결된 데이터들을 순차적으로 저장할 때 사용된다.
• 순서가 상관 없더라도 서로 연결된 데이터들을 저장할 때 일반적으로 사용된다.
• 삽입 순서대로 저장된다.
• 이미 생성된 리스트도 수정이 가능하다. (mutable)
• 동일한 값도 여러번 삽입 가능하다.
• Multi-dimensional Array ( 다중차원 배열 ) : Array의 요소가 array가 될 수 있다. 이러한 array를 multi-dimensional array ( 다중차원 배열 ) 이라고 한다.

Array 내부 구조

• array는 순차적으로 데이터를 저장하는 자료 구조이다. 이렇게 순서가 있다보니 당연히 순차적으로 번호를 지정할 수 있다. 이 번호를 index라고 한다.
• Index는 0부터 시작된다. Index는 - 부호를 가질 수 있다. 그리고 - 부호는 맨 마지막 요소부터 시작한다.

Array는 왜 순차적으로 데이터를 저장할 수 밖에 없을까?

물리적으로 데이터가 순차적으로 저장되기 때문

• 데이터에 순서가 있기 때문에
  • 1) index가 존재하며
    : 0부터 시작하는 index
  • 2) Indexing
    : Index를 사용해 특정 요소를 array(list)로 부터 읽어 들이는 것이 가능하고
  • 3) Slicing
    : 요소의 특정 부분, 즉 n번째 index부터 m번째 index까지 따로 분리해 조작하는 것이 가능하다.

Array의 단점

Array는 실제 주소도 순차적으로 되어있다. 그렇기 때문에 Indexing이 가능한 것을 비록하여 여러가지 장점이 있지만 단점도 존재한다.

1. Removing or Adding Elements

중간의 특정 요소를 삭제해야하는 경우, 순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간의 요소가 삭제되는 경우에 항상 메모리가 순차적으로 이루어져있어야 하기 때문에 삭제된 요소로부터 뒤에 있는 모든 요소들을 앞으로 한 칸씩 이동시켜주어야 한다.

따라서 배열에서 요소를 삭제한다는 것은 다른 자료 구조에 비해 느릴 수 있다는 뜻이다.

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

즉, 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.

2. Array Resizing

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

그렇기 때문에 Array 는 사이즈 예측이 잘 되지 않는 데이터를 다루기에는 적절하지 않다.

그럼 언제 쓸까?

• 순차열적인 데이터를 저장할 때
• 다차원 데이터를 다룰 때
• 어떠한 특정 요소를 빠르게 읽어야 할 때 ( index를 통해 곧바로 읽을 수 있기 때문 )
• 데이터의 사이즈가 자주 변하지 않을 때
• 요소가 자주 삭제 되거나 추가되지 않을 때

Tuple

Tuple 이란?

• List와 마찬가지로 데이터를 순차적으로 저장할 수 있는 순열 자료 구조
• 하지만 한 번 정의되고 나면 수정할 수 없다. ( immutable )
• 2~3개 정도의 적은 수의 소규모 데이터를 저장할 때 많이 사용
• 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 때

Tuple의 장점

• 간단한 값을 빨리 표현하고 싶을 때
• 함수에서 리턴 값을 한 개 이상 리턴하고 싶을 경우

Tuple의 단점

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

언제 쓸까?

Tuple이 List보다 더 가볍고 메모리를 더 적게 먹기 때문에 List를 쓰기에는 간단한 데이터들을 표현할 때 사용한다.

---

면접 대비 질문

• 자료 구조의 정의와 중요한 이유

  자료 구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조작하는 방법을 의미한다. 이러한 자료 구조가 중요한 이유는 여러가지의 자료 구조 중 모든 목적에 부합하는 자료 구조는 존재하지 않기 때문에 본인의 개발 상황에 맞게 올바른 자료 구조를 선택하고 사용해야 코드를 훨씬 효율적으로 구현할 수 있기 때문이다.

• Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점

  List의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점이다. 이러한 특징으로 인해 다차원 데이터를 다루거나 어떠한 특정 요소를 빠르게 읽어야 할 때 사용이 용이하다는 점이 있다. 그에 반해 실제 주소도 순차적으로 되어 있기 때문에 중간의 특정 요소를 삭제하거나 수정해야 하는 경우 모든 요소들을 그 상태에 맞게 바꿔주어야하고, Resizing이 필요하다는 단점이 존재한다. 그렇기 때문에 이러한 작업이 필요한 과정에서는 List라는 자료 구조를 사용하기에 적합하지 않고 요소가 자주 삭제되거나 추가되지 않는 ( 자주 변하지 않는 ) 순차열적인 데이터를 저장할 때 주로 사용된다.

• Array를 적용 시키면 좋을 데이터의 예를 구체적으로 들어보자. 그리고 Array를 적용하면 좋은 이유, 사용하지 않으면 어떻게 되는지도 함께 서술

  Array(List)를 적용시키기 좋은 예시로는 주식 차트가 있다. 주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제 되는 정보가 아니며, 날짜별로 주식 가격이 차례차례 저장되어야 하는 데이터다. 즉, 순서가 굉장히 중요한 데이터이므로 Array(List)를 사용하지 않는 경우 (순서가 없는 자료 구조를 사용하는 경우)에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어들이고 비교해야하는 번거로움이 발생한다.