For Programmer

해당문제는 누적합의 응용 문제라고 생각하면 된다. 우선 누적합을 구해놓고 누적합을 처음부터 N 까지 돌면서 해당 값의 찾고하는 값 K 를 뺀 cnt리스트의 인덱스에 저장되어 있는 값을 우선 더해준다.(즉, cnt[prefix[i] - K]) 그 후 해당 누적합의 개수를 cnt 리스트의 해당 인덱스에 +1개 추가해준다. (즉, cnt[prefix[i]] += 1) 하지만 K의 값이 아주크거나 음수가 존재할 경우 cnt의 배열크기가 아주 커지게 된다. 혹은 음수 계산을 할 수가 없다. 따라서 딕셔너리 형태로 변환하여 위의 상황을 진행해야 한다. N, K = map(int, input().split()) arr = [0] + list(map(int, input().split())) # 입력받은 수들을 저장 p..

해당 문제 dp적용할 점화식을 생각하기가 생각보다 까다로웠다. 해당 문제의 점화식은 다음과 같다. 어떠한 점 i, j 가 있으면 해당 지점까지 1~9 까지 개수를 3차원 dp에 dp[i][j][k] += 1로 (k는 해당 array[i][j] 의 값) 개수를 저장을 해놓는다. 그 후 개수를 누적해주기 위해 그 윗줄의 같은 행 즉 dp[i - 1][j] + 그 전열의 같은행 dp[i][j -1] 그리고 2번더해진 해당부분 dp[i -1][j -1]을 한번 빼주면 된다. 그 후 이렇게 저장된 dp의 값을 이용해 입력받은 4개의 점을 기준으로 1~10 까지 반복문을 돌면서 dp[x2][y2][k] - dp[x2][y1 - 1][k] - dp[x1-1][y2][k] + dp[x1-1][y1-1][k] 와 같은 ..

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 _ ..