clohi 님의 블로그

https://www.acmicpc.net/problem/1965 문제 코드import sysinput = sys.stdin.readlinen = int(input())box = list(map(int, input().split()))dp = [1] * nfor i in range(n): for j in range(i): if(box[i] > box[j]): dp[i] = max(dp[i], dp[j] + 1)print(max(dp)) 문제 풀이 - DP 문제를 봤을 때 DP를 이용해서 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제를 푸는 것과 똑같다. 상자 크기 배열에서 앞에 있는 상자가 뒤에 있는 상자보다 작을 때만..

https://www.acmicpc.net/problem/10431 문제 코드 import sysinput = sys.stdin.readlinep = int(input())for _ in range(p): arr=list(map(int,input().split())) total=0 for i in range(1,len(arr)-1): for j in range(i+1,len(arr)): if arr[i] > arr[j]: arr[i],arr[j] = arr[j],arr[i] total+=1 print(arr[0], total) 문제 풀이 - 시뮬레이션 간단한 실버 구현문제이다. 우선 테스트 케..

https://www.acmicpc.net/problem/16713 문제 코드 - 첫번째 import sysinput = sys.stdin.readlinen, q = map(int, input().split())li = list(map(int, input().split()))prefix_sum = [0] * (n+1)query = []for i in range(1, n+1): prefix_sum[i] += li[i-1] ^ prefix_sum[i-1]for j in range(q): s, e = map(int, input().split()) if(s == 1): query.append(prefix_sum[e]) else: query.append(prefix_..

https://www.acmicpc.net/problem/17299 문제 코드 - 직접 구현from collections import dequeimport sysMAX_NUM = 1000001input = sys.stdin.readlinen = int(input())li = list(map(int, input().split()))li_cnt = [0] * MAX_NUMfor i in li: li_cnt[i] += 1ans = deque()stack = []while(1): if(len(li) == 0): break x = li[-1] if(len(stack) == 0): stack.append(x) ans.appendleft(-1) ..

https://www.acmicpc.net/problem/10799 문제 코드 import sysinput = sys.stdin.readlines = input().rstrip()stack = []cnt = 0for i in range(len(s)): if s[i] == '(': stack.append(s[i]) else: stack.pop() if s[i - 1] == '(': cnt += len(stack) else: cnt += 1print(cnt) 문제 풀이 - 스택 스택을 이용하여 풀 수 있는 문제이다. 우선 여는 괄호와 닫는 괄호가 있는데 여는 괄호가 들어오면 무조건 스택에 push를 하고, 닫..

https://www.acmicpc.net/problem/1149 문제 코드 import sysinput = sys.stdin.readlinen = int(input())rgb= []for _ in range(n): rgb.append(list(map(int, input().split())))dp = [[0] * 3 for _ in range(n)]dp[0] = rgb[0]for i in range(1, n): dp[i][0] = rgb[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = rgb[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = rgb[i][2] + min(dp[i-1][0], dp[i-1][1])pr..

https://www.acmicpc.net/problem/24480 문제 코드import syssys.setrecursionlimit(100000)input = sys.stdin.readlinen, m, r = map(int, input().split())graph = [[] for _ in range(n+1)]visited = [False] * (n+1)for i in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u)for j in graph: j.sort(reverse=True)idx = 1def dfs(graph, visited, n): global idx visited[n..

https://www.acmicpc.net/problem/15900 문제 코드import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())graph = [[] for _ in range(n+1)]for i in range(n-1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a)visited = [False] * (n+1)dist = [0] * (n+1)leafnode = []sum_dist = 0q = deque([1])visited[1] = Truewhile q: is_leafnode = True u = q.po..