Teddy Data Blog

collections이라는 라이브러리에서는 deque와 Counter가 많이 쓰인다.dequedeque와 list의 차이점은 시간 복잡도이다.list의 경우는 앞쪽에 있는 값을 처리할 때 리스트 개수에 따라 시간이 많이 소요된다.앞쪽에 값을 추가/제거 할 경우 시간 복잡도는 O(N),뒤쪽에 값을 추가/제거 할 경우 시간 복잡도는 O(1)이 걸린다. deque는 슬라이싱, 인덱싱이 불가능하지만 데이터를 추가/삭제할 때는 매우 효과적이다.- popleft() : 리스트의 첫 번째 값을 제거- pop() : 리스트의 마지막 값을 제거- appendleft() : 리스트의 맨 앞에 값을 추가- append() : 리스트의 마지막에 값을 추가from collections import dequedata = dequ..

문제 링크https://www.acmicpc.net/problem/17425 17425번: 약수의 합두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더www.acmicpc.net 처음에는 감을 잡을 수 없었으나 차근차근 패턴을 파악해보았다.f(6)은 6의 약수의 합 [1, 2, 3, 6], 답 12f(7)은 7의 약수의 합 [1, 7], 답 8 g(6)은 f(1)+f(2)+f(3)+f(4)+f(5)+f(6)을 뜻한다.1의 약수 12의 약수 1 23의 약수 1 34의 약수 1 2 45의 약수 1 56의 약수 1 2..

문제 링크https://www.acmicpc.net/problem/2530 2530번: 인공지능 시계첫째 줄에 종료되는 시각의 시, 분, 초을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수이며, 분, 초는 0부터 59까지의 정수이다. 디지털 시계는 23시 59분 59초에서 1초가 지나면 0시 0www.acmicpc.net첫 코드 (오류)import sysA, B, C = map(int, sys.stdin.readline().split())D = int(sys.stdin.readline())min_ = D//60sec_ = D%60B = B+min_C = C+sec_if C >= 60: C -= 60 B += 1 if B >= 60: B = B%60 A = A..

bisect- 이진 탐색을 구현할 수 있도록 파이썬에서 제공하는 라이브러리- 정렬된 배열에서 특정한 원소를 찾을 때 효과적- bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드- bisect_right(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드from bisect import bisect_left, bisect_righta = [1,2,4,4,8]x = 4print(bisect_left(a, x))print(bisect_right(a, x))## 2## 4 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수 구할 때from bisect import bisect_lef..

heapq- heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용- PriorityQueue 라이브러리도 사용할 수 있지만, heapq가 보통 빠르다고 함- heapq.heappush(): 힙에 원소 삽입- heapq.heappop(): 힙에 원소 추출- 파이썬의 힙은 최소 힙으로 구성되어 있어 원소를 힙에 전부 넣어다가 뺴는 것으로도 시간 복잡도 O(NlogN)에 오름차순 정렬됨 최소 힙 구현import heapqdef heapsort(iterable): h = [] # 힙 result = [] # 모든 원소를 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h, val..