코딩공부66 (c++) 11054번: 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 개요 백준 11053번의 응용문제이다. 11053번은 커지는 수열의 개수만 구했다면, 11054번은 커지는 수열과 작아지는 수열을 동시에 고려해야 한다. 나는 각 자리에서 커지는 수열의 개수와 작아지는 수열을 각각 메모이제이션을 하고, 둘을 더해주는 형식으로 풀었다. int lis(int start) { int& ret = cache[start]; if (ret != 0) return ret; ret = 1; .. 2024. 1. 16. (c++) BOJ 6549번 분할 정복 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 개요 여러 가지 풀이가 존재하는 문제지만 분할 정복으로 해결하는 방법으로 풀었다. 히스토그램이 주어졌을 때 분할 정복으로 구간을 나누어 계산한다. 2로 나누어 왼쪽, 오른쪽, 가운데 세 구간에 대한 경우를 구하면 된다. 1. 왼쪽에 최대 값 직사각형이 만들어 질 때 2. 오른쪽에 최대 값 직사각형이 만들어 질 때 3. 가운데 부분을 걸.. 2024. 1. 15. (c++) BOJ 11401번: 이항 계수 3 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 개요 코드 작성이 어렵다기보다 페르마의 소정리를 이용하여 큰 수에 대한 거듭제곱을 수행하면 된다. 페르마의 소정리를 이 문제에 적용시키는 것이 관건이다. 먼저 이항 정리의 식을 알고 가야 한다. $$ \binom{N}{K} = \frac{n!}{(N-K)!K!} $$ 그리고 페르마의 소정리를 간단하게 보면 $$ a^{p} \equiv a (mod \; p) $$ $$ a^{p-1} \equiv 1 (mod \; p.. 2024. 1. 14. (c++) BOJ 1629번: 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 개요 숫자의 제곱에 대해서 재귀로 프로그램을 돌렸을 경우 O(N)이 걸린다. ex) n = 6 6 → 5 → 4 → 3 → 2 → 1 여기서 분할 정복을 사용한다면 O(logN)이 걸리게 된다. ex) n = 6 6 → 3 → 2 → 1 시간을 절반 정도 줄일 수 있는 분할 정복을 알기에는 최적의 문제인 것 같다. 코드 pow() 함수를 사용하지 않았다. (사용하지 않아도 되는 코드이다.) 코드가 짧지만 분할 정복의 정수가 담겨있다. n이 짝수일 경우 n .. 2024. 1. 13. (c++) BOJ 1780번: 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 개요 쿼드 트리는 원래 4개로 나누는데 이 문제는 9개로 나누는 문제이다. 쿼드 트리 코드에서 재귀 부분만 코드를 고친다면 쉽게 해결 가능하다. 재귀 부분은 이중 for문을 이용해서 구현했다. (9번 코딩해도 문제없다.) 만일 N이 9일 경우 (0, 0), (0, 3), (0, 6) ... ,(6, 6) 순서로 재귀한다. 코드 #include #define MAX_N 2187 us.. 2024. 1. 13. (c++) BOJ 2630번: 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 개요 쿼드 트리란 대량의 좌표 데이터를 메모리 안에 압축하기 위해 사용하는 기법입니다. 주어진 공간을 4개로 분할하게 되는데 같은 데이터만 모일 때까지 재귀적으로 분할하게 됩니다. 위의 그림이 쿼드 트리로 변환하는 과정이다. 크기의 절반으로 분할해가면서 진행된다는 것을 알고 코드로 보자. 코드 분할한 정사각형의 처음 숫자와 다른 숫자가 나오면 4개의 정사각형으로 분.. 2024. 1. 12. 이전 1 2 3 4 5 6 ··· 11 다음
