python

문제https://www.acmicpc.net/problem/4803백준 단계별로 풀어보기 - 트리풀이입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. 정말 어처구니 없는 실수로 삽질했던 문제다;; 입력값으로 주어지는 간선은 '노드1 노드2' 의 형태로 되어있는데, 부모-자식 순서로 주어지는게 아니다.놀랍지만 이 실수로 거진 20분은 삽질한것같다.(이게 안될리가 없는데 왜 안되지?의 반복)  일단 간선들을 저장할 2차원 리스트를 생성해준다. 각 행에는 빈 리스트가 들어간다.lst = [[], [], []] ← 이런 형태가 되겠다.그리고 무..

문제https://www.acmicpc.net/problem/1463백준 단계별로 풀어보기 - 동적 계획법1풀이정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 주어진 값 N이 1이 될때까지 세가지 조건을 체크해가며 최적의 케이스를 구해야한다.첫번째 풀이N = int(input())def make_one(): dp = [0] * (N+1) for i in range(2, N+1): dp[i] = dp[i-1] + 1 ..

문제https://www.acmicpc.net/problem/11401백준 단계별 풀이 - 분할 정복풀이이항계수가 주어졌을 때, 이항계수 (N K)를 1,000,000,007로 나눈 나머지를 구해야한다. 이항계수를 구하는 공식은 nCk = n!/(k!(n-k)!) 다.정리하면 아래와 같다.(n * (n-1) * (n-2) * (n-k+1) 여기부터 (n-k)! * (n-k) * (n-k-1) * ... * 2 * 1)/ (k * (k-1) * (k-2) * ... * 2 * 1)((n-k) * (n-k-1) * ... * 2 * 1)=> (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 2 * 1) 그리고 이 값들을 1,000,000,007로 나누어줘야한다.이걸 분할..

문제https://www.acmicpc.net/problem/11054백준 단계별 풀이 - 동적 계획법 1풀이수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 즉, 수열에서 어느 한 지점을 P라고 했을때 (증가하는 수열), P, (감소하는 수열)형태가 되어야 한다.아하, 이해는 쉽지만... 구현이 어렵다!결국 구글링, AI를 통해 풀이를 얻어냈다. 찾아보니 바이토닉 수열을 구하는 공식은 아래와 같다.바이토닉 수열 = LIS(증가부분수열) + LDS(감소부분수열) - 1 하지만 우리는 전환점이 되는 지점을 모르는 상태다.무조건 LIS, LDS를 구하는게 아니라 수열 하나하나를 전환점으로 가정하고 따져봐야한다. 예시 데이터로 ..

문제https://www.acmicpc.net/problem/1629백준 단계별 풀이 - 분할 정복풀이자연수 A를 B번 곱한 값을 구하는 문제다. 단, 값이 매우 커질 수 있으므로 C로 나누어야 한다.제한시간은 0.5초인데... 이걸 어떻게 분할하느냐? 만약 A, B가 2, 8로 주어졌다고 가정해보자.8은 짝수이므로 단순히 반으로 쪼개주면 된다.$ 2^8 $$ = 2^4 * 2^4 $$ = 2^2*2^2 * 2^2*2^2 $가 될것이다. 홀수라면?$ 2^5 $$ = 2 * 2^4 $$ = 2 * 2^2*2^2 $가 되겠다. 즉, 짝수일땐 B//2를, 홀수일땐 A * B//2를 곱해주면 된다.B가 0으로 주어질때 or B가 1일때 B//2는 자연수^0 = 1 이므로 1을 반환해주도록 한다.# 메모리: 31..

문제https://www.acmicpc.net/problem/10830백준 단계별로 풀어보기 - 분할 정복풀이NxN 행렬을 B번 곱한 값 % 1000 을 출력하는 문제다.# 메모리: 31252KB / 시간: 44msfrom sys import stdin# 1input = stdin.readlineN, B = map(int, input().split())A = [list(map(int, input().split())) for _ in range(N)]p = 1000A = [[col % p for col in row] for row in A]# 2def make_matrix(arr1: list, arr2: list) -> list: tmp = [[0]*N for _ in range(N)] for ..