개발 블로그

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 문제 설명 1 2 4 8 9 o o o 이런식으로 최대한 공유기를 떨어뜨려서 설치한 후에 그중에 가장 가까운 공유기 사이의 거리를 구하는 문제이다. 2. 코드설명 import sys input = sys.stdin.readline n, c = map(int, input().split()) home = [int(input()) for _ in..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 1. 문제 설명 분할 정복문제이지만 스택을 활용해서 문제를 풀었다. 2. 예 3. 코드 import sys while True: input_list = list(map(int, sys.stdin.readline().split())) if input_list[0] == 0: break input_list.append(0) ret = 0 sta..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 코드 설명 이항 계수를 구하는 공식이다. 범위가 4,000,000이라서 일반적인 공식으로는 풀기 불가능 페르마의 소정리를 활용한 코드, 확장 유클리드 호제법의 두가지 방식으로 풀 수 있다. 페르마의 소정리 - p가 소수이고 a가 p의 배수가 아니면 a^(p-1)의 p로 나눈 나머지는 1이다. 유클리드 호제법 - 자연수 a,b가 주어졌을 때, a와 b의 최대 공약수를 구하는 방법. - gcd(a,b) 확장 유클리드 ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 코드 설명 두줄로 들어오는 문자열의 부분 문자열중에 최다 길이. 부분 수열하고 비슷한듯 다른 문제. 2. 예 A C A Y K P C A P C A K 부분 문자열중에 가장 긴 문자열은 ACAK이다. 3. 코드 s1 = input() s2 = input() dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)] fo..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 1. 코드설명 - n-1개의 원판을 1번 막대에서 2번 막대로 옮긴다. - 남은 1개의 원판을 1번 막대에서 3번 막대로 옮긴다. - 다시 n-1개의 원판을 2번 막대에서 3번 막대로 옮긴다. 이 매커니즘으로 재귀를 짠다. 2. 예 원판의 개수 n개를 입력하면 첫번째줄에 3번째로 모두 옮기기 위한 총 이동 횟수가 나오고 두번째줄부터는 원판이 어디서 어디로 이동했는가가 나온다. 3. 코..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 1. 코드설명 자연수 n에 대하여 n부터 2n사이에 소수가 적어도 하나 존재한다는 내용 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 문제 2. 예 3. 코드 내용 # 4948 : 베르트랑 공준 # 시간초과로 틀림 a = 1 def sosu(n): if n == 1: return False for i in range(2, int(n**0.5)+1): i..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 1. 코드 설명 3kg, 5kg으로 설탕봉투 수를 세는데 최대한 적게 봉투를 가져가야한다. 필요한 무게를 입력받고 최소필요 봉투 개수를 출력한다. 2. 예 : 18kg의 경우 3kg 6개 보다 5kg 3개 + 3kg 1개 해서 4봉투를 가져가는 방법을 추구 3. 풀이 코드 # 2839 : 설탕배달 s = int(input()) if s%5==0: print(s//5) else: p=0 while s>0: i..

# 1316 : 그룹 단어 체커 a = int(input()) b = 0 re = 0 for _ in range(a): b=0 c = input() d=[] if len(c)