맛대의 블로그

https://www.acmicpc.net/problem/2141 로직 우체국에서 각 사람까지의 거리의 합을 구해야함 우체국이 왼쪽에서 오른쪽으로 이동 가정 사람이 우체국의 왼쪽,오른쪽에 있는 지에 따라 값의 방향이 바뀜 우체국의 왼쪽에 있다면 오른쪽으로 이동시 거리가 1씩 증가 우체국의 오른쪽에 있다면 오른쪽으로 이동시 거리가 1씩 감소 즉 우체국의 왼쪽에 있는 사람의 수만큼 값이 증가, 오른쪽에 있는 사람의 수만큼 값이 감소 우체국이 마을중 제일 왼쪽에 있을땐 오른쪽에 사람이 많으므로 오른쪽으로 갈수록 거리의 합이 줄어듬 하지만 왼쪽에 있는 사람의 수가 절반을 넘어가는 순간 값의 증가 방향이 바뀜 따라서 사람의 수가 절반이 될 떄까지는 값이 감소하지만, 그 이후로는 다시 값이 증가하는 그래프 사람이 ..

https://www.acmicpc.net/problem/1461 로직 0에서 시작하여 음수위치, 양수위치에 책을 둬야함 책을 양수 // 음수 위치로 분리 및 정렬 => M개의 책을 운반시 정렬 순서로 한꺼번에 처리하기 위해 가장 먼 지점부터 M개씩 끊어서 처리 [1,2,3]을 2개씩 끊을 경우 [1,2],[3] // [1],[2,3] 으로 나눌 수 있는데 차이가 발생 [1,2],[3] 의 경우 22(왕복) + 31(편도) = 7 [1],[2,3] 의 경우 12(왕복) + 31(편도) = 5 해당 그룹에서 가장 큰 값 기준으로 이동을 하다보니 차이 발생 def div_books(arr:list[int]): # part1은 양수값들, part2는 음수값들로 분리 part1,part2 = list(),lis..

https://www.acmicpc.net/problem/1939 2개의 풀이방법 다익스트라(dijkstra) 두 지점중 한 지점(start)에서 다익스트라를 이용하여 다른 지점(end)지점의 최대 무게를 구하는 방식 새로운 길이 기존의 최대 중량 길(ls[node])보다 괜찮을 경우 탐색을 이어가는 방식 python의 heapq의 경우 작은값을 우선순위로 진행하기에 음수값을 저장하여 큰 값을 우선순위로 사용 중량이 큰 다리(길?,루트?) 부터 탐색하는 방식 import heapq,sys input = sys.stdin.readline def dijkstra(node:int,N:int,end:int)->int: INF = 1000000001 h = [(-INF,node)] ls = [0]*(N+1) ls..

https://www.acmicpc.net/problem/10986 누적합 값들을 누적해 가며 기록(total) 누적할때 나머지 값만 중요하므로 M으로 나머지 연산하며 누적 각각의 지점에서 total 값이 얼마인지를 기록(cnt) 로직 첫 숫자 값 1이라고 가정 x번 index까지 누적된 값이 1이라면 0-x번 사이의 누적합이 M으로 나누어 떨어짐 => 1번-x번 사이의 합이 M로 나누어 떨어짐 즉 0번 index에서 total = 1 이라면, x번 index에서 total = (A * M) % M + 1 = 1 2-x번 사이의 합은 (A*M) => M으로 나누어 떨어짐 이렇게 만들 수 있는 지점의 조합의 수가 정답 따라서 cnt[idx] 값이 같은 지점의 조합의 수가 정답(comb(v,2)) from ..

https://www.acmicpc.net/problem/1103 코드를 먼저 보고 설명하는게 더 좋을것 같아서 코드를 먼저 올린다. import sys input = sys.stdin.readline sys.setrecursionlimit(3000) def makeArr(R:int,C:int)->list[list]: arr = [] for _ in range(R): temp = [] target = input() for i in range(C): if target[i].isdigit(): temp.append(int(target[i])) else: temp.append(target[i]) arr.append(temp) return arr def recur(r:int,c:int,cnt:int)->None..

