전체 글

코드 # n은 최대 100000, k는 n보다 작거나 같은 수 # 최악의 경우 10^10, O(nlogn) 이하로 해결해야함 n,k = map(int, input().split()) numlst = [*map(int, input().split())] res = -987654321 # -100이 100000개일 경우 대비해서 작은 수 할당 arr_sum = [0]*(n+1) # 구간합을 구해 줄 리스트 for i in range(1,n+1): arr_sum[i] = arr_sum[i-1] + numlst[i-1] for i in range(1,n+1): if i+k > n+1: break # 범위를 벗어나면 탈출 # ex)10일까지의 온도합에서 5일차까지의 온도합을 빼면 6~10의 온도 합이 나온다 tem..

코드 # O(N^2+M)으로 해결할 수 있어야 한다 # O(N^2)인 이유는 2차원 배열의 구간합을 계산해야하므로 import sys input = sys.stdin.readline n,m = map(int, input().split()) numlst = [[0]*(n+1)] # 리스트 인덱스 1로 맞춰주기 위함 for _ in range(n): numlst.append([0,*map(int, input().split())]) arr_sum = [[0]*(n+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,n+1): arr_sum[i][j] = numlst[i][j] # 구간합을 구해줄 자리에 더해줘야할 값 할당 arr_sum[i][j] ..

코드 # 모든 노드의 depth의 합이 짝수면 No, 홀수면 Yes from collections import deque import sys input = sys.stdin.readline n = int(input()) cnt = 0 tree = [[] for _ in range(n+1)] visited = [0]*(n+1) # 방문기록 depth = [0]*(n+1) # 깊이를 기록할 리스트 for _ in range(n-1): x,y = map(int, input().split()) tree[x].append(y) tree[y].append(x) def bfs(): queue = deque() queue.append(1) visited[1] = 1 res = 0 while queue: pn = que..

코드 n = int(input()) path = [0,*map(int, input().split())] # 숫자를 맞춰주기 위해 tree = [] while path: if len(path) == 1: break level = [] # tree level을 모아줄 리스트 road = [] # 남는 수를 모아줄 리스트 for i in range(0, len(path)): if i%2 == 1: level.append(path[i]) # 홀수 번째 있는 것들이 리프 노드 else: road.append(path[i]) # 나머지는 남기기 tree.append(level) # 트리에 넣어준다 path = road # 반복 tree.sort(key=lambda x: len(x)) # 개수를 기준으로 정렬 for..

코드 # 트리 순회 # 루트 노드가 어디에 있는지에 따라 전위, 중위, 후위가 정해진다 # 전위 순회(preorder): 루트 -> 왼쪽 -> 오른쪽 순으로 순회 # 중위 순회(inorder): 왼쪽 탐색 -> 루트 -> 오른쪽 순회 # 후위 순회(postorder): 왼쪽 -> 오른쪽 -> 루트 순회 n = int(input()) tree = {} for _ in range(n): parent,left,right = input().split() tree[parent] = [left, right] # 이진 트리 입력 # 전위 순회 def preorder(node): if node != ".": print(node, end='') preorder(tree[node][0]) preorder(tree[node..

코드 # n = 100만 -> nlogn으로는 애매, O(N) 이하로 해결해야함 # 문제 조건: 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록하는 시행의 횟수 # 홀수-짝수 교체가 1번 있어야한다. # -> 홀수는 홀수끼리 모으고 짝수는 짝수끼리 모은다. # -> 이렇게하면 최대 1번 교체된다. # 최소 시행 횟수는? # 짝수를 어디 모을지, 홀수를 어디 모을지 정할 기준 n = int(input()) num = [*map(int, input().split())] cnt_odd = 0 cnt_even = 0 left_odd = 0 # 왼쪽에 홀수를 모으는 경우 left_even = 0 # 왼쪽에 짝수를 모으는 경우 for i in num: if i%2 == 1: cnt_odd += 1 left_odd..

코드1 n,k = map(int, input().split()) table = list(input()) res = 0 for i in range(len(table)): if table[i] == "P": for j in range(max(0,i-k), min(i+k+1,n)): if table[j] == "H": res += 1 table[j] = "E" break print(res) 코드2 # n: 문자열의 길이 (20000) # k: 먹을 수 있는 길이 # 인덱스에 주의 (range over 방지할 것) n,k = map(int, input().split()) table = list(input()) res = 0 for i in range(len(table)): if table[i] == "P": f..

코드 # 원래 리스트를 삭제하면 홀수 index였던 수가 짝수 index를 가짐에 주의 n = int(input()) numlist = [i for i in range(1,n+1)] while len(numlist) != 1: # 길이가 1이 되면 종료 temp = [] # 짝수번째만 넣어줄 리스트 for i in numlist[1::2]: # 2번째부터 2칸씩 띄어가며 추가 temp.append(i) numlist = temp # numlist 업데이트 print(numlist[0]) # 마지막 남은 수 출력 수학적으로 생각하면 n보다 크지않은 2의 제곱수를 출력하는 문제라고 한다.

코드 import sys from itertools import combinations INF = 987654321 input = sys.stdin.readline def dist(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2) n,m = map(int, input().split()) coor = [] # 좌표를 넣을 리스트 res = INF for _ in range(n): x,y = map(int, input().split()) coor.append((x,y)) for i in combinations(coor, m): temp = 0 for j in coor: min_dist = INF # 가장 가까운 대피소 찾아주는 과정 for k in range(m):..

코드1 import sys input = sys.stdin.readline N,d,k,c = map(int, input().split()) res = 0 sushi = [int(input()) for _ in range(N)] for i in range(N): if i+k+1