목록코딩테스트 (130)
코딩하는 해맑은 거북이
해당 글은 백준 4948번 문제 '베르트랑 공준'을 다룬다. 문제 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 설명 해당 문제는 소수의 갯수를 구하는 문제이고, 입력받을 때마다 소수를 구하면 시간 제한에 걸리기 때문에 미리 소수를 구해둔 다음에 정해진 범위 내에 소수의 개수를 세는 방식으로 해결해야 한다. 소수를 구하는 방법은 예전 포스팅에서 '에라토스테네스의 체'를 다뤘었다. 이를 이용하면 쉽게 구할 수 있다. 오랜만에 빠르게 소수..
해당 글은 백준 11057번 문제 '오르막 수'을 다룬다. 문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 설명 해당 문제는 DP로 간단하게 풀 수 있는 문제이다. 먼저 수는 0부터 시작할 수 있고, 인접한 수가 같아도 오름차순으로 친다는 조건이 있다. 한 자리의 수는 모든 값이 오르막 수 이므로 0~9까지의 1의 자리수를 의미하는 dp 배열을 [1]*10으로 초기화해준다. 두 자리의 수는 이전의 한 자..
해당 글은 백준 1049번 문제 '기타줄'을 다룬다. 문제 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 설명 해당 문제를 해결하는데 2가지 방법을 사용하였다. 먼저 DP를 통해 (N+1)개의 index를 가지는 result 배열을 만들고, 1부터 각 index개의 기타줄을 샀을 때 최솟값을 점차 구하는 방법이다. 다음은 단순하게 패키지와 낱개를 구매할 때의 가격에 대해 각각 최솟값만 저장해둔 후, 패키지로 살 때와 낱개로 6개를 샀을 때..
해당 글은 백준 11279번 문제 '최대 힙'을 다룬다. 문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 설명 해당 문제는 heapq 라이브러리를 이용해서 풀 수 있다. heapq 라이브러리는 기본으로 '최소 힙'으로 구성되어 있다. '최대 힙'으로 사용하기 위해서는 간단하게 -1을 곱하여 음수로 만들어주고, 출력시에 다시 양수로 되돌려주면 된다. 또한, 해당 문제에서 시간을 단축하기위해 input을 sys 라이브러..
해당 글은 백준 1309번 문제 '동물원'을 다룬다. 문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 설명 해당 문제는 DP 문제이고, 9901로 나눈 나머지를 출력하라는데서도 힌트를 얻을 수 있다. 그리고 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정하는 조건이 있다. 한 마리도 배치하지 않았을 경우(X), 왼쪽에 배치할 경우(L), 오른쪽에 배치할 경우(R)를 고려한 (n+1)x3의 배열을 생성하고, 아래의 점화식을 통해 해결할 수 있다. 1) i번째 행이 X일 경우, i-1번째 행은 X, L, R 모든 경우가 올 수 있으므로 이들의 합을 넘겨준다. ..
해당 글은 백준 1074번 문제 'Z'을 다룬다. 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 설명 해당 문제는 2x2 크기의 배열이 될 때까지 계속해서 2^n x 2^n 의 큰 사분면으로 생각하여, 각 사분면에 해당하는 visit을 더해주는 과정을 반복하면 된다. 코드 import sys input = sys.stdin.readline n, r, c = map(int, input().split()) visit = 0 whil..