개발 블로그

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 설명 DFS + DP를 이용한 문제이다. DFS로만 푼다면 모든 경우의 수를 다 세야 하기 때문에 많은 경우의 수가 나오게 된다. 그래서 DP를 이용해서 불필요한 연산을 줄여야한다. 도착 지점까지 가는 경우의 수는 도착 지점이 아닌 임의의 점들에서 도착지점까지 가는 경우의 수를 합한 것과 같음 2. 코드 import sys input = sys.stdin.readline def dfs(x, ..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. 문제 설명 가장 긴 부분수열을 이진탐색으로 푸는 문제 DP를 사용해서 푼다면 시간복잡도(O(n^2)) 때문에 시간 초과가 나온다. 이분 탐색을 사용한다면 O(nlogn)의 시간복잡도로 풀 수 있다. 2. 코드설명 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) lis = [0..

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/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 1. 코드 설명 사각형 안에 숫자가 1로 나오는 정사각형 개수 찾는 문제 같다. 2. 예 입력에는 변의 개수 이후에 사각형 내부가 입력되고 출력으로는 하얀색 색종이의 개수, 파란색 색종이의 개수가 각각 한줄에 출력된다. 3. 코드 import sys input = sys.stdin.readline N = int(input()) paper = [list(map(int, i..

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/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 1 . 코드 설명 병합 정렬을 재귀 알고리즘으로 풀어가는 방식이였다. 병합 정렬부터 공부하고 시작했다. 이렇게 앞뒤를 나눠서 정렬해 나가면서 조합하는 방식이였다. k는 번째로 정렬한 수이다. 배열 A는 [ 3, 4, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5] 이런 식으로 나온다. 2. 예 앞서 설명한대로 앞뒤로 쪼개 앞에서 부터 하나씩 정..

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..