개발 블로그

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제설명 동적 계획법(Dynamic Programming, DP)은 최적화 문제를 해결하는 알고리즘으로서, 아래의 내용을 항상 명심해야 한다. '전체의 문제'를 '부분 문제'로 잘 나누었는가? 그렇다면 전체 문제를 해결하기 위한 부분 문제의 점화식은 무엇인가? 부분 문제들을 해결하며 얻는 결과값을 메모이제이션하는가? 부분 문제의 점화식은 부분 문제들 사이의 '관계'를 빠짐없이 고려하는가? 22..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 문제 설명 양팔 저울을 이용해 주어진 추로 특정 무게를 만드는 문제이다. 추를 사횽해 무게를 만드는 방법은 3가지 이다. 추의 무게를 더한다. 추의 무게를 뺀다. 추를 사용하지 않는다. 위 3가지 규칙으로 만들 수 있는 모든 무게를 dp에 저장한다. 재귀를 사용해서 코드를 작성했다. 2. 코드 설명 n = int(input()) weight = list(map(int, input().split..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 1. 문제 설명 이 문제는 전형적인 시뮬레이션 문제이다. 문제에서 요구하는 내용을 오류 없이 성실하게 구현한다면 풀기 가능 사방 탐색을 위해 dr, dc 의 별도의 리스트를 만들어 방향 탐색을 통해 카운트를 세어 몇번 움직였는지 세면 된다. 2. 입, 출력 3. 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) r..

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