DataScience
[자료구조] 배열(Array)과 리스트(List) 본문
자료구조 : 데이터를 효율적으로 저장, 접근, 수정하기 위한 그릇을 뜻하며, 즉 데이터를 표현하고 관리하고 처리하기 위한 구조라로 생각하면 된다. 자료구조에는 다음 그림과 같이 두 가지 유형이 있다.
1. Linear data structure : 원소들이 메모리 공간 측면에서 선형적으로 연결되있는 경우, 즉 순서가 있는 데이터의 모임
2. Non-linear data structure : 원소들이 순서 개념으로 정돈되어 있지 않은 경우, 즉 비연속적으로 연결되 있는 데이터의 모임
● 배열[Array] : 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
배열이란 연관된 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 방법입니다. 특히 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장이 가능하다. 배열의 예를 들면 친구들의 서있는 현재 단계 수를 아는 것만으로 친구들의 위치를 정확하게 접근이 가능하다.
위의 그림에서 1은 Value에 저장된 값이며, 숫자 1 아래의 (0)은 1이라는 값을 식별하는 Index를 말한다. 이 Index를 사용해서 1이라는 값을 가져올수 있다.
1. 배열의 특징
1. 인덱스를 사용하여 빠르게 조회 후 값에 바로 접근이 가능하다.
2. 구조가 간단하고 길이가 고정적으로 생성된다.
2. 배열의 한계
1. 인덱스에 따라서 값을 유지하기 때문에 엘리먼트가 삭제돼도 빈자리가 남게 되는 문제가 발생 -> 메모리 낭비 발생
2. 배열의 크기를 선언 할수 있으나, 선언하면 수정이 불가능하다.
3. 새로운 값을 삽입하거나 특정 인덱스에 있는 값 삭제가 어렵다.
→ 삽입 / 삭제의 경우 인덱스 주변에 있는 값을 이동시키는 과정 필요하다.
3. 배열 관련 알고리즘
구간 합
[자료구조] 구간 합 (prefix sum)
● 구간 합(Prefix sum) : 합 배열을 이용하여 시간 복잡도를 줄이기 위한 목적 n개의 수들이 존재하고 0의 인덱스의 위치부터 n번째 인덱스까지의 합을 구한다고 했을때 다음과 같이 두가지 방법이
sjm2449.tistory.com
● 리스트[List] : 인덱스를 버리고 빈틈없이 데이터를 적재하는 형태의 자료구조
인덱스를 이용해서 데이터를 가져오려면 데이터에 대한 인덱스의 값이 고정되어야 했기에 엘리먼트가 삭제되면 빈자리가 남게되어 이것은 메모리의 낭비가 발생되는데 이것을 방지하기 위해 인덱스라는 장점을 버린 대신 값과 포인터를 묶은 노드라는 것을 포인터로 연결하여 빈틈없는 데이터의 적재의 형태를 말한다.
1. 리스트의 특징
1. 배열에서 유일한 식별자였던 인덱스는 리스트에선 몇 번째 데이터인가 정도의 의미를 가진다.
2. 인덱스가 없기때문에 값에 접근하려면 Head 포인터부터 순서대로 접근해야한다.
3. 데이터를 삽입하거나 삭제할때 포인터만 변경해주기 때문에 효율적이다.
4. 빈 Element는 허용되지 않지만, 중복된 데이터는 허용한다.
2. 리스트의 한계
1. Head부터 접근하는 방식때문에 값에 접근하는 속도가 느리다.
→ 인덱스가 없기에 특정 데이터를 검색하는데 무조건 O(n)의 시간이 걸린다.
2. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.
3. 링크드 리스트의 종류 : 링크드 리스트는 데이터 관리가 쉽기 때문에 파이썬 이외의 경우에 사용
4. 리스트 관련 알고리즘
투 포인터
슬라이싱 윈도우
※ 파이썬의 리스트는 리스트의 특징 뿐만 아니라 배열의 특징을 가지도록 구현되었다.
참고서적
'Data science > algorithm' 카테고리의 다른 글
| [그래프] 그래프의 표현 (1) | 2022.10.23 |
|---|---|
| [정렬] 빠른 정렬 (병합, 퀵) 알고리즘 (0) | 2022.10.17 |
| [정렬] 단순 정렬 (버블, 선택, 삽입) 알고리즘 (0) | 2022.10.16 |
| [그래프 탐색] 깊이 우선 탐색[DFS]와 너비 우선 탐색[BFS] 알고리즘 (0) | 2022.10.16 |
| [자료구조] 스택(Stack)과 큐(Queue) (0) | 2022.10.10 |
