WEEK2 개발일지

 지난주부터 계속 알고리즘 문제를 풀고 있는데, 확실히 단기간에 할 수 없다는 것을 느꼈다. 개념 하나하나가 좀 헤비하기도 하고 아직 컴퓨터적인 사고에 완전히 적응하지 못했기 때문에 더 힘든 측면이 있는 것 같다. 처음에 정글 시작하기 전에는 공부에 집중이 안되어서 정글 들어가면 어떻게든 되겠지라는 생각으로 한 부분이 있었는데, 역시 공부는 오랫동안 꾸준히 해야하는 것 같다. 이번 주에는 집중도 잘 안되고 개념 이해도 잘 안 되고 해서 좀 힘들었는데, 이제 그냥 편하게 생각하고 정글 끝나고도 꾸준히 공부하겠다는 마음을 먹었다. 만약 내가 아는 것으로 코딩을 한다치면 하루에 16시간할 수도 있는데, 모르는 것을 받아들이는 것은 절대로 16시간 온전히 못한다.. 만약 누군가 그게 가능하다면 정말 대단한 사람이거나 아니면 집중을 제대로 안 한 것일 거다.(물론 나만 그럴 수도..) 그래서 알고리즘 주차가 끝나도 계속 공부를 하는 것이 좋다는 생각이 들었고, 일주일에 개념 2-3개 정도 익히고 관련 문제를 푸는 루틴을 생각하고는 있다.(과연 가능할지는 모르겠음) 

1. 스택, 큐, 최대 힙의 정의

1. 스택 : 후입선출 자료 구조. 가장 나중에 저장한 함수 또는 값이 다음 실행에서 가장 먼저 실행될 수 있는 후보군이 되는 경우에 사용. 예를 들어 재귀함수의 경우 기저 조건이 실행되면 이전의 최근 재귀함수가 실행이 된다.

 

2. 큐 : 선입선출 자료 구조. 저장된 순서대로 실행되는 경우에 사용. 예를 들어 프로세스의 경우, 큐에 프로세스가 쌓이고 대기 상태가 풀려날 때 가장 먼저 등록된 프로세스부터 실행.

 

3. 최대 힙: 이진 트리로 구현된 자료 구조로 리스트의 '인덱스'를 이용하여 값을 순차적으로 저장. 리스트의 첫 번째 요소가 최댓값, 마지막 요소가 최솟값으로 최소 최대값을 자주 찾아야할 때 유용한 자료구조이다. 특히 우선순위 큐를 구현할 때 많이 사용되는데, 일반적인 리스트에 우선순위 요소를 넣어 정렬은 n이 걸리지만(정렬된 것을 가정했을 때)힙에 요소를 넣어서 정렬이 되는 시간은 logn이다.

2. 사용 사례 비교

스택	큐	최대 힙
DFS, 재귀함수, 백트래킹, 수식 계산, 괄호 유효성 계산	BFS, 실시간 처리, 프로세스, 캐시 구현	우선순위 큐, 힙 정렬, 최소값/ 최댓값을 자주 추출하는 경우

3. 구현 방식

1. 큐

스택의 경우 알고리즘 문제를 풀 때 리스트를 사용해도 되는데, 대부분 append pop()같이 상수시간이 걸리는 연산밖에 하지 않기 때문이다. 하지만 큐나 힙을 사용해야하는 경우 모듈을 사용.

from collections import deque
d = deque([])
d.append(x) ##deque 오른쪽 끝에 요소 추가.. 리스트랑 동일
d.appendleft(x) ##deque 왼쪽 끝에 요소 추가.. 리스트는 O(n), deque는 O(1)
d.pop() ##deque 오른쪽 끝에서 요소 제거 및 반환
d.popleft() ##deque 왼쪽 끝에서 요소 제거 및 반환
d.extend(iterable) ##deque 오른쪽 끝에 객체 요소 추가
d.extendleft(iterable) ##deque 왼쪽에 객체 요소 순서를 뒤집어서 추가
d.rotate(x) ##deque 요소들을 x만큼 회전, 양수면 오른쪽 음수면 왼쪽
d.clear() ##deque 요소 전부 제거
d.remove(x) ##처음으로 발견되는 x 제거

2. 힙

import heapq

##최소 힙
heap = []
heapq.heappush(heap, x) ## heap리스트에 x를 최소 힙 구조로 푸시
heapq.heappop(heap) ## heap리스트의 최소값 제거 및 반환
heapq.heapify(list) ## list를 최소 힙으로 변환
heapq.heappushpop(heap,x) ## 힙에 새로운 요소 추가 후 가장 작은 요소 제거 및 반환
heapq.nlargest(x, heap) ## 힙에서 가장 큰 x개 요소 반환
heapq.nsmallest(x, heap) ## 힙에서 가장 작은 x개 요소 반환

##최대 힙
max_heap = []
heapq.heappush(max_heap, -x)
max_value = -heapq.heappop(max_heap)