one Book a Day

분할정복 대표적인 문제이다. 연산 갯수를 줄이기 위해 반으로 쪼개고 쪼개 A*1로 쪼갠다음 그 결과값을 양쪽에서 곱해주면서 조합해준다. 분할 : 곱해야 하는 갯수 B를 2로 나누어 주며 분할한다. 정복 : A*1의 정복을 통해 계산한다. 조합 : A*A / (A*A) * (A*A) / 이런식으로 결과값을 제곱하면서 올라와 모든 재귀가 끝나면 연산이 끝난다. import sys input = sys.stdin.readline A, B, C = map(int, input().split(' ')) # 정복 def conq(length): # 정복 : length가 1이 되면 A를 반환하겠다.(최소단위 연산의 정복) if length == 1: return A %C # 짝수면 좌우로 찢고 if length % ..

벽을 뚫는다 = 이동시 비용이 든다. = 가중치 있는 그래프 가중치가 0 과 1로 이루어진 그래프 탐색으로 맨앞 요소에 가중치 누적요소 cnt를 넣어 가중치가 낮은 길로 target을 찾아가는 bfs를 그리면 된다. heap을 이용해 낮은가중치탐색을 하는방법과 deque을 이용해 가중치가0인 노드이동에 대해 appendleft를 해주는 방법도 있다. 여튼 먼저 탐색해준다는게 핵심. import sys input = sys.stdin.readline from heapq import heappush, heappop m, n = map(int, input().split()) dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] maze = [] visited = [[0] * m for i in ..

다익스트라의 정석.(단방향) import sys input = sys.stdin.readline from collections import defaultdict from heapq import heappush,heappop def dijkstra(start): global min_dists heap = [] min_dists = [float('INF')]*(V+1) min_dists[start] = 0 heappush(heap,[min_dists[start],start]) while heap: cur_dists,cur_node = heappop(heap) if cur_dists > min_dists[cur_node]: continue for next_dists,next_node in graph[cur_n..

골드2여서 시간 메모리 빡빡할까봐 쫄았는데 그냥 무지성 코드로 통과.. 슬라이스 정렬,중앙값찾기.,count로 출력숫자 제어. import sys input = sys.stdin.readline for test in range(int(input())): M = int(input()) seqs = [] for i in range(M//10+1): seqs.extend(list(map(int,input().split()))) print(M//2+1) print(seqs[0], end=" ") if M !=1: cnt=1 for i in range(2,M,2): print(sorted(seqs[:i+1])[(i+1)//2], end=" ") cnt+=1 if cnt==10: print() cnt=0 else:..

최소거리 배열 다 구해서 전부 더해준 다음 합 미니멈인 방번호 출력 다익스트라로 간단하게 풀었다. import sys input = sys.stdin.readline from heapq import heappop, heappush from collections import defaultdict # 각 친구들 위치에서 모든 방에 대해 최소거리 배열 출력. def dijkstra(start): global dp_dists dp_dists = [float('inf')] * (N + 1) heap = [] dp_dists[start] = 0 heappush(heap, [dp_dists[start], start]) while heap: cur_dist, cur_node = heappop(heap) if dp_di..

출발지, 도착지에 따라. BFS로 거리구하면 끝. import sys input = sys.stdin.readline from collections import defaultdict,deque def Distance(a,b): queue = deque() queue.append(a) visited = [False]*(N+1) visited[a] = True target_dist = [0]*(N+1) while queue: v = queue.popleft() if v==b: print(target_dist[v]) return for next,dist in graph[v]: if not visited[next]: queue.append(next) visited[next] = True target_dist[n..

문자열 뒤집은 key찾아서 key길이와 중앙값 출력. import sys input = sys.stdin.readline N = int(input()) files = [input().rstrip() for _ in range(N)] for i in range(N-1): for j in range(i,N): if files[i][::-1] == files[j]: print(len(files[i]), files[i][len(files[i])//2]) exit()

실질적으로 별찍기(프렉탈 분할정복) 을 접한건 두번째다 첫번째는 감이 잘 안왔는데 이제는 슬슬 감이온다. 1. 입력값 2. 최소단위로 분할 3. 최소문제 해결 4. 더 큰문제 정복 5. 조합 정복시 그림이 잘 안그려질때는 실질적으로 뭐가 몇개 늘어났는지. 최소단위가 몇개 늘어나는지 잘 살펴보면 된다. 그리고 최소단위를 반복, 순회하면서 반복 덧셈, 곱셈을통해 확장시켜나가면 된다. 이 문제같은 경우 가장 작은 삼각형이 다음 차수에 밑에 2개 더 붙고 그다음은 그 큰 3개의 삼각형이 밑에 2개씩 더붙는다. 즉 이전 그림의 두배씩 아래쪽 배열에 추가된다고 생각하면 된다. 또 처음 들어갔던 배열도 " " 빈칸을 추가해줘야하는데 얼마나 추가해주냐면 실질적으로 늘어나는 3칸을 세어 3칸 -> 6칸 -> 12칸 즉 ..

처음에 그냥 matrix에 넣었다가 시간초과나고 합연산은 한번에 하는걸로 코드 수정. 통과 import sys input = sys.stdin.readline for test in range(int(input())): N,M = map(int,input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] ans = [[] for _ in range(2)] for i in range(N): ans[0].append(sum(matrix[i])) for i in range(N): ans[1].append(sum(matrix[m][i] for m in range(N))) for _ in range(M): r1,c1,r2,c2,v = ma..

뭔가 요새 DFS로 풀릴것 같으면 DFS하는 습관이 생겼다. import sys input = sys.stdin.readline N = int(input()) A = list(map(int,input().split())) check = [False] * 1200 ans = [] v = 0 cnt = 0 def DFS(v,cnt): if v>=N-1: ans.append(cnt) return if A[v]==0: return for i in range(1,A[v]+1): if not check[v+i] and not v+i>N-1: check[v+i] = True DFS(v+i,cnt+1) check[v+i] = False check[0]=True DFS(0,0) print(min(ans) if ans e..