one Book a Day

들어오는 두 점이 모두 동일한 집합에 속한 점이라면 사이클이 형성된다. import sys input = sys.stdin.readline def find(x): if x == arr[x]: return x arr[x] = find(arr[x]) return arr[x] def union(x, y): x = find(x) y = find(y) if x < y: arr[y] = x else: arr[x] = y N, M = map(int, input().split()) arr = [i for i in range(N)] for i in range(M): a, b = map(int, input().split()) if find(a) == find(b): print(i+1) exit() union(a, b) p..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 날짜보다 강의한 숫자가 더 크면 가장 싼 강연 포기 import sys input = sys.stdin.readline from heapq import heappop,heappush n=int(input()) arr=[list(map(int, input().split())) for _ in range(n)] arr.sort(key=lambda x: x[1]) h..

박스 순회하며 누적합. 자주나오는 유형이다. 중요한건 누적합은 뒤에서부터 쌓아줘야 중복이 안생긴다는것. 때문에 H부터 1까지 순회해주며 더해줬다. import sys input = sys.stdin.readline N, M, H = map(int, input().split()) boxes = [list(map(int, input().split())) for _ in range(N) ] dp = [0]*(H+1) for box in boxes: for idx in range(H,0,-1): if not dp[idx]: continue for num in box: if idx + num > H: continue dp[idx+num] += dp[idx] for num in box: dp[num] += 1 pr..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 배열돌리기 쓸데없이 귀찮지만 오늘 괜찮은 방법론을 배웠다. deque로 rotate시켜버리는 것. 따로 tmp를 안두어도 된다는게 너무 맘에 든다. import sys input = sys.stdin.readline from collections import deque def rotate_each(x,y,d,m): q = deque() for i in range(y-..

최소공배수 길이를 만들어 비교해줬다. 근데 다른 풀이보니까 그냥 상대 문자 길이만큼 곱해줘도 되더라..(꼭 최소가 아니라 그냥 공배수면됨) import sys input = sys.stdin.readline from math import gcd s = input().rstrip() t = input().rstrip() n = len(s) m = len(t) a = gcd(n,m) if s*(m//a) == t*(n//a): print(1) else: print(0)

https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net K명 모두가 친구여야 통과하는 dfs를 짜주면 된다. import sys input = sys.stdin.readline def dfs(v,arr): if len(arr)==K: for num in arr: print(num) exit() for i in range(v+1,N+1): if not visited[i]: for num in arr: if num not in graph[i]: break el..

xor로 다른거 찾은 다음 1이랑 0 갯수 세서 옮기거나 더해줌 import sys input = sys.stdin.readline for _ in range(int(input())): N, M = map(lambda x: int(x,2), input().split()) xor = N^M n = len(bin(xor)[2:]) one = 0 zero = 0 answer = 0 for i in range(n): if xor & 1

세번째 푼다. 솔직히 이젠 쉬운듯. 중복 탐색은 조금 존재한다. import sys input = sys.stdin.readline def dfs(x,y,depth,s,init_x,init_y): global max_sum if depth==4: max_sum = max(max_sum,s) return for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

hash map import sys input = sys.stdin.readline N, M = map(int, input().split()) dic = {} for _ in range(N): adress, pw = input().split() dic[adress] = pw for _ in range(M): print(dic[input().rstrip()])

bfs로 나머지값보다 작고 첫번째 가능한 제곱수값과 나머지의 차이보다 큰 제곱수들만 조사하는 방식. 좋은걸 깨달았다. bfs의 종료조건은 무조건 위보다 아래가 좋다는 것을.. 아래에 하고 return해야 한분기 덜 돈다. import sys input = sys.stdin.readline from collections import deque def bfs(n): q = deque() q.append((n,0)) visited[n] = True while q: r, cnt = q.popleft() flag = 1 for square in squares: next_r = r-square if next_r > 0 and not visited[next_r]: if flag: first = next_r flag ..