one Book a Day

재귀 비교 import sys input = sys.stdin.readline def polling(n,start_x,start_y): half = n//2 if n==2: arr = [matrix[start_x][start_y], matrix[start_x+1][start_y], matrix[start_x][start_y+1], matrix[start_x+1][start_y+1]] arr.sort() return arr[-2] left_top = polling(half,start_x,start_y) right_top = polling(half,start_x+half,start_y) left_bottom = polling(half,start_x,start_y+half) right_bottom = poll..

슬라이딩 윈도우 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) left = 0 prefix_sum = 0 answer = -float('inf') for right in range(N): prefix_sum += arr[right] while right-left+1 >= M: answer = max(answer, prefix_sum) prefix_sum -= arr[left] left += 1 print(answer)

bfs로 동맹 나누고 heap에 동맹 크기 큰 순서(최대힙)로 넣어서 K넘지안는선에서 동맹. import sys input = sys.stdin.readline from collections import deque from heapq import heappop,heappush def bfs(i): queue = deque() queue.append(i) check[i] = i cnt = 1 while queue: cur = queue.popleft() for next in graph[cur]: if not check[next]: queue.append(next) check[next] = i cnt += 1 return cnt N, M = map(int, input().split()) graph = {i:..

이분탐색 + bfs import sys input = sys.stdin.readline from collections import deque def is_possible(limit): queue = deque() queue.append(s) visited = {i: False for i in range(1,N+1)} visited[s] = True while queue: cur_node = queue.popleft() if cur_node == e: return True for next_node, next_limit in graph[cur_node]: if not visited[next_node] and limit

내 풀이. dfs 조합으로 무식하게 풀었다. import sys input = sys.stdin.readline def dfs(s,cnt): global ans if cnt==3: ans += 1 return if cnt > 3: return for next in range(s+1,N+1): if not eat[next] and next not in donot_list: eat[next] = True for hate in ice_cream[next]: donot_list.append(hate) dfs(next, cnt + 1) eat[next] = False for hate in ice_cream[next]: donot_list.pop() N, M = map(int, input().split()) ice..

핵심은 power함수의 logN화. 1번 50점. import sys input = sys.stdin.readline N = int(input()) menus = sorted(map(int,input().split())) MOD = 1000000007 minus = 0 for i in range(N-1): for j in range(i+1,N): minus += ((menus[j] - menus[i])*(2**(j-i-1)))%MOD print(minus%MOD) 2번 50점 N = int(input()) menus = sorted(map(int,input().split())) MOD = 1000000007 minus = 0 plus = 0 for i in range(N): minus += (menus[..

1. 투포인터 후 큰 숫자부터 cnt 50점 통과 import sys input = sys.stdin.readline from collections import defaultdict N, M = map(int, input().split()) cards = list(map(int, input().split())) cards.append(cards[-1]) # 연속된 카드 묶기. 정확히 M개의 카드팩. 같은 종류 카드 두장되면 안됨. # 카드팩의 최대 길이. left = 0 pack_cnt = [] card_pack = defaultdict(int) for right in range(N+1): card_pack[cards[right]] += 1 if card_pack[cards[right]] > 1: pac..

그냥 바뀔때마다 센다음 작은거 +1 import sys input = sys.stdin.readline N = int(input()) s = input().rstrip() cnt = {'B': 0,'R': 0} cnt[s[0]] += 1 for i in range(1,N): if s[i] != s[i-1]: cnt[s[i]] += 1 print(min(cnt['B'],cnt['R'])+1)

이분탐색 짤때마다 느끼지만 조금 인덱싱 꼬일때가 있움.. l =(0.9)*f[m]: l = m + 1 else: r = m c += r-i-1 print(c)

마이너스로 증가하는 배열 import sys input = sys.stdin.readline from bisect import bisect_left N = int(input()) arr = list(map(int, input().split())) q = [] q.append(-arr[0]) for i in range(1,N): if -arr[i] > q[-1]: q.append(-arr[i]) else: q[bisect_left(q,-arr[i])] = -arr[i] print(N-len(q))