알고리즘
[백준 파이썬] # 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를 이용해서 원하는 값을 찾아가도록 구..
[백준 파이썬] # 1620 나는야 포켓몬 마스터 이다솜
Silver IV # 1620 나는야 포켓몬 마스터 이다솜 링크 : https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이 import sys N, M = map(int, sys.stdin.readline().split()) dogam = {} for i in range(1, N+1): a = sys.stdin.readline().rstrip() dogam[i] = a dogam[a] = i for i in range..