- 입력 받을 때
read = sys.stdin.readline
해두면 매번 sys.stdin.readline() 쓸 필요 없이, read() 만 써주면 되니까 편하고 빠르다.
- 이진탐색
정렬된 배열이 들어왔을 때, 반씩 나눠서 왼쪽, 오른쪽 중 해당하는 범위만 검사하여 원하는 value를 찾는 방법이다.
선형탐색은 시간복잡도 O(n), 이진탐색은 O(logn) 이다. 완전 빠르다.
이진탐색 수행 시, bisect 라이브러리 이용할 수 있다.
iterable에서 value값이 들어갈 자리의 인덱스값을 반환한다.
bisect_left(iterable, value): 왼쪽 반환 (리스트에 동일값이 존재하면 해당 값의 이전 인덱스를 반환)bisect_right(iterable, value): 오른쪽 반환 (리스트에 동일값이 존재하면 해당 값의 다음 인덱스를 반환)
-> 응용 : 특정 값이 리스트 안에 몇 개 있는지 찾을 수 있다. (bisect_right - bisect_left)
이진탐색에서 if문 부등호 정하기가 어려웠다. 어디에 등호를 붙여야하는지, answer값은 언제 갱신해야하는지 이해를 못해 애를 먹었다.
공부하면서 조금씩 이해하고 있는데, 일단 조건을 만족하는 쪽(더 넉넉한 쪽?)에 등호를 붙이고, answer값을 갱신해주면 된다.
- 스택 (LIFO)
파이썬에서 스택은 list를 쓰면 된다. append, pop 다 똑같다. push는 ㄴㄴ
- 큐 (FIFO)
파이썬에서 큐도 list를 쓸 수 있다.
pop 할 때, pop(0)으로 가장 첫번째 원소를 꺼내준다.
반대 방향에서 큐를 사용하고 싶으면, push할 때, insert(0, value) 해주고, pop은 그냥 pop()하면 된다.
하지만!
pop(0), insert(0, value) 는 시간복잡도가 O(n)라서 느리고 별로다..
collections의 deque를 사용하자!
- deque (double-ended queue)
양방향에서 원소 추가, 제거 가능
append, pop 은 동일하다.
appendleft(x), popleft() 메소드가 있어서 바로 접근 가능하다.
append(x), popleft()
appendleft(x), pop()
두 조합으로 사용하면 된다.
- 힙
파이썬 heapq 모듈 이용한다.
기본적으로 최소 힙이 제공된다. (루트 노드가 최솟값)
(우선순위 큐가 힙?)
최대 힙 이용하기
- 방법 1
import heapq
nums = [4, 1, 7, 3, 8, 5]
heap = []
for num in nums:
heapq.heappush(heap, (-num, num)) # (우선 순위, 값)
while heap:
print(heapq.heappop(heap)[1]) # index 1(우선순위, 값) 으로 된 튜플을 heappush의 값으로 넣어주면 튜플[0] 기준으로 최소 힙이 만들어진다. (-8,-7,-6 …) 이런 식으로
출력할 때는 튜플[1]을 출력하면 내림차순으로 출력 가능
- 방법2
for num in nums:
heapq.heappush(heap, -num) # -값
while heap:
print(-heapq.heappop(heap)) # 출력할 때, 마이너스굳이 튜플 안써도 된다. 이게 훨씬 빠름.
넣을 때 마이너스 붙여서 넣고, 꺼낼 때 마이너스 붙여서 꺼냄
- 투 포인터
백준 2470번 두 용액 문제풀이에 사용되는 알고리즘이다.
https://www.acmicpc.net/problem/2470
이진탐색인줄 알고 어디에 이진탐색을 적용해야하나 고민을 많이 했는데, 투 포인터라는 새로운 알고리즘을 적용하는 문제였다.
양쪽 끝을 start, end로 잡고 시작하는 것은 이진탐색과 같으나, mid를 구하지 않고 조건을 만족할 때까지 start나 end를 조정해가며 최적해를 찾는다는 점이 다르다.
본 문제에서는 합이 음수면 start += 1, 합이 양수면 end -= 1을 해주면서 값을 점점 양쪽에서 조이면서 최적해를 찾았다.
