백준 검색 결과

해당 글 78건

[BOJ 11066] 파일 합치기(C++)

파일 합치기(Gold3) 문제 전체 문제 보기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 접근법 이번 문제는 동적 계획법으로 풀 수 있는 문제입니다. 동적 계획법의 주요한 두 가지 개념은 다음과 같습니다. 큰 문제를 작은 문제로 나눠서 문제를 해결한다. 한번 푼 문제를 저장하여 불필요한 연산을 줄인다. 우선 큰 문제를 작은 문제로 나눠 봅시다. 문제의 첫 번째 예시 (40 30 30 50) 인경우를 살펴보겠습니다. 장의 수가 총 4개일 때 마지막으로 파일을 합쳐서 하나로 만들 때는 다음과 같이 3..
Algorithms/DP 2021. 10. 20. 10:31

[BOJ 15683] 감시 (C++)

감시(Gold 5) 문제 전체 문제 보기 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 접근법 문제에서 주어지는 카메라는 최대 8대입니다. 모든 카메라가 4방향으로 회전할 수 있다고 하더라도 \(4^8 = 65,536\)경우의 수가 존재하고 각 경우의 수마다 전체 맵(64칸)에 존재하는 사각지대를 카운트하면 되기 때문에 백트래킹을 활용한 완전 탐색을 하더라도 충분히 시간 내에 풀 수 있는 문제입니다. 다만 카메라의 회전을 구현하는 부분이 조금 복잡한 문제였습니다. 카메라의 회전은 다음과 같이 구현하..
Algorithms/Implementation 2021. 10. 18. 21:04

[BOJ 11444] 피보나치 수 6

피보나치 수 6 (Gold 3) 문제 전체 문제 보기 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근법 피보나치 수는 아래의 점화식을 따릅니다. \[f(n) = f(n-1) + f(n-2) \] 그런데 이번 문제에서 n의 크기는 매우 큽니다. 그래서 Brute Force로는 해결할 수 없고 행렬의 제곱으로 문제를 해결해야 합니다. 위 점화식을 행렬로 표현하면 아래와 같이 나타낼 수 있습니다. \[\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} = \begin{pmatr..
Algorithms/Math 2021. 10. 9. 11:01

[BOJ 10830] 행렬 제곱(C++)

행렬 제곱(Gold 4) 문제 전체 문제 보기 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근법 이번 문제는 행렬의 거듭제곱을 최적화하는 문제입니다. 우선 행렬 간의 곱셈은 다음과 같이 3중 for문을 통해서 계산할 수 있습니다. using Matrix = vector; Matrix operator*(const Matrix& lhs, const Matrix& rhs) { int N = static_cast(lhs.size()); Matrix ret(N); for (int i = 0; i < N; ++i) { ret[i]..
Algorithms/Math 2021. 10. 8. 14:49