chyam

https://www.acmicpc.net/problem/1922import sysimport heapqinput = sys.stdin.readlinen = int(input())m = int(input())computers = []res = 0parent = [0] * (n+1)def find(x): # 특정 원소가 속한 집합 찾기 if parent[x] != x: # 루트 노드가 아니라면 루트 노드 찾을때까지 재귀적으로 호출 parent[x] = find(parent[x]) return parent[x]def union(a,b): # 합치기 a, b = find(a), find(b) # 속하는 집합의 부모를 찾음 if a

https://www.acmicpc.net/problem/10986import sysinput = sys.stdin.readlinen, m = map(int, input().split())numbers = list(map(int, input().split()))cnt = [0] * mprefix = 0cnt[0] = 0# (a+b) % m == a % m == b % m for x in numbers: # 누적합이 같은것의 개수 증가 prefix = (prefix + x) % m cnt[prefix] += 1 res = cnt[0] # 나머지가 0인 경우for c in cnt: res += c * (c - 1) // 2 # 같은 나머지가 나온 개수가 C일때 만들 수 있는 쌍의 개수prin..

1. DP로 푸는 방법 만약 list에 [8,9,2,1,4,6,7,10] 이 있다면, 여기서 최장 증가 수열은 [1,4,6,7,10] 이다.처음부터 끝까지 순차적으로 기준을 잡은 뒤 앞의 숫자와 비교한다. 만약 기준이 앞의 숫자보다 크다면 앞의 숫자의 최장 증가 + 1(기준)와 현재까지 구한 기준 숫자의 최장 증가 길이 중 더 큰 값을 선택한다. 코드로 보면 다음과 같다.def lis(li): if not li: return 0 # dp[i] : i번째 인덱스에서 끝나는 최장 증가 수열의 길이 dp = [1] * len(li) for i in range(len(li)): # 기준이 되는 숫자 for j in range(i): # 기준보다 앞쪽에 있는 숫자들..

https://www.acmicpc.net/problem/2565n = int(input())electronic = []li = []res = 0for _ in range(n): electronic.append(list(map(int,input().split())))electronic.sort() # 정렬for a, b in electronic: li.append(b) # 이어진 전깃줄 번호 저장def lis(li): dp = [1] * len(li) for i in range(len(li)): for j in range(i): if li[i] > li[j]: # 이전보다 길다면 dp[i] = max(dp[i], dp[j] ..

https://www.acmicpc.net/problem/11404import sysinput = sys.stdin.readlinen = int(input())m = int(input())li = [[float('inf')]*n for _ in range(n)]for _ in range(m): a, b, p = map(int,input().split()) li[a-1][b-1] = min(p,li[a-1][b-1])for i in range(n): for j in range(n): if i != j: for k in range(n): if j != k and i != k: li[j][k] = mi..

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기배낭 알고리즘이란? 배낭 문제(Knapsack)는 n개의 물건과 배낭 있을 때, 각 물건에는 가치와 무게가 존재한다. 또한 각 물건은 1개씩만 있다. 배낭에는 담을 수 있는 최대 용량이 존재한다. 이러한howudong.tistory.com오래 고민하다가 위의 블로그 내용을 통해 풀이를 이해 하였다. https://www.acmicpc.net/problem/12865n, k = map(int, input().split())items = []dp = [[0] * (k + 1) for _ in range(n + 1)]for _ in range(n): v, w = map(int, input().split()) items.append((w..

https://www.acmicpc.net/problem/2468import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())space = [] # 땅 높이max_len, res = 0, 0direct = [[0,1],[0,-1],[1,0],[-1,0]] # 방향 설정 for _ in range(n): tmp = list(map(int,input().split())) max_len = max(max(tmp),max_len) # 빗물 최대 높이 space.append(tmp)def bfs(l, i, j): queue = deque([(i,j)]) # 시작 지점 visited[i][j] = Tru..

https://www.acmicpc.net/problem/1916import heapqn = int(input())m = int(input())graph = [[] for i in range(n+1)]for i in range(m): u,v,w = map(int,input().split()) graph[u].append([v,w])start, end = map(int,input().split()) # 출발점, 도착점 distance = [float('inf')] * (n+1) # 각 최소 거리 저장distance[start] = 0q = []heapq.heappush(q,(0,start))while q: x, y = heapq.heappop(q) # 비용, 기준점 if distanc..