Algorithm Study
[백준 파이썬] # 9095 1, 2, 3 더하기
Silver III # 9095 1, 2, 3 더하기 링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 T = int(input()) for i in range(T): n = int(input()) dp = [0] * (n+3) dp[0] = 1 dp[1] = 2 dp[2] = 4 for i in range(3, n): dp[i] = dp[i-3] + dp[i-2] + dp[i-1] print(dp[-4]) 후기 동적 프로그래밍 문제라는 것을 캐치하면 규칙성을 발견할 수 있다 (동적 프로그래밍 문제인지 여부를 빠르게 파악하는 방법..
[백준 파이썬] # 11286 절댓값 힙
Silver I # 11286 절댓값 힙 링크 : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 import heapq import sys heap = [] N = int(sys.stdin.readline()) for i in range(N): x = int(sys.stdin.readline()) if x == 0: if len(heap) == 0: print(0) else: print(heapq.heappop(he..
[백준 파이썬] # 11549 구간 합 구하기 4
Silver III # 11659 구간 합 구하기 4 링크 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 import sys N, M = map(int, sys.stdin.readline().split()) li = list(map(int, sys.stdin.readline().split())) summary = 0 prefix_sum = [0] for i in li: summary += i prefix_sum..
[백준 파이썬] # 1927 최소 힙
Silver II # 1927 최소 힙 링크 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 import heapq import sys heap = [] N = int(sys.stdin.readline()) for i in range(N): num = int(sys.stdin.readline()) if num == 0: if len(heap) == 0: print(0) else: print(heapq.heappop(..
[백준 파이썬] # 3053 택시 기하학
Bronze III # 3053 택시 기하학 링크 : https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 풀이 import math R = int(input()) print('{:.6f}'.format(math.pi*R**2, 6)) print('{:.6f}'.format(2*R**2)) 후기 택시 기하학이 무엇인지 떠올리지 못해서 풀지 못했다. 유튜브 영상으로 택시 기하학을 찾아보고서야 문제 풀이 자체는 어렵지 않다는 것을 알게 되었다. cf. 택시 기하학에서 원이란 ..
[백준 파이썬] # 18870 좌표 압축
Silver II # 18870 좌표 압축 링크 : https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 # 해시 사용 : 정답__O(1) N = int(input()) X = list(map(int, input().split())) S = list(sorted(set(X))) dic = {} for i in range(len(S)): dic[S[i]] = i for i in X: print(d..
[백준 파이썬] # 1065 한수
Silver IV # 1065 한수 링크 : https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 N = int(input()) li = [False] * 1000 def d(n): text = str(n) if len(text)
[백준 파이썬] # 4673 셀프 넘버
Silver V # 4673 셀프 넘버 링크 : https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 풀이 def d(n): text = str(n) if len(text) == 1: t = int(text[0]) + int(text[0]) if len(text) == 2: t = int(text[0]) + int(text[1]) + int(text) if len(text) == 3: t = int(..
[백준 파이썬] # 11727 2xn 타일링 2
Silver III # 11727 2xn 타일링 2 링크 : https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 n = int(input()) dp = [0] * n dp[0] = 1 for i in range(1, n): if i%2 == 0: dp[i] = dp[i-1] + dp[i-1] - 1 else: dp[i] = dp[i-1] + dp[i-1] + 1 print(dp[-1] % 10007) 후기 이전 문제인 11726과 동일한 유형의 문제다. 수열의 n번째 값을..
[백준 파이썬] # 11726 2xn 타일링
Silver III # 11726 2xn 타일링 링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 n = int(input()) if n == 1: print(1) else: dp = [0] * n dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i-1]+dp[i-2] print(dp[-1] % 10007) 후기 결과부터 말하자면 피보나치 수열임을 발견할 수 있다. dp를 이용해서 원하는 값을 찾아가도록 구..