For Programmer

N이 10만이라 사실상 누적합으로 풀어야하는 문제이다. 처음에 문제 접근 방식을 어떻게 해야하는지 계속고민하다 결국 힌트를 얻었다. 우선 P ,H , S를 냈을때 이기는 횟수를 구해 이를 누적합으로 저장해놓는다. 그후 인덱스를 다시돌면서 각각의 인덱스마다 다른걸 냈을때의 이기는 횟수를 구해 가장 큰값을 구해주는 식으로 했다.(즉, 지금이 P를 기준으로 3번째 인덱스라면 2번째까지 P가 이기는 횟수 + 3번째 인덱스부터 마지막까지 H로바꿧을때의 이기는 횟수) 와 같은식으로 각각의 6번의 모든 상황을 구해 가장 큰값을 구해주었다. # H > S, S > P, P > H import sys input = sys.stdin.readline N = int(input().rstrip()) H = [0] * (N +..

import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = ([[0] * (N + 1)]) + [[0] + list(map(int, input().split())) for _ in range(N)] # 2차원 누적합 구하기 prefix = ([[0] * (N + 1)]) + [[0] * (N + 1) for _ in range(N)] for i in range(1, N + 1): for j in range(1, N + 1): prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + arr[i][j] for _ in range(M): x1, y1, x..

간단한 누적합 문제이다. 누적합을 저장한 후 해당 구간만큼 빼주어 그 결과를 출력해주면 된다. import sys input = sys.stdin.readline N, M = map(int, input().split()) nums = [0] + list(map(int, input().split())) prefix = [0] * (N + 1) for i in range(1, N + 1): prefix[i] = prefix[i - 1] + nums[i] for _ in range(M): a, b = map(int, input().split()) print(prefix[b] - prefix[a - 1])

이 문제 그림으로 해놓으니 중위순회라는 것을 찾기가 힘들었다. 문제는 단순히 우선 트리의 깊이를 계산해주고 그 후 중위순회를 돌면서 너비를 계산해준다.(중위순회를 돌면서 찾아지는 순서가 해당 노드의 너비가 된다.) 그리고 나서 너비의 최댓값을 찾아주면 되는 간단한 문제이다. import sys input = sys.stdin.readline # 중위순회로 돌면서 번호를 매겨준다. def in_order(v): global order if v: in_order(tree[v][0]) tree[v][4] = order order += 1 in_order(tree[v][1]) # 이진트리를 돌면서 tree의 깊이를 매겨준다. def dfs(cur, depth): global max_depth visited[cu..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMeRLz6kC0DFAXd SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제는 각 자리수를 돌면서 현재와 다른 값(예를 들어 첫번째 자리가 0 이면 2진수는 1로 3진수는 1 또는 2로 바꾸어 보며) 모든 자리수를 해당방식으로 검사하여 10진수로 변환하여 그중 공통된 한개만 뽑아내는 식으로 처리하였다.) 뽑아 낼때는 set의 교집합 연산자를 이용하였다. # 입력받은 해당 진수의 값을 10진수로 변환 def convert(num, b): return int(num, ..

해당 문제는 어느 한 정점에서 부모노드들을(자신을 포함) 쭉 찾아 리스트에 저장한 다음에 2개의 정점들을 비교해서 가장 가까운 조상노드들을 출력하면된다. 여기서 부모 리스트들을 찾아 리스트에 저장해보면 항상 뒤로 갈 수록 상위 부모의 노드가 저장이 된다는 점이다. 따라서 두개의 리스트들을 뒤에서 비교해서 달라지는 지점의 인덱스를 찾은 다음 + 1 을 하면 가장 가까운 조상노드가 된다. import sys sys.setrecursionlimit(70000) input = sys.stdin.readline N = int(input().rstrip()) graph = [[] for _ in range(N + 1)] parent = [0] * (N + 1) visited = [0] * (N + 1) for _ ..

이 문제는 이것만 알면 쉽게 풀 수 있다. 루트 노드를 기준으로 가장 비용이 큰 노드를 찾아간다. 그 후 그 노드에서 다시 가장 비용이 큰 노드를 찾는다. 그렇게 찾은 비용이 지름이다. import sys sys.setrecursionlimit(100000) input = sys.stdin.readline N = int(input().rstrip()) graph = [[] for _ in range(N + 1)] # 그래프의 정보를 저장할 리스트 visited = [False] * (N + 1) # 방문처리 cost = [0] * (N + 1) # 한 정점 v까지 도착할때 드는 비용을 저장할 리스트 for _ in range(N - 1): p, c, temp_cost = map(int, input().s..

간단한 트리문제이다. 0으로 이루어진 리스트를 하나 선언 후 dfs를 돌면서 하위 재귀에서 탐색한 개수를 계속 더해주면서 리턴 해주면 된다. import sys sys.setrecursionlimit(150000) input = sys.stdin.readline # dfs로 자식노드의 개수 구하기 def dfs(cur): child_count[cur] = 1 visited[cur] = True for nxt in graph[cur]: if not visited[nxt]: child_count[cur] += dfs(nxt) #하위재귀에서 탐색한 개수를 계속 더해주면서 그 값을 리턴 return child_count[cur] N, R, Q = map(int, input().split()) # 정점의 수 , ..