[CaseStudy] 알고리즘 2주차 수업 내용 정리

자료구조 Data Structure

 

1) 배열

배열은 삽입, 삭제가 느리고 조회가 빠르다

 

2) 연결리스트

배열과 연결리스트는 특징이 반대인데 파이썬에서는 배열의 기호로 [] (리스트)를 사용하여 헷갈릴 수가 있음.

연결리스트는 노드 단위로 존재. 삽입, 삭제가 빠르고 조회가 느림.

시간복잡도도 배열이랑 정반대의 양상인 것을 볼 수 있음.

파이썬은 연결리스트가 없어 직접 구현해야 한다고 함.

연결리스트는 데이터를 비연속적으로 저장하여 임의 접근이 불가능!!

 

3) 스택

LIFO / FILO 구조

배열은 스택의 연산을 포함하고 있다. => 배열 ) 스택

배열을 이용해서 스택을 구현. 한가지 주의점은 배열에서 스택을 구현할 때, pop()에 인덱스를 주어서 맨 위가 아닌 값을 삭제하게 되면 스택으로써의 기능(?)을 잃게되어 적절하지 않은 상황이 됨. 스택으로 쓸거면 중간 값들은 건드리면 안됨.

 

4) 큐

LILO / FIFO 구조

파이썬에서 큐를 쓰고 싶으면 import queue 대신 from collections import deque(덱)를 씀.

* 덱

Double-Ended QUEue의 줄임말로, '양면 큐'를 의미하여 앞뒤로 입출력이 다 가능함. 큐의 연산을 포함하고 있으므로 덱 ) 큐 가 되므로 큐를 쓰고 싶으면 덱을 쓰면 되는 것임.

큐와 같이 append를 쓰면 맨 뒤에 값이 추가되는데, 앞으로 넣고 싶으면 appendLeft를 쓰면 됨.(Left를 앞으로 봄)

pop도 마찬가지로 맨 뒤 값이 빠지고, popLeft를 쓰면 맨 앞에 값이 빠짐.

 

5) 우선순위 큐

노드에 어떤 것이든 담을 수 있다. 단, 노드 간에 우선순위가 존재해야 한다 = 정렬이 가능해야 한다.

내부적으로 힙(Heap)이라는 자료구조를 써서 구현됨. 힙은 완전이진트리 형태로 이루어져 있다. 트리에서 최상단 노드는 루트 노드로, 우선 순위가 가장 높다.

max-heap / min-heap에 따라 우선순위가 달라진다.

최대 힙 : 값이 클수록 우선 순위가 높다.

최소 힙 : 값이 작을수록 우선 순위가 높다.

-> 이에 따라서 값을 예를 들어 삽입을 하면 루트 노드쪽으로 가면서 위치를 바꿈(switch)

 

우선순위 큐에서 삽입, 삭제, 조회의 시간복잡도

파이썬에서 우선순위 큐를 쓰려면 import heapq를 사용!

heapq.heappush() -> 삽입

heapq.heappop() -> 삭제

파이썬에서 우선순위 큐 사용

 

가장 작은 값만 정해지고 나머진 섞여있는데, 큐에 넣었다가 뺴면 결국엔 작은 순서대로 정렬이 됨.

=> 힙정렬의 시간복잡도는 O(NlogN)이 됨. (2 * N * logN = 2NlogN, O(2NlogN) = O(NlogN).)

 

파이썬에서는 기본이 min-heap이다. (max-heap은 없음)

그럼 최대힙이 필요할 때는 ?!

넣기 전에 부호를 -로 바꿔서 넣고, 뺀 다음에 다시 바꿔주면 뒤집힘!

 

6) 맵

가장 큰 특징 : key-value 쌍으로 데이터를 저장

파이썬에서는 딕셔너리를 사용

시간복잡도는 전부 O(1)

해시를 이용해서 구현된 맵의 특징 :

맵에 들어간 원소는 순서가 보장되지 않음. => 데이터를 넣은 순서대로 이루어지지 않는다.

내부적으로 해시 테이블이라는 자료구조를 써서 구현됨. => O(1)이라도 데이터가 너무 많으면 느릴 수 있다.

 

파이썬에서는 {}를 사용 (딕셔너리)

 

7) 집합 Set

데이터들을 중복하지 않고 저장

파이썬에서는 기본 연산으로 교집합, 합집합, 차집합 등 지원

삽입, 삭제, 조회 전부 O(1)

맵처럼 내부가 hash로 되어 있어 특징도 맵이랑 똑같음. (해시의 특징이기 때문)