자료구조 | 파이썬에 한정된 이야기 아님!
배열과 연결리스트 (Array & Linked List)
배열과 연결리스트는 둘 다 자료들을 저장하는 방식의 일종 (자료구조). 이 두 가지 기본적인 형태가 수많은 자료구조를 만드는 뼈대가 됨.
배열 (Array)
특정 자료형 (Data Type) 들이 메모리 공간상에서 연속적으로 이루어져 있는 자료구조.
(e.g. 위 예시는 int 를 담는 배열이, 메모리 공간상에서 연속적인 공간으로 연결되어 있음)
- 각각의 공간들은 0으로 시작하는 index 값 (0-4) 에 의해 즉각적으로 참조될 수 있음. 메모리 공간상에서 연속적으로 이루어져 있기 때문!
- 따라서, 배열은 자료에 대한 접근이 빠름. (index 값으로 바로 원하는 칸에 가서 자료를 확인할 수 있기 때문에, 딱 한 번의 접근만 필요)
- 배열은 크기를 변경할 수 없음. (e.g. 위와 같이 5개의 연속된 공간을 만들었다면, 자료를 최대 5개까지만 저장할 수 있으며, 만약 2개만 저장하고 싶다면 3개의 공간을 낭비하는 셈, 또한 사용자(Client) 가 5개 이상의 자료를 넣으려고 하면 문제가 발생함.)
정적 배열 (Static Array)과 동적 배열 (Dynamic Array)
배열은 크기를 변경할 수 없다는 한계를 해결한 배열 -> 동적 배열!
위에서 본 크기를 변경할 수 없는 배열 -> 정적 배열
배열은 두 종류가 존재함.
- 정적 배열: 위에서 본 배열의 개념 (크기를 변경할 수 없음)
- 동적 배열: 크기를 변경할 수 있는 배열
동적 배열 (Dynamic Array)
특정 자료형 (Data Type) 들이 메모리 공간상에서 연속적으로 이루어져 있는 자료구조인 기본적인 성질은 정적 배열과 동일하나,
배열의 크기를 조절할 수 있다는 차이가 있음.
즉, 프로그래밍에서 크기가 고정되지 않은 배열.
(동적) 배열의 크기를 바꾸는 방식 (2가지)
1. '한 개씩' 바꾸는 방식
- 배열의 크기를 하나만 늘리는 것.
- 저장공간을 최대한 절약할 수 있음.
- 다만, 시간 복잡도의 경우, 배열의 크기를 자주 바꾸게 될 경우, 계속해서 배열 크기를 바꿔주는 함수를 호출하게 되므로, 시간 복잡도가 증가함.
- 즉, 공간을 최대한으로 최적화할 수 있는 대신, 빈번한 자료의 입출력 시 배열의 크기가 자주 바뀜.
2. 배열을 'n 배'로 늘리는 방식
- 처음 동적 배열이 생성되었을 때, 일정한 크기를 갖는 배열 할당하고 원소 추가.
- 추가된 원소의 총 개수가 동적 배열이 가진 크기를 넘어가면 기존의 크기의 n배의 크기를 갖는 배열을 새로 할당
- 대개는 더블링 (Doubling) 이라 하여 2배씩 늘려주는데, 모든 언어가 항상 그런 것은 아니며 각 언어마다 늘려가는 비율은 상이함.
- 재할당 비율을 Growth Factor (재할당 비율; 성장 인자) 라고 함. 파이썬의 그로스 팩터는 초반에는 2배씩 늘려가지만, 전체적으로 1.125배로, 다른 언어에 비해서는 다소 조금만 늘려가는 형태로 구현됨.
- 참고) 자바의 ArrayList는 1.5배, C++의 std::vector, 루비는 2배
* 정적 배열과 동적 배열 비교 *
| 정적 배열 | 동적 배열 | |
| 장점 | 실행 속도가 빠름 | 원하는 만큼의 공간을 할당하고 사용 |
| 단점 | 크기가 고정, 유연하지 못함 정적인 배열의 메모리 낭비 |
처음 할당 이후에 재할당하는 문제 발생 (성능) |
| 공통점 | 특정 자료형 (Data Type) 들이 메모리 공간상에서 연속적으로 이루어져 있는 자료구조 | |
연결 리스트 (Linked List)
여러 개의 노드 (Node) 가 연결된 형태의 자료구조.
메모리 공간 상에서 각 노드들이 연속적으로 이루어져 있지 않고, 흩어져 있으며, 각각의 노드가 자신의 다음 노드의 위치를 알고 있음.
- 정적 배열과 달리, 크기가 고정되어 있지 않음.
- 각각의 원소들은 자기 자신 다음에, 어떤 원소인지만을 기억.
노드
- 정적 배열에서의 '한 칸', 각각의 노드들은 내부적으로 자신의 안에 포함할 자료 (Data)의 내용과, 다음 노드의 위치 정보 (Next, Link) 를 가지고 있음.
- 노드는 구현하는 사람이 마음대로 수정할 수 있음.
- 노드의 시작점은 head, 끝점은 tail 이라 부름.
- next 정보를 담은 부분은 4byte를 차지하는데, 만약 노드 개수가 많아진다면, 해당 부분의 메모리 차지도 무시하지 못함.
연결 리스트 종류
연결 리스트는 노드의 연결 방식에 따라 3가지 종류가 있음.
1. 단일 연결 리스트 (Simple linked list, Singly linked list)
- 한 가지 방향으로만 연결되어 있는 리스트 자료구조.
- 각 노드에 자료 공간 (Data) 과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킴.
2. 이중 연결 리스트 (Doubly linked list)
- 포인터 공간이 두 개 있고, 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킴.
3. 원형 연결 리스트 (Circular Linked list)
- 가장 첫 번째 노드 (head) 가 맨 마지막 노드와 연결되어 있는 형태
- head 노드에서 시작해, 다음 노드로 순차적으로 이동하면서 검색을 할 때, 마지막 노드에 도달하면 멈추지 않고 계속 순환.
4. 이중 원형 연결리스트 (Circular Doubly Linked List)
- 이중 연결리스트와 원형 연결리스트의 특성을 합친 개념
- 인접한 두 개의 노드는 서로의 위치를 알고 있으며, 맨 마지막 노드는 맨 앞의 노드인 head 노드와 인접하게 되어 서로의 위치를 알게 됨. 원형의 형태.
- head 에서 시작하여 시계 방향, 또는 시계 반대 방향으로 순환 가능.
- 따라서 기본 연결리스트에 비해 자료에 대한 접근성이 뛰어남.
연결리스트의 특징
- 각 노드들이 메모리 공간상에 어디에 위치하는지, 각각의 노드들만 알고 있음.
- 그리고 연결 리스트의 사용자는 제일 첫 번째 노드의 위치 (head) 만 알고 있음.
- 따라서, 자료에 접근하는데 배열에 비해 시간이 많이 걸림.
- 그러나, 노드를 추가하고, 제거하는 과정을 통해 최대 노드의 수를 언제든지 변경할 수 있기 때문에, 메모리 구조를 유동적으로 사용할 수 있음.
- 또한 사용자 (Client) 가 자료를 무분별하게 삽입, 삭제하더라도, 연결리스트가 자동으로 확장/축소 되기 때문에 문제가 되지 않음.
동적 배열과 연결리스트 비교
1. 자료 접근
| 배열 | 연결리스트 |
| 기본 주소 + (항목 크기 * index) 로 특정 인덱스에 위치한 항목에 접근하면 됨. 따라서 위치에 상관없이 한 번의 연산으로 항목을 찾아갈 수 있어 접근 속도가 빠름. | 첫 항목부터 순차적으로 접근해야 하므로 최대 O(n) 의 시간이 걸림. 즉, 자료 접근 속도가 느림. |
2. 자료 삽입/삭제
| 배열 | 연결리스트 |
| 배열 중간에 항목을 추가 및 삭제하려면, 기존 항목을 밀어내고 (혹은 삭제하고), 해당 공간을 비워야 함 (메꿔야 함). 따라서 최대 N 번의 항목 이동이 발생함. 상대적으로 느림. | 삽입 및 삭제가 간단함. 항목 생성 (혹은 삭제) 후, 포인터 값만 변경해 주면 됨. 상대적으로 빠름. |
정리
데이터 양이 많지만, 데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이루어질 경우 : 배열이 유리
데이터 양이 많지 않고, 데이터의 삽입/삭제가 빈번하게 이루어지는 경우 : 연결리스트가 유리
파이썬에서의 배열과 연결리스트
| 정적 배열 | 동적 배열 | 연결리스트 | |
| 파이썬 | X | O (리스트, 책 5장, 7장) | O 연결리스트 (책 8장) |
05장 리스트 발표 자료)
리스트는 배열과 연결 리스트의 장점을 모두 취한 듯한 형태를 가짐.
- 배열의 장점: 연속된 공간에 요소를 배치함 (7장 배열) => 정적 배열의 연속된 공간에 요소를 배치한다는 장점과
- 연결 리스트의 장점: 다양한 타입을 연결해 배치함 (8장 연결 리스트)=>연결리스트 처럼 다양한 타입의 데이터를 배치할 수 있다는 장점
- 연결 리스트: 각 노드가 데이터와 포인터를 가지고, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
파이썬에서의 단일 연결 리스트 구현
class Node:
def __init__(self, v, n = None):
self.value = v
self.next = n
class LinkedList:
def __init__(self, v):
self.head = Node(v)
def add(self, v):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(v)
def printlist(self):
if self.head is None:
print("value does not exist in linked list")
else:
cur = self.head
while cur is not None: # 기존 while cur.next is not None: 은 마지막 node의 cur.next가 None이기 때문에 마지막 node를 출력하지 못함. 따라서 코드 변경.
print(cur.value)
cur = cur.next
def remove(self, v):
if self.head.value == v:
self.head = self.head.next
else:
cur = self.head
while cur is not None:
if cur.value == v:
self.removeItem(v)
return
cur = cur.next
print('value does not exist in linked list')
def removeItem(self, v):
cur = self.head
while cur is not None:
if cur.next.value == v:
nextnode = cur.next.next
cur.next = nextnode
break
cur = cur.next # 기존 코드에는 없었는데, 다음 node로 넘어가기 위해서는 필요하다고 판단해서 넣음. 필요한 듯.
def search(self, v):
cur = self.head
index = 0
while cur is not None:
if cur.value == v:
print(index)
return index
else:
cur = cur.next
index += 1
print("value does not exist in linked list")
if __name__ == '__main__':
ll = LinkedList(3)
ll.add(4)
ll.add(5)
ll.printlist()
print('=======')
ll.remove(5)
ll.printlist()
print('=======')
ll.search(99)
08장 연결 리스트
| no | title | leedcode | status |
| 13 | 팰린드롬 연결 리스트 | 리트코드 234 | O |
| 14 | 두 정렬 리스트의 병합 | 리트코드 21 | O (02/18) |
| 15 | 역순 연결 리스트 | 리트코드 206 | O |
| 16 | 두 수의 덧셈 | 리트코드 2 | O (02/18) |
| 17 | 페어의 노드 스왑 | 리트코드 24 | |
| 18 | 홀짝 연결 리스트 | 리트코드 328 | |
| 19 | 역순 연결 리스트 2 | 리트코드 92 |
No.13 팰린드롬 연결 리스트
My Solution) Deque 이용 (사실 유튜브에서 봤음)
72ms, 24.3MB
시간 복잡도: O(n^2)
책 풀이
Solution 1) 리스트 변환
114ms, 24.3MB
Solution 2) 데크를 이용한 최적화
Solution 3) 런너를 이용한 우아한 풀이
68ms, 24.3MB
런너 기법
런너 (Runner) 는 연결리스트를 순회할 때, 2개의 포인터를 동시에 사용하는 기법.
- 한 포인터가 다른 포인터보다 앞서게 하여, 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있음.
- 2개의 포인터는 그림처럼 각각 빠른 런너 (Fast Runner), 느린 런너 (Slow Runner) 라고 부름.
- 대개 빠른 런너는 두 칸씩 건너뛰고, 느린 런너는 한 칸씩 이동.
- 이때, 빠른 런너가 연결 리스트 끝에 도달하면, 느린 런너는 정확히 연결 리스트의 중간 지점을 가리킴.
- 이와 같은 방식으로 중간 위치를 찾아내면, 값을 비교하거나, 뒤집기 시도 등 다양한 방법으로 활용 가능.
다중 할당 (Multiple Assignment)
파이썬에서 다중 할당은 2개 이상의 값을 2개 이상의 변수에 동시에 할당하는 것
다중 할당이 필요한 이유
rev, rev.next, slow = slow, rev, slow.next
위와 같은 코드가 있을 때, 다중 할당을 사용하지 않는다면?
rev = slow
rev.next = rev
slow = slow.next다음과 같이 사용할 수 있고, 이는 slow와 rev 가 동일한 참조가 되어, 문제가 됨.
(파이썬은 '객체' 이기 때문, 즉, = 연산자를 이용해 할당을 진행하게 되면, 값을 할당하는 것이 아니라, 불변 객체에 대한 참조를 할당함.)
런너를 이용한 우아한 풀이
- 연결리스트를 다른 자료형(리스트, deque)으로 변환하거나 편법을 사용하지 않고, 그 자리에서 바로 풀이함.
+추가) 연결리스트 뒤집기 (15번 문제에서 다룸)
No.14 두 정렬 리스트의 병합
My Solution 1) 코드가 좀 지저분..
36ms, 14.3MB
시간 복잡도: O(n)
- 리스트로 변환
- 두 리스트 결합 후, 정렬
- 다시 연결리스트로 변환
책 풀이
Solution 1) 재귀 구조로 연결 (이해 못했음..)
No.15 역순 연결 리스트
My Solution) (사실 유튜브에서 봤음..)
44ms, 15.6MB
시간 복잡도: O(n^2)
책 풀이
Solution 1) 재귀 구조로 뒤집기
36ms, 20.3MB
Solution 2) 반복 구조로 뒤집기
40ms, 15.5MB
No.16 두 수의 덧셈
My Solution) 풀이가 좀 지저분함..
72ms, 14.5MB
시간 복잡도: O(n)
- 리스트 변환
- string (문자열) 변환
- 숫자로 변환 (sum)
- string (문자열) 변환
- 리스트 변환
- 연결 리스트 변환
책 풀이
Solution 1) 자료형 변환
80ms, 14.4MB
Solution 2) 전가산기 구현
68ms, 14.2MB
'Python Basic > 파이썬 알고리즘 인터뷰' 카테고리의 다른 글
| [3부] 10장 데크, 우선순위 큐 (0) | 2021.02.22 |
|---|---|
| [3부] 09장 스택, 큐 (0) | 2021.02.16 |
| [3부] 07장 배열 (0) | 2021.02.11 |
| [2부] 06장 문자열 조작 (0) | 2021.02.09 |
| [2부] 05장 리스트, 딕셔너리 (0) | 2021.02.06 |
