Data Structure의 개념
1. 자료구조란?
- 데이터에 편리하게 접근하여 조작을 하기 위해 데이터를 저장하거나 조직하는 방법
- 자료구조의 종류는 다양하며, 각자 특성이 있어 장점과 한계를 잘 이해해야한다.
- 상황,문맥에 따른 자료구조 사용이 중요
- 언어별로 양상이 다름
- 데이터에 맞는 적절한 자료구조를 사용하는 것이 전체 개발에 큰 영향을 끼친다.
- Array(Python에서는 List), Tuple, Set, Dictionary, Stack & Queue, Tree
"코딩은 알고리즘과 자료구조, 이 두가지로 이루어진다." - 리누스 토르발스
2. 자료구조의 분류
- Primitive Data Structure(단순 구조)
프로그래밍에서 사용되는 기본 데이터 타입 - None-Primitive Data Structure(비단순 구조)
단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조- Linear Data Structure(선형 구조)
: 저장되는 자료의 전후 관계가 1:1 (ex. List, Stacks, Queues) - Non-Linear Data Structure(비선형 구조)
: 데이터 항목 사이의 관계가 1:n 또는 n:m (ex. Graphs, Trees )
- Linear Data Structure(선형 구조)
Array(list)
1. 정의
- JavaScript 에서는 Array, Python에서는 List
- Array(List)는 가장 기초적이고 단순하면서도 가장 자주 사용 되는 자료 구조
- Python 에서는 List 가 Array 라고 생각하고 써도 무방하지만 엄밀히 말하자면 Array 와 List 는 다르다.
- 메모리 효율면에서는 Array 가 유리하다.(Python 에서 import Array 모듈을 import 해서 사용)
2. 특징
순차적으로 데이터를 저장하는 자료 구조
- 순차적(ordered)으로 데이터를 저장
- 자료구조에 저장하는 데이터 == 요소(element)
- 서로 연결된 데이터들을 순차적으로 저장할때 사용
- 순서가 상관 없어도 서로 연결된 데이터들을 저장할때 일반적으로 사용
- 삽입(insertion)은 순서대로 된다.
- 이미 생성된 리스트도 수정 가능(mutable).
- 동일한 값도 여러번 삽입 가능
Multi-dimensional Array(다중차원 배열)
- Array의 요소가 array가 될 수 있습니다. 이러한 array를 다중차원(multi-dimensional) array라고 한다. 일반적으로 2D (2차원) array가 많이 사용된다.
3. 내부 구조
- 순차적으로 번호를 지정할 수 있으며,index 라고 한다.
- Index는 0부터 시작된다.
- 마이너스 index는 맨 마지막 요소 부터 시작한다.
Array가 순차적으로 데이터를 저장하는 이유는?
- 물리적으로 데이터가 순차적으로 저장되기 때문이다.
- 데이터에 순서가 있기 때문에
- 1) index가 존재: 0부터 시작하는 index
- 2) Indexing: Index를 사용해 특정 요소를 array(list)로 부터 읽을 수 있다.
- 3) Slicing: 요소의 특정 부분, 즉 n번째 index부터 m번째 index까지 따로 분리조작이 가능하다.
4. 단점
1. Removing or Adding Elements
-
중간의 특정 요소를 삭제한다면, 순차적으로 담겨있는 데이터 중 특정 위치에 있는 요소가 삭제 된다.
-
이 경우 삭제된 요소부터 뒤에 있는 모든 요소들은 앞으로 한칸씩 이동한다.
-
요소를 삭제하는 과정이 코드 상에서는 한 줄 이지만 실제 메모리 상에서 이루어지는 작업(operation)은 훨씬 커진다.(expensive operation)
-
중간에 요소가 추가 되는 경우도 마찬가지다.
-
특정 위치에 새롭게 요소가 추가되는 경우에는 그 뒤의 요소들이 하나씩 밀리게 됩니다.
-
그렇기 때문에 Array 는 정보가 자주 삭제 되거나 추가되는 데이터를 담을 때 비 효율적이다.
2. Array Resizing(사이즈 재조정)
- 배열은 미리 메모리를 할당 한다. (pre-allocation)
- 메모리를 pre-allocation 함으로써 새로 추가되는 요소들도 순차적으로 메모리에 저장된다.
- 그러나 요소들이 많아진다면 resizing을 해야한다.(메모리 추가 할당 + 순차배열)
- 그럼으로 배열의 resizing은 상대적으로 오래걸리는 작업이다.예)
100개의 메모리 공간 다 차서 100개를 추가해야 되는 경우
- 200개 크기의 메모리를 생성 후 > 기존 100개를 복사하고 > 그 다음 101번 부터 데이터가 순차적으로 추가 - 사이즈 예측이 안되면 배열을 사용하기 쉽지 않음.
5. 언제 사용할까?
- 순차열적인 데이터를 저장할 때
- ex) 주식 가격. 어제의 2만원과 오늘의 2만원이 다름 >>> 값보다는 순서가 중요한 데이터
- 다차원 데이터를 다룰 때 >>> Multi-dimensional Array
- 어떠한 특정 요소를 빠르게 읽어야 할 때 >> index를 통해 곧바로 읽을 수 있기 때문
- 데이터의 사이즈가 급변하게 자주 변하지 않을 때
- 요소가 자주 삭제 되거나 추가되지 않을 때
면접 기출
1) 자료구조의 정의와 중요한 이유를 설명하세요.
내 답안)
자료구조란 컴퓨터 공학에서 상황에 맞춰 데이터에 효율적인 접근과 조작을 가능하게 하는 자료 저장, 조직을 의미한다. 자료구조는 효율적으로 쓰여질 때 전체 개발 과정에서 시간과 메모리를 줄일 수 있기때문에 중요하다.
모범 답안)
자료 구조란 데이터의 편리한 접근과 조작을 가능하게 하는 데이터를 저장하거나 조직하는 방법입니다. 문맥과 데이터의 종류에 따라 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 끼칩니다. 그렇기 때문에 자료구조의 다양한 종류와 각각의 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요합니다.
2) Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명하세요.
내 답안)
Array(list)는 순차열적으로 데이터를 저장한다. 특정 요소를 빨리 읽거나, 순차열적인 데이터를 저장하는데 유리하며 수정이 가능하다. 다차원 데이터를 저장할 때 사용할 수도 있다. 하지만, 요소를 제거하거나, 삭제할 때 요소가 앞으로 한칸씩 이동되기 때문에, 삭제와 추가가 많이 생기는 데이터의 경우 사용을 하면 안되고, 메모리 사이즈 재조정이 이루어질 경우 사용이 어렵다.
모범 답안)
Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다. 이렇게 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다. 반면에 이에 따른 단점도 존재하는데, 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제 되는 경우 그 뒤의 모든 요소들을 한칸씩 뒤로 밀거나 당겨줘야 하는 단점이 있습니다. 이러한 경우 메모리 상에서 이루어지는 작업이 다른 자료구조에 비해 커지기 때문에 Array 는 정보가 자주 삭제 되거나 추가되는 데이터를 담기에는 적절치 않습니다.
3) Array를 적용 시키면 좋을 데이터의 예를 구체적으로 들어주세요. (ex. 주식 차트) 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 서술해주세요.
내 답안)
과거와 현재 날씨에 대한 데이터에 array를 적용시키면 좋다. 날씨에 대한 데이터는 과거부터 현재 혹은 가까운 미래까지 날짜에 맞춰 차례대로 데이터가 저장되야 한다. 중간에 어떤 날씨가 새롭게 추가되거나 삭제되지 않기 때문에 Array를 적용시키는게 좋다. 만약 Array를 사용하지 않을 경우 순서가 없기 때문에 특정 날짜에 따른 날씨 정보를 확인할 수 없어서 자료를 모두 가져와야하는 단점이 생긴다.
모범 답안)
Array를 적용시키면 좋은 예로 주식 차트가 있습니다. 주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다. 즉, 순서가 굉장히 중요한 데이터 이므로 Array 같이 순서를 보존 해주는 자료구조를 사용하는 것이 좋습니다. 이와 같은 데이터에 Array를 사용하지 않는 경우, 즉 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.
