one Book a Day

사실 연결그래프의 최소갯수는 항상 n-1이다.. 최대는 n(n-1) import sys input = sys.stdin.rewadline def DFS(v,cnt): for next_node in graph[v]: if not visited[next_node]: visited[next_node] = True cnt = DFS(next_node,cnt+1) return cnt for test in range(1, int(input())+1): N, M = map(int, input().split()) graph = {i:[] for i in range(1, N+1)} visited = {i:False for i in range(1, N+1)} for _ in range(M): a, b = map(int,i..

2차원 배열회전 문제. 이문제는 따로 notebook배열을 늘려줄 필요가 없어서 그나마 설계하기 쉬웠다. 저번 문제보다 훨씬.. 90도 회전 외워두니까 진짜 넘 편한듯. [k[::-1] for k in zip(*list)] import sys input = sys.stdin.readline # 검사하기 def is_matching(x, y, sticker, R, C): for i in range(x, x+R): for j in range(y, y+C): if notebook[i][j] and sticker[i-x][j-y]: return False for i in range(x, x+R): for j in range(y, y+C): if sticker[i-x][j-y]: notebook[i][j]=1 r..

완전 이진트리. 어차피 배열 인덱스랑 같은 노드값 가지므로 배열 번호대로 루트까지 타고 올라가는 방법을 사용. import sys input = sys.stdin.readline N, Q = map(int,input().split()) owned = [False for _ in range(N+1)] for _ in range(Q): dest = int(input()) tmp = dest flag = 0 while tmp != 1: if owned[tmp]: flag = 1 first_owned = tmp if tmp%2: tmp -= 1 tmp //= 2 if flag: print(first_owned) else: owned[dest] = True print(0)

슬라이딩 윈도우. dp의 방식을 차용하되 2칸만 유지해 메모리 효율을 최고로 끌어올림. import sys input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] max_sum = [[0,0,0],[0,0,0]] min_sum = [[0,0,0],[0,0,0]] # 슬라이딩 윈도우 N까지 미끄러짐. // dp를 같이 쓰는데 dp를 모두 저장하는 것이 아니라 전의 값과 현재 계산할 칸만 남겨둠. for i in range(0,N): max_sum[1][0] = max(max_sum[0][1], max_sum[0][0]) + arr[i][0] max_sum[1][1] = max(ma..

원형 큐이므로 배열 두개 이어주고 순회. for 문을 돌려 right는 따로 컨트롤x 길이가 k가 되면 최댓값 갱신, left삭제, left idx 증가를 반복.ㄴ import sys input = sys.stdin.readline from collections import defaultdict N, d, k, c = map(int,input().split()) sushi = [] for _ in range(N): sushi.append(int(input())) sushi.extend(sushi) left = 0 right = 0 max_cnt = 0 eat = defaultdict(int) eat[c] += 1 for right in range(len(sushi)): eat[sushi[right]] +..

히스토그램과 똑같은 문제 입력방식만 다르다. import sys read=sys.stdin.readline def maxSize(): max_size = 0 #최대 넓이 저장 stack = [] for now in range(N): #왼쪽으로 이어질 수 있는 index left = now while stack and stack[-1][0] >= heights[now]: #pop되었다는 것은 추가 될 직사각형보다 높이가 높다는 의미이다. #따라서 추가될 직사각형은 pop되는 직사각형의 point값까지 넓어질 수 있다! #pop된 사각형의 point값으로 left를 업데이트 h, left = stack.pop() tmp_size = h * (now-left) max_size = max(max_size, tm..

stack을 이용해 뒤로 돌아가며 가능한 높이를 모두 구해주는 방법이다. 일단 나보다 낮은애가 나오면 내 뒤로 돌아보면서 낮은애들 높이에 나로부터의 가로거리를 곱한 넓이를 전부 비교해 최댓값을 가져간다. 나보다 낮은 곳이 나오면 다시 탐색한다. import sys input=sys.stdin.readline n=int(input()) graph=[] result=0 left=0 a=0 for _ in range(n): graph.append(int(input())) graph.append(0) stack=[(0,graph[0])] # cursor는 오른쪽으로 탐색할수록 커짐. stack에 cursor위치와 그곳의 높이를 집어넣음. # stack의 제일 위층 의 높이(전층의 높이)가 이번 층의 높이보다 크..

백트래킹을 걸 수 없는 탐색 ( target이 움직여서 중복방문을 막을 수 없을 시)시 사이클도는 구간을 찾아 사이클마다 각 지점에 대한 체크만 해주고 탐색은 더 진행하지 않는 방법을 사용. 중복 구간 탐색을 막고 사이클은 돌며 target이 오나 안오나 감시할 수 있다. import sys input = sys.stdin.readline from collections import deque def BFS(N,K): odd_even_visited = [[False]*500001 for _ in range(2)] queue = deque() queue.append([N,K,0,0]) cur_sister = K odd_even_visited[0][N] = True while queue: cur_node,cu..

여러모로 데이터 넘기는데는 BFS가 최고라는 생각.. 재귀로 데이터넘기는건 아직 힘들다.. 다행히 오늘은 원큐에 성공 import sys input = sys.stdin.readline from collections import deque from math import floor def search_unions(x,y): queue = deque() nation_cnt=1 sum_population = maps[x][y] queue.append([x,y]) finish_union[x][y] = union_num while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

평범한 BFS 그 양배추밭이랑 똑같은 문제다. import sys input = sys.stdin.readline from collections import deque dx = [0,0,1,-1] dy = [1,-1,0,0] def BFS(i,j): queue = deque() queue.append([i,j]) while queue: x,y = queue.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] if 0