Data Structure
데이터 구조란 무엇인지, 왜 중요한지, 그리고 데이터 구조의 첫 번째 Array와 Tuple에 대해 배워봅시다.
✔️Data Structure의 개념 필요성, 그리고 다양한 종류의 자료구조에 대해 이해한다.
✔️Array의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다.
✔️Tuple의 개념과 장점, 단점, 그리고 언제 사용하면 좋은지 이해한다.
Data Structure(자료 구조)란 무엇인가?
자료구조란 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법입니다.
- 자료구조의 종류에는 여러가지가 있습니다. 하지만 모든 목적에 부합하는 자료구조는 없기 때문에
각 자료구조가 가지는 장점과 한계를 이해하고 상황에 맞는 올바른 자료 구조를 선택하고 사용해야 합니다. - 자료구조는 언어별로 지원하는 모양이 다릅니다.
- 언어별로 지원하는 자료구조가 다르더라도 개념을 올바르게 알고 있으면 해당 언어에 맞추어서 사용 가능합니다.
왜 Data Structure을 사용하는가?
우리는 무언갈 담기 위해 다양한 가방을 이용합니다.
여행을 갈 때는 많은 짐의 양을 한꺼번에 담을 수 있는 큰 캐리어, 화장품을 넣을 때는 작은 파우치 등 내용물에 맞는 적절한 가방을 사용합니다
- 이처럼 자료구조란, 상황과 맥락에 맞게 데이터를 담을 수 있는 적절한 구조를 말합니다.
- 데이터를 맞는 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 굉장히 큰 영향을 끼칩니다.
Data Structure의 분류
- Primitive Data Structure(단순 구조)
: 프로그래밍에서 사용되는 기본 자료구조.실제로 컴퓨터는 0과 1만을 다룰 수 있기 때문에 다를 수 있는 기본형의 종류는 세 가지에 불과합니다.
숫자, 문자, True/False, 이것이 컴퓨터가 다를 수 있는 기본 자료형의 종류입니다 - Non-Primative Data Structure(비단순 구조)
: 단순한 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 사용하는 구조
- Linear Data Structure(선형 구조)
: 저장되는 자료의 전후 관계가 1:1 (ex. List, Stacks, Queues)
- Non-Linear Data Structure(비선형 구조)
: 데이터 항목 사이의 관계가 1:n 또는 n:m, 데이터가 트리 형태로 저장되어있는 자료구조 (ex. Graphs, Trees)
일반적으로 가장 자주 사용되는 데이터 구조
- Array(Python에서는 List)
- Tuple
- Set
- Dictionary
- Stack & Queue
- Tree
1. Array(List)
1) Array(List)란?
가장 기초적이고 단순하면서 가장 자주 사용되는 자료 구조입니다.
JavaScript에서는 Array, Python에서는 List
2) Array의 특징
Array는 순차적(ordered)으로 데이터를 저장할 때 사용하는 가장 일반적인 자료구조입니다.
- 순서가 상관 없더라도 서로 연결된 데이터들을 저장할 때 사용합니다.
- 자료 구조에 저장하는 데이터를 요소(element)라고 합니다.
기타 특징
- 삽입된 순서대로 저장됩니다. 새로 삽입되면 맨 뒤로 갑니다.
- 이미 생성된 리스트도 수정 가능합니다.(mutable)
- 동일한 값을 여러번 삽입 가능합니다.
- 다중차원 배열(Multi-dimentional Array)도 가능합니다
:Array의 요소가 Array가 될 수 있습니다
3) Array 내부 구조
Array의 가장 큰 특징은 순차적으로 데이터를 정리하는 것입니다.
이렇게 순서가 있다보니 당연히 순차적으로 번호(index)를 지정할 수 있습니다.
index는 0 부터 시작합니다. 마이너스 index는 맨 마지막 요소부터 시작합니다.
예를들어 -1은 맨 마지막 요소를 의미합니다
왜 Array는 데이터를 순차적으로 저장할까?
실제 메모리 상에서 즉 물리적으로 데이터가 순차적으로 저장되기 때문입니다
데이터가 순차적으로 저장되기 때문에
- index가 존재하며
- Indexing : index를 사용해 특정 요소를 읽어 들이는 것이 가능하고
- Slicing : 요소의 특정 부분, 즉 n~m인덱스까지 따로 분리해 조작이 가능합니다
4) 단점
Array는 indexing이 가능하다는 장점도 있지만 그러한 특성 때문에 단점도 존재합니다
1. 데이터의 삭제와 추가
-
삭제 : 순차적으로 담겨있는 데이터 중 특정 위치에 있는 중간 요소가 삭제되는 경우 삭제된 요소부터 뒤에 있는 모든 요소를 데이터가 잘려나간만큼 앞으로 당겨줘야합니다. 가래떡을 중간에 자르면 뒤에 있는 떡을 끌어와야 하나의 가래떡 처럼 보이겠죠?
-
추가 : 추가도 마찬가지입니다. 특정 위치에 새롭게 요소가 추가되면 추가된 데이터만큼 그 뒤의 요소가 밀리게 됩니다.
-
결론 : Array에서의 데이터 삭제와 추가는 다른 자료구조에 비해 느릴 수 있습니다.
그렇기 때문에 Array는 데이터가 자주 삭제, 추가 되는 데이터를 담기에는 적절하지 않습니다.
2. Array 리사이징
배열은 메모리가 순차적으로 채워지기 때문에 처음 생성될 때 메모리를 미리 할당합니다. 이를 pre-allocation이라고 부릅니다.
하지만 요소가 할당한 메모리보다 이상으로 많아진다면 아래의 과정을 진행합니다
- 만약 100개의 메모리 공간이 다 차서 100개를 추가해야 하는경우
- 200개 크기의 메모리를 생성후 > 기존 100개를 복사하고 > 그 다음 101번 부터 데이터가 순차적으로 추가됩니다.....
그럼으로 배열의 resizing은 상대적으로 시간이 오래 걸리는 작업입니다.
그렇기 떄문에 Array는 사이즈 예측이 잘 안되는 데이터를 다루기엔 부적합니다.
5) 언제 사용하면 좋을까?
- 순차열적인 데이터를 저장할 때
- 다차원 데이터를 다룰때(Multi-demensional Array)
- 어떠한 특정 요소를 빠르게 읽어야 할 때 -> index를 통해 빠르게 읽을 수 있음
- 데이터의 사이즈가 급변하지 않는 데이터일 때
- 요소가 자주 삭제되거나 추가되지 않을 때
6) 면접 기출 - Data Structure #1. 자료구조 & Array
자료구조의 정의와 중요한 이유를 설명하세요.
자료 구조란 데이터의 편리함 접근과 조작을 가능하게 하는 데이터를 저장하거나 조직하는 방법입니다.
문맥과 데이터의 종류에 따라 적절한 자료 구조를 사용하는 것은 전체 개발 시스템에 큰 영향을 미칩니다.
그렇기 때문에 자료구조의 다양한 종류와 각각의 장점을 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 좋습니다.
Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명하세요.
Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 점입니다. 이렇게 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 조작이 가능하다는 것이 Array의 장점입니다.
반면에 이에 따른 단점도 존재하는데, 순차적으로 존재하는 데이터 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 뒤로 밀거나 당겨줘야 하는 단점이 있습니다.
이러한 경우 메모리 상에서 이루어지는 작업이 다른 자료구조에 비해 커지기 때문에 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에 적절하지 않습니다.
Array를 적용 시키면 좋을 데이터의 예를 구체적으로 들어주세요. (ex. 주식 차트) 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 서술해주세요.
Array를 적용시키면 좋은 예로 주식 차트가 있습니다.
주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식가격이 차례차례 저장되어야 하는 데이터입니다.
즉, 순서가 굉장히 중요한 데이터 이므로 Array를 사용하지 않는 경우, 즉 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어들이고 비교해야하는 번거로움이 발생합니다.
