알고리즘

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 처음에 리스트 말고 collections의 deque를 사용해서 문제를 풀려고 했는데 리스트와는 다르게 deque에서는 슬라이싱하는 방법을 찾지 못해서 다시 리스트로 풀게 되었다. 간단하게 입력받은 문자를 슬라이싱해서 하나씩 스택에 넣어주면서 스택에 4개이상 쌓였을 때, 4개를 빼고 해당 문자가 PPAP이면 P를 다시 스택에 넣어주고 마지막에 스택에 남은 문자가 P이거나 P P A P가 남아있으면 PPAP 문자열이고 나머지 문자는 전부 NP 이다...

https://www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 이 문제는 분할 정복으로 풀어야 하는 문제 중 하나이다. 처음 접근을 할때 10**9의 문자열 길이까지 가능하기 때문에 문자열을 직접 만들면서 실행하면 시간초과나 메모리 초과가 날 것을 알았지만 그래도 한번 해봤었고 역시나 메모리 초과가 나왔다. 메모리 초과를 해결하기 위해서는 각각 단계를 분할해서 문제를 해결해야 한다. moo는 기본적으로 - S(n-1) + ..

🕹️ 가운데를 말해요 from sys import stdin as s import heapq leftHeap = [] rightHeap = [] s= open('input.txt','rt') n = int(s.readline()) arr = list(map(int,s.readlines())) for i in range(n): if len(leftHeap) > len(rightHeap): heapq.heappush(rightHeap,arr[i]) else : heapq.heappush(leftHeap,-arr[i]) if len(leftHeap) != 0 and len(rightHeap) != 0 and -leftHeap[0] > rightHeap[0] : left = -hea..

🗒️ 우선순위 큐 - 큐는 먼저 들어온 데이터가 먼저 처리되는 자료구조이지만, 우선 순위 큐는 우선 순위가 높은 데이터부터 처리하는 자료구조이다. 배열, 연결리스트, 힙으로 모두 구현할 수 있지만 보통 시간복잡도가 적은 힙을 사용한다. 💡 우선순위큐 from queue import PriorityQueue q = PriorityQueue() # 삽입 q.put(3) q.put(2) q.put(1) # 삽입시 우선순위 지정 q.put((5,"banana")) q.put((1,"apple")) q.put((3,"FINE")) # 반환 print(q.get()) # 1 print(q.get()) # 2 print(q.get()) # 3 # 사이즈 print(q.qsize()) # 튜플 값만 print(q.ge..

18111번 _ 마인크래프트 문제 N, M ,B = list(map(int,s.readline().split())) array = [list(map(int,s.readline().split())) for _ in range(N)] listMax = max(map(max,array)) listMin = min(map(min,array)) result = int(1e9) resultH = 0 for k in range(listMin,listMax+1): ans = 0 block = B for i in range(N): for j in range(M): if array[i][j] > k : ans +=(array[i][j] - k) * 2 block += 1 else: ans +=abs(array[i][j] ..