one Book a Day

1차시 DFS 시간초과 import sys input = sys.stdin.readline def DFS(depth,start,sum_t): if depth==3: if arr[start]==sum_t: return True return for pre_num in arr[:start]: if DFS(depth+1,start,sum_t+pre_num): return True N = int(input()) arr = list(map(int,input().split())) # 앞에있는 수 3개의 합. DFS(중복가능) depth 3까지. cnt=0 for i in range(1,N): if DFS(0,i,0): cnt+=1 print(cnt) 2차시 누적합 메모리초과 import sys input = sys...

백준님의 블로그내용으로 공부한 것을 정리한 포스팅입니다. 세그먼트 트리.(Segment Tree) Intro 구간 l,r 이 주어졋을 때 A[l]~A[r]까지의 합 i 번재 수를 v로 바꾸기 A[i] = v 수행해야 하는 연산은 최대 M번. 1번연산하는데 O(N) 2번연산 O(1) 총 시간복잡고 O(MN) 2번 연산이 없다고 가정해봅시다. 수를 바꾸는 경우가 없기 때문에 합도 변하지 않습니다. 따라서 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀 수 있습니다. S[i] = A[1]+...+A[i] i~j까지 합은 S[j]-S[i-1] S[0] = A[0] for i in range(N): S[i] = S[i-1] + A[i] 여기서 2번연산을 하려면 수가 바뀔때마다 S를 변경해줘야 합니다. 가장 ..

전형적인 0-1 냅색. dp로 풀었습니다. import sys input = sys.stdin.readline N,K = map(int,input().split()) dp =[[0]*(N+1) for _ in range(K+1)] times=[] grades=[] for _ in range(K): I,T = map(int,input().split()) times.append(T) grades.append(I) for class_no in range(1,K+1): for now_time in range(1,N+1): if times[class_no-1] > now_time: dp[class_no][now_time] = dp[class_no-1][now_time] else: # 지금시간에서 추가하는 과목의 ..

비트마스트 bfs. 외판원순회처럼dfs로 해보려다가 중대한 문제점을 발견했다. 내가 dfs return값, 메모이제이션 설계를 잘 못한다는 것이었다.. 특히 분기가 많아질수록.. 다음번엔 그거 보완해야겠다. 큰 깨달음을 얻은 문제. from collections import deque import sys input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def bfs(): while q: x, y, key, cnt = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

배열의 길이가 줄어듦에 따라 idx도 조정해줘야한다. import sys input = sys.stdin.readline N, K = map(int, input().split()) nums = [i for i in range(1, N + 1)] result = [] idx = 0 for _ in range(N): idx += K-1 if len(nums)

dp.. 그놈의 정사각형 import sys input = sys.stdin.readline N = int(input()) maps = [list(map(int,input().split())) for _ in range(N)] dp = [[0]*(N+1) for _ in range(N+1)] for i in range(1,N+1): for j in range(1,N+1): dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+maps[i-1][j-1] max_profit=dp[1][1] for k in range(N): for i in range(1,N-k+1): for j in range(1,N-k+1): cur_profit = dp[i+k][j+k]-dp[i-1][j+k]..

또상정렬. heap써서 완전한 위상정렬은 아니고 그냥 앞숫자부터 빼주는위상정렬. import sys input = sys.stdin.readline from heapq import heappop,heappush def topological_sort(): heap=[] for i in range(1,N+1): if not level[i]: heappush(heap,i) while heap: cur_solve = heappop(heap) answer.append(cur_solve) for next_solve in ordered[cur_solve]: level[next_solve] -=1 if not level[next_solve]: heappush(heap,next_solve) # 문제는 모두 풀어야한다. ..

코드는 한방에 짰는데 1갯수 확인하는 코드에서 노래수만큼이 아니라 기타수만큼 반복문돌려서 7번 틀렸다.. import sys input = sys.stdin.readline from itertools import combinations # 기타 플레이 리스트 이진수로 바꿔서 set에 저장. N,M = map(int,input().split()) guitars = set() for _ in range(N): name,pos = input().split() bin_change='' for chr in pos: if chr=="Y": bin_change += '1' else: bin_change += '0' guitars.add(int(bin_change,2)) # 셋에서 0 제거하고 비었으면 -1출력후 종료..

발전소 최솟값으로 키는 문제. 꺼져있으면 켜져있는 발전소중에 제일 싼 발전소로 선택해 키는게 상태값 최저가면 최신화. import sys input = sys.stdin.readline from collections import deque def make_electic(start,cur_cnt): queue = deque() dp[start] = 0 answer=float('inf') if target_cnt==0 or cur_cnt>=target_cnt: return 0 elif cur_cnt==0: return -1 else: queue.append([start,0]) while target_cnt > cur_cnt: # 한 순회에 하나씩 킬꺼임. circle_SIZE = len(queue) for ..

버튼을 누르면 5가지 방향에 대해 불이켜지고 꺼지는 버튼이 있다. 2열부터는 위쪽 열에만 켜져있는걸 꺼주는 식으로 진행해주면 되는데 1열처리가 문제이다.(각각 누르고 켜는 경우의수 2의 10승) 때문에 1열 경우의 수에 대해 비트마스크 처리를 해준다. 사실 그 외의 탐색은 10*10이어서 그리 오래걸리지 않기 때문에 1열 경우의수 탐색만 잘 처리해주면 통과한다. table = [] for i in range(10): temp = list(input()) for j in range(10): if temp[j] == 'O': temp[j] = True #True: 불 켜져있음 continue temp[j] = False #False: 불 꺼져있음 table.append(temp) # 5방탐색. dx = [-..