one Book a Day

슬라이딩 윈도우. 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]] +..

투포인터는 연속 구간의 길이가 가변적으로 변할 때 O(2*N)으로 풀도록 도와줌. 슬라이딩 윈도우는 구간의 크기가 고정일때. 둘다 start, end 포인트 사용(슬라이딩 윈도우는 end가 그냥 배열 포인터긴 함.) 하지만 둘다 연속적인 값들을 이용해 풀어나가는 한계가 있음. 기존 배열의 구간합 구하는 코드 배열 크기에서 구간의 길이k만큼의 모든 배열의 합을 순회하며 계산. import sys def max_sub_array(arr, k): maxsum = -sys.maxsize - 1 arraysize = len(arr) for i in range(arraysize - k + 1): current_sum = 0 for j in range(i, i + k): current_sum += arr[j] max..

히스토그램과 똑같은 문제 입력방식만 다르다. 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

666을 찾아 떠나는 여행. 처음엔 666을 삽입하자는 생각이었으나 자릿수가 늘어날 수록 규칙이 계속 바뀌기 때문에 불가. 완전탐색으로 진행하였다 import sys input = sys.stdin.readline n = int(input()) cnt = 0 i=666 while cnt

무너가 탐색을 해야할 것 같지만 사실 치킨집을 골라 모든 집까지의 거리들 중 최솟값들만 더해서 거리합을 갱신해준다. import sys input = sys.stdin.readline from itertools import combinations # 맵크기(N), 치킨집 최대 선택가능개수(M) N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] # 빈칸(0), 집(1), 치킨집(2) // 그래프 그리기. house = [] chicken = [] for i in range(N): for j in range(N): if board[i][j] == 1: house.append((i, j)) el..