https://www.acmicpc.net/problem/11505 세그먼트 트리 활용 트리 구조 0번 노드는 비워둠 1번 노드는 2,3 번 노드의 곱, 2번 노드는 4,5번 노드의 곱 (이진 트리 형식) 업데이트 1번 노드는 모든 숫자의 곱 1번 노드부터 밑으로 해당 index를 가진 노드로 이동하며 업데이트(재귀 형태로 코드가 짜여 있어서 제일 밑 노드부터 업데이트 됨) index가 1~7까지 존재 할 때, 3번 노드(타겟)를 업데이트, 1~7의 중간값은 4 타겟인 3번 노드는 중간값 이하이므로 왼쪽 노드에 존재 왼쪽 노드는 1~4까지의 값을 가진 노드, 중간값은 (1+4)//2 = 2 타겟인 3번 노드는 중간값 초과이므로 오른쪽 노드에 존재 오른쪽 노드는 3~4까지의 값을 가진 노드 ... 구간 곱..

https://www.acmicpc.net/problem/14503 구현 구현문제라 특벽한 로직은 없습니다. 문제에 맞게 북동남서를 설정(dr,dc) 왼쪽 회전 방향을 구하기 위해 나머지 연산 사용(nd = (d+3)%4) 2-1 조건에 부합할 경우에만 break를 걸어 첫번쨰 반복으로 돌아와서 청소 그 외의 경우에는 두번째 반복문에서 반복 변수에서 now를 사용했는데, 그냥 r,c,d로 직접 할당 했으면 이해가 더 쉬웠을거 같다 import sys # N = row , M = column N,M = map(int,sys.stdin.readline().split()) position = tuple(map(int,sys.stdin.readline().split())) arr = [list(map(int,s..

https://www.acmicpc.net/problem/1202 로직 보석을 무게순으로 정렬 가방을 무게 한도순으로 정렬 무게한도가 가장 낮은 가방부터 채우는 형식 현재 가방에 담을 수 있는 보석이면 can_theft에 heapq를 이용하여 추가(최대 값어치를 가진 보석이 pop되게 하기 위해) 현재 가방에 담을 수 있다면 다음 가방은 무게 한도가 더 크므로 다음 가방에도 담을수 있음 => can_theft를 유지 현재 가방에 담을 수 있는 보석이 모두 can_theft에 담기면 그 중 가장 큰 값어치를 가진 보석을 담음 import sys from heapq import heappush,heappop N,K = map(int,sys.stdin.readline().split()) jewel = [] f..

https://www.acmicpc.net/problem/1238 다익스트라(dijkstra)활용 도로가 단방향이므로 도착,복귀경로가 다름 모이는 지점X에서 각 마을까지 최단거리를 출발지점과 도착지점을 기록한 도로를 이용하여 다익스트라를 이용하여 구함 (복귀경로) 각 마을에서 모이는 지점X까지는 출발지점과 도착지점을 바꾼 도로를 이용하여 다익스트라를 통해 구함(도착 경로) 모이는 마을X에서만 다익스트라를 통해 왕복을 구할 수 있음 import heapq,sys def dijkstra(start): h1 = [(start,0)] # 복귀 경로 계산용 h2 = [(start,0)] # 도착 경로 계산용 maximum = 1000000 shortcut1 = [maximum]*(N+1) #복귀 경로 최단거리 s..

https://www.acmicpc.net/problem/2263 tree 만들기 postorder의 마지막이 root인 것을 이용 root를 구한 뒤 inorder에서 root를 기준으로 좌우를 가름 갈랐을 때 왼쪽이면 왼쪽 서브 트리, 오른쪽이면 오른쪽 서브 트리 왼쪽 서브 트리에 해당하는 postorder 부분을 추출후 그안에서 root 찾기 반복 서브 트리자체를 인자로 함수 재귀 시도 메모리 초과 서브 트리에 해당하는 index의 시작과 끝을 인자로 재귀 시도 파이썬 재귀 한도에 걸려 Recursion Err 인덱스를 list에 추가하면서 pop 하는 형식으로 구현 index 시작, 끝 부분을 변수 하나로 바꾼뒤 코드를 짜면 가독성이 좋았을 것 같다 preorder 마찬가지로 Recursion E..