eaz_coding

문제https://www.acmicpc.net/problem/1167 풀이지난번에 풀었던 1967번 트리의 지름을 그대로 이용한 문제 풀이다.트리의 지름은 하나의 공식처럼 이해하면 좋을 것 같다.    1. 루트 노드에서 각 노드까지 최소 거리를 구한다.    2. 최소 거리가 가장 먼 노드에서 가장 먼 거리를 구한다.import sysinput = sys.stdin.readlinefrom collections import dequev = int(input())nodes = [[] for _ in range(v+1)]for _ in range(v): q = deque(list(map(int, input().split()))) x = q.popleft() while q: y =..

문제https://www.acmicpc.net/problem/9019 풀이오답에서 놓쳤던 부분들1. L과 R에서 이동할때, str로 변경하지 않고 몫과 나머지로 계산해서 구할 수 있다.2. visited를 딕셔너리로 하는 것보다 리스트로 만들어서 인덱싱 하는 것이 더 빠르다.3. visited를 통해 더 적은 수로 미리 만들어진 곳은 큐에 추가하지 않는다. import sysinput = sys.stdin.readlinefrom collections import dequet = int(input())for _ in range(t): visited = [False for _ in range(10001)] a, b = map(int, input().split()) q = deque() q.appe..

문제https://www.acmicpc.net/problem/14891 풀이import sysinput = sys.stdin.readlinewheel = [list(input().strip()) for _ in range(4)]k = int(input())def check(now, i, directions): if i == 2: if now 0 and wheel[now][i] != wheel[now-1][2]: directions[now-1] = -directions[now] directions = check(now-1, i, directions) return directionsdef move(before, direction): res..

문제세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다. https://www.acmicpc.net/problem/1300 풀이import sysinput = sys.stdin.readlinen = int(input())k = int(input())s, e = 1, kanswer = 0while s = k: answer = m e = m-1 else: s = m+1print(answer)

문제요약1 한개 타일과 00 두개 타일이 있을 때, n개의 타일로 만들 수 있는 이진수의 개수를 15746으로 나눈 나머지를 구하시오. 원본https://www.acmicpc.net/problem/1904  풀이import sysinput = sys.stdin.readlinen = int(input())lst = [0, 1, 2]if n > 2: for i in range(3, n+1): lst.append((lst[i-1]+lst[i-2]) % 15746)print(lst[n])

문제https://www.acmicpc.net/problem/2805 풀이from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())trees = list(map(int, input().split()))u, l = max(trees), 1answer = 0while l 0: s += (trees[i] - mid) if s >= m: break if s >= m: if answer

풀이import sysinput = sys.stdin.readlinen, k = map(int, input().split())items = [tuple(map(int, input().split())) for _ in range(n)]dp = [[0] * (k+1) for _ in range(n+1)]for i in range(1, n+1): for j in range(1, k+1): if j >= items[i-1][0]: dp[i][j] = max(items[i-1][1]+dp[i-1][j-items[i-1][0]], dp[i-1][j]) else: dp[i][j] = dp[i-1][j]print(dp[n][k])

문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 원본https://www.acmicpc.net/problem/9251 풀이import sysinput = sys.stdin.readlinea = list(input())b = list(input())arr = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]for i in range(1, len(a)+1): for j in range(1, len(b)+1): if a[i-1] == b[j-1]: ..

문제n이 주어질 때, 세로가 3, 가로가 n인 타일로 만들 수 있는 경우의 수를 1000000007로 나눈 나머지를 구해라 원본https://school.programmers.co.kr/learn/courses/30/lessons/12902 풀이def solution(n): if n % 2 != 0: return 0 idx = n // 2 lst = [0, 3, 11] if idx

문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.입력첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.출력M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.풀이import sysn = int(sys.stdin.readline())arr_n = set(list(map(int, sys.stdin.readlin..