Algorithm

(파이썬) 백준 1725번 "히스토그램"

# 문제상황 # 스택을 이용한 풀이 일정 구간에서 가장 큰 직사각형의 넓이는 (해당 구간의 너비) x (해당 구간에서의 높이 최솟값) 입니다. 스택의 top이 나보다 크다면, 계속해서 pop합니다. 즉 스택의 top에는 늘 최댓값이 들어있도록 합니다. 스택을 pop 하며 뒤로 돌아가는 과정에서, 정답이 될 수 있는 모든 직사각형 넓이를 탐색할 수 있습니다. 현재 나의 위치에서부터 뒤로 탐색하는 것이기 때문에, 뒤로 가면 갈수록 높이(= 스택에서 pop한 값)는 낮아집니다. 즉, (뒤로 탐색한 거리) x (pop한 값)이 직사각형 넓이가 됩니다. import sys input = sys.stdin.readline n = int(input()) stk = [] l = 0 ans = 0 for r in ran..

(파이썬) 백준 2293번 "동전 1"

# 답 n, k = map(int, input().split()) coins = [int(input()) for _ in range(n)] dp = [0] * (k + 1) dp[0] = 1 for coin in coins: for i in range(coin, k + 1): if i - coin >= 0: dp[i] += dp[i - coin] print(dp[k]) # 풀이 dp[n]을 'n원을 만들 수 있는 모든 경우의 수'이라고 할 때, dp 테이블을 일일이 채워보면 아래와 같습니다. dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] coin = 1 1 1 + 1 1 + 1 + 1 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 + 1 coi..

기약분수 만들기

분자가 a, 분모가 b인 분수를 기약분수로 만드는 방법 → a와 b를 각각 최대공약수로 나누어 주면 된다! import math gcd = math.gcd(a, b) a // gcd b // gcd

LIS 가장 긴 증가하는 부분 수열

1. dp를 이용한 풀이 N = int(input()) arr = list(map(int, input().split())) dp = [1] * N for i in range(N): for j in range(i): if arr[j]

(파이썬) 백준 2740번 "행렬 곱셈"

# 답 N, M = map(int, input().split()) matrix1 = [list(map(int, input().split())) for _ in range(N)] M, K = map(int, input().split()) matrix2 = [list(map(int, input().split())) for _ in range(M)] ans = [[0] * K for _ in range(N)] for n in range(N): for k in range(K): tot = 0 for m in range(M): tot += matrix1[n][m] * matrix2[m][k] ans[n][k] = tot for i in range(len(ans)): print(*ans[i]) # 행렬 곱셈 1. ..

(파이썬) 백준 1629번 "곱셈"

# 문제상황 A, B, C = map(int, input().split()) def R(B): global A, C ans = 0 if B == 1: ans = A elif B % 2 == 1: ans = R(B // 2) ** 2 * A elif B % 2 == 0: ans = R(B // 2) ** 2 return ans % C print(R(B) % C) # 풀이과정 어떤 수 A를 20억번 곱해야한다고 가정해봅시다. 무식하게 A를 정말 20억번 다 곱하고 있으면 시간이 오래 걸립니다. 생각해봅시다. (A의 20억승)은 (A의 10억승)을 2번 곱한 것과 같습니다. 즉 A를 20억번 곱할 필요 없이, A를 10억번만 곱하고 그 결과를 제곱하면 연산횟수가 절반으로 줄어듭니다. 다른 예시를 생각해봅시다...

(파이썬) 백준 10986번 "나머지 합"

# 답 N, M = map(int, input().split()) a = list(map(int, input().split())) + [0] cnt = [0] * M for i in range(N): a[i] += a[i - 1] cnt[a[i] % M] += 1 ans = cnt[0] for v in cnt: ans += v * (v - 1) // 2 print(ans) # 풀이과정 1. 누적 합(p_sum)을 구한다.2. 누적 합을 m으로 나눈 나머지가 같은 것끼리 분류한다.3. 누적 합의 나머지가 같은 것들 중에서 2개를 조합한다. 이 때 뽑힌 누적합 인덱스를 각각 i와 j라고 하겠다.4. i + 1부터 j까지 구간의 구간합(j번째 누적합 - i번째 누적합)은 m으로 나누어 떨어진다.5. 단, 누적..

(파이썬) 백준 1676번 "팩토리얼 0의 개수"

# 답 N = int(input()) print(N // 5 + N // 25 + N // 125) # 원리 0의 개수는 곧, 10이 몇 번 곱해져 있나를 세는 것. 10이 몇 번 곱해져 있느냐는 곧, 2와 5가 몇 번 곱해져 있냐는 것. 2와 5가 몇 번 곱해져 있느냐는 곧, 5가 몇 번 곱해져 있냐는 것. (2의 배수가 5의 배수보다 더 촘촘히 있다. 따라서 2의 배수는 5의 배수보다 언제나 많고, 결국 5의 개수가 10의 개수를 결정한다.) 결국 이 문제는 N! 안에 곱해져 있는 5의 개수를 구하면 된다. 생각해보자. 5! 안에는 5의 배수가 몇 개 들어있는가? 1개 들어있다.(5) 6! 안에는 5의 배수가 몇 개 들어있는가? 여전히 1개 들어있다. (5) 10!안에는 5의 배수가 몇 개 들어있는가..

(파이썬) 백준 11659번 "구간 합 구하기 4"

# 답 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [0] + list(map(int, input().split())) for i, v in enumerate(arr): if i != 0: arr[i] += arr[i - 1] for _ in range(M): i, j = map(int, input().split()) print(arr[j] - arr[i - 1]) # 원리 i번째부터 j번째까지의 구간 합을 빠르게 구하는 방법은 1) 주어진 배열을 처음부터 누적합 형태로 바꿔놓고, 2) arr[j] - arr[i - 1]하면 됩니다. 예를 들어, 다음과 같은 배열 arr1이 있다고 가정해봅시다. arr1 = [1..

(파이썬) 백준 2981번 "검문" 자세한 원리

# 답 import math N = int(input()) arr = [] G = 0 for i in range(N): arr.append(int(input())) if i == 1: G = abs(arr[1] - arr[0]) G = math.gcd(G, abs(arr[i] - arr[i - 1])) # G의 약수 구하기 ans = set([G]) for i in range(2, int(G ** 0.5) + 1): if G % i == 0: ans.add(i) ans.add(G // i) print(*sorted(list(ans))) # 원리 나누었을 때 나머지(R)를 모두 같게 만들어주는 숫자 M이 있다고 가정해봅시다. 그렇다면 각 숫자들(N)은 아래와 같이 표현할 수 있을 것입니다. N[0] = X..