코딩 테스트 유형보기 1 - 자료구조

파이썬

---

기출 유형 

• 구현/시뮬레이션: 문제의 요구 사항을 주고 이를 구현하거나 시뮬레이션하도록 함
• 자료구조: 다양한 자료구조를 사용하여 문제 해결
• 그래프 이론: DFS/BFS와 관련된 알고리즘으로 문제 해결
• 완전 탐색(부르트 포스): 모든 경우를 탐색하여 해결

 

---

자료구조

---

스택(Stack)

• LIFO 구조
• 리스트로 구현
• 세로로 그려보면 문제풀때 이해하기 좋은거같음
• 리스트에서 다음 유형 둘다 만족할때 stack 쓰면될거같다.
  - 1. 좌측에서 왼쪽으로 나아가면서 풀때
  - 2. 순서는 안바꾸는 유형일때 
• Stack에 쌓고(append) 빼내고(pop) 하면서 풀기
• 대표문제
  1. 가장 큰수
  2. 후위 표기식 

큐(Queue)

• FIFO 구조
• collections.deque 로 구현
  - 파이썬 내부 queue라는 내부라이브러리도 존재하지만, 내부적으로는
  - collections.deque로 queue를 관리하기때문에 deque사용
  - 변수명 = deque() 로 선언
• Deque 는 덱이라 불리는 자료구조
  - 앞뒤 모두 데이터삽입/삭제 가능
  - 연결리스트로 구현되어 있어 삽입/삭제가 O(1)안에 끝나 매우 빠름
• 기억할 메소드
  - 1. append
  - 2. appendleft
  - 3. pop
  - 4. popleft

from collections import deque

queue = deque()

# 오른쪽에 데이터 추가
queue.append(3) # deque([3])
queue.append(5) # deque([3,5])
queue.append(7) # deque([3,5,7])

# 왼쪽에 데이터추가
queue.appendleft(2) # deque([2,3,5,7])
queue.appendleft(4) # deque([4,2,3,5,7])

# 오른쪽에서 데이터 삭제
queue.pop() # 7
queue.pop() # 5

# 왼쪽에서 데이터 삭제
queue.popleft() # 4
queue.popleft() # 2

queue # deque([3])

힙(Heap)

• 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조
• heapq 라이브러리로 구현
  - heap 은 리스트 기반으로 동작
  - heap 의 root 가 최소값을 가지는 min-heap 이 기본이다.
• 속성
  - A가 B의 부모노드이면, A의 Key값과 B의 Key값 사이에는 대소관계가 성립한다.
  - 형제 노드 사이에는 대소관계가 정해지지 않는다.
• 종류
  - 최대 힙 : 부모노드 Key값 > 자식노드 Key 값
  - 최소 힙 : 부모노드 Key값 < 자식노드 Key 값
• 기억할 메소드
  - 1. heapq.heappush(힙으로 사용될리스트,넣을값)
  - 2. heapq.heappop(힙으로 사용될리스트)
  - 3. heapq.heapify(힙으로 사용될 리스트) 
    - 리턴값없음 (리스트의 .sort() 느낌)
    - 처음 입력데이터를 받았을때, heapify로 정렬해주자
  - 4. heapq.nlargest(개수,힙) / heapq.nsmallest(개수,힙)

import heapq 

heap = []

# heap에 값 넣기 
# heapq.heappush(heap으로 사용될 리스트, 넣을 값)
heapq.heappush(heap,3)
heapq.heappush(heap,4)
heapq.heappush(heap,1)

print(heap) # result : [1, 4, 3] --> min-heap 기반

# heap에서 root 값 빼기
# heapq.heappop(heap으로 사용될 리스트)
print(heapq.heappop(heap)) #  result : 1
print(heap) # result : [3, 4]



# 주어진 리스트를 heap으로 만들기
# heapq.heapify(리스트)
list = [9, 8, 7, 6, 5, 4, 3, 2, 1]
heapq.heapify(list)

print(list) # result : [1, 2, 3, 6, 5, 4, 7, 8, 9]


# 가장 큰 / 작은 n개의 element 찾기
# heapq.nlargest(개수, 힙) 
# heapq.nsmallest(개수, 힙)
heap = [9, 8, 7, 6, 5, 4, 3, 2, 1]
heapq.heapify(heap)

print(heapq.nlargest(3,heap)) # result : [9, 8, 7]
print(heapq.nsmallest(3,heap)) # result : [1, 2, 3]

• Max-heap 구현하기
  - 튜플 형태로 값을 구성한다.
  - 튜플에서 좌측값(음수)을 기준으로 heap이 구성됨
  - 하나씩 뽑아내서 우측값을 리턴하면 max-heap 구현됨

import heapq

heap = []

for i in range(1,10):
	heapq.heappush(heap,(-i,i))
    
print(heap) 
# result : [(-9,9), (-8,8), (-6,6), (-7,7) .... (-1,1), (-4,4)]

for _ in range(9):
	print(heapq.heappop(heap)[1])

# reulst : 9 8 7 6 5 4 3 2 1