[알고리즘 전략] python 기본 자료구조 정리

** [한권으로 합격하는 취업 코딩테스트] 책을 참고해 작성했습니다.

** 주의점, 기억해야할 것을 위주로 작성합니다. 

 

배열

- 선언 시 주의점 

a1 = [[0] * 5] * 3
a1[1][1] = 99 # [1][1] 외에 다른 곳의 값도 99로 출력됨. 

a2 = [[0] * 5 for _ in range(3)]
a2[1][1] = 99 # [1][1] 만 변경됨.

 

- 삽입/삭제는 적고 조회가 잦다 => 배열 

- 삽입/삭제가 많고 조회가 적다 => 연결리스트 

** 대표문제 

- 요세푸스 문제 0

 

 

스택/큐 

 

스택 

- LIFO Last Input First Output 

- 삽입/삭제: O(N)

- 배열 사용, append(), pop() 

- 스택 활용 문제: 입력을 순차적으로 살펴보면서 각각의 데이터를 스택에 언제 넣고 뺄지 결정하는 게 핵심 포인트

** 대표 문제

- 괄호 

 

큐 

- FIFO First Input First Output 데이터를 넣은 순서 그대로 빼게 된다.

- BFS에서 사용되는 자료구조 

- 삽입/삭제: O(N) 

- deque 모듈 사용: 앞뒤 구분 없이 어느 쪽으로든 넣고 뺄 수 있다. 

from collections import deque
dq = deque()
dq.append(123) 
while len(dq):
	print(dq.popleft())

** 대표문제 

- 카드2

 

우선순위 큐/ 최소힙과 최대힙

우선순위 큐 

- 힙(heap)이라는 완전이진트리로 되어있다. 

- 루트 노드 = 데이터 중 가장 큰 값(최대힙) 또는 가장 작은 값(최소힙)

- 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 

- 삽입/삭제 O(logN) 

- heapq 모듈 사용 

import heapq as hq

h = [] 
hq.heappush(h, 123) 
hq.heappush(h, 234)
while len(h): 
	print(hq.heappop(h))

 

최대힙과 최소힙 

- heapq 모듈은 default로 최소힙을 제공한다. 

- 최대힙 구현: 데이터를 넣기 전에 전부 부호를 반대로 바꿔서 넣으면 순서가 뒤집혀 저장되므로 최대힙처럼 사용할 수 있다. pop한 값은 다시 부호를 바꾸면 원래의 값을 얻는다. 

- 우선순위 큐에 넣는 자료형이 단일 값이 아닌 선형 자료구조(튜플)라면 기본적으로는 맨 앞의 요소부터 우선적으로 살펴보며 정렬한다. 

** 대표문제 

- 절댓값 힙 

 

 

맵(Map) / 집합(Set)

맵(Map) 

- key, value로 데이터를 저장한다. 

- key는 중복 불가 

- 파이썬: 딕셔너리로 구현 

** 대표문제 

- 베스트 셀러

 

집합(Set)

- 중복이 없다. 

- 내부 구조가 트리로 되어있고, 데이터가 정렬되어 저장된다. 

- 합집합, 교집합 가능 (단, 빼기 연산 불가) 

** 대표문제 

- https://www.acmicpc.net/problem/7785