반응형 Programming406 [C/C++] 백준 #2312 수 복원하기(수학) 소인수 분해하는 것은 어렵지 않게 할 수는 있습니다. 물론 소수를 구해서 하면 더 좋겠지만, 소수를 별도로 구하지 않아도 소인수 분해를 할 수 있습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 소인수 분해를 할 때에는 n의 숫자의 제곱근까지만 하면 됩니다. 예를 들어서 12를 소인수 분해하기 위해서는 2부터 시작합니다. 12의 제곱근은 3보다는 크고 4보다는 작겠죠. 즉, 3까지만 하면 됩니다. 하지만, 제 알고리즘은 그 전에 끝나게 됩니다. 12를 2로 계속 나누면, 2번 나눌 수 .. 2023. 4. 20. [C/C++] 백준 #2302 극장 좌석(동적 계획법) #2302 극장 좌석 문제는 수학적인 원리를 이해하면 풀기 편합니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석은 일렬로 최대 40개까지 있을 수 있습니다. 이 중 몇개의 좌석은 이미 고정석으로 채워져 있을 때, 1부터 N까지의 숫자를 채우는 경우의 수를 구하는 문제입니다. 단, 모든 숫자는 자신의 자리 번호와 그 옆자리로 이동을 할 수 있지만, 고정석으로는 이동할 수 없습니다. 극장 자리는 아래와 같이 표시될 수 있습니.. 2023. 4. 20. [C/C++] 백준 #2294 동전 2(동적 계획법) #2294 동전 문제도 #2293 동전 문제와 비섯합니다. 단, 가치가 같은 동전이 주어질 수 있다는 것 뿐으로 크게 고려 대상은 아닙니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 참고할 수 있는 이전 문제 링크입니다. https://sdev.tistory.com/1333 [C/C++] 백준 #2293 동전 1(동적 계획법) 동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 .. 2023. 4. 20. [C/C++] 백준 #2293 동전 1(동적 계획법) 동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 계획법을 이용하는 대표적 문제 중 하나입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 주어진 K원을 만들기 위해서는 동전의 종류를 먼저 조절해야 합니다. 서로 다른 동전의 종류가 n개가 있다면, 우리는 동적 계획법의 변수 \(d_{n, k}\)를 정의하도록 합니다. n개의 동전을 가지고 k 금액을 만드는 경우의 수로 정의토록 합니다. 이렇게 하면 다음과 갈은.. 2023. 4. 20. [C/C++] 백준 #2290 LCD Test(구현) #2290 LCD Test는 단순하게 구현만 하면 되는 문제로, 특별한 알고리즘이 필요치 않습니다. 테이블을 만들어서 하면 좋을 듯 합니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2290 2290번: LCD Test 첫째 줄에 두 개의 정수 s와 n이 들어온다. (1 ≤ s ≤ 10, 0 ≤ n ≤ 9,999,999,999)이다. n은 LCD 모니터에 나타내야 할 수 이며, s는 크기이다. www.acmicpc.net 사실 이 문제는 LCD라고 되어 있지만, 7 segment LED라는 소자를 이용한 글쓰기와 같습니다. s 값에 따라 두께를 조절해야 하는 것이 좀 까다롭습니다. 제가 작성한 소스는 다음과 같습니다. //--------------------------.. 2023. 4. 20. [C/C++] 백준 #2268 수들의 합 7(세그먼트 트리) 백준에 유달리 세그먼트 트리를 이용한 문제가 많습니다. 한동안 난이도는 플래티넘 등급이었는데, 이제는 골드 등급으로 설정되어 있습니다. 그만큼 보편화된 알고리즘이라고 생각하시면 될 듯 합니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2268 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 세그먼트 트리는 쿼리가 2종류(읽기 쿼리, 쓰기 쿼리) 이상이 존재하며, 쿼리의 수가 많을 때 사용합니다. 읽기 쿼리와 쓰기 쿼리는 서로 반대되는 개.. 2023. 4. 19. 이전 1 ··· 6 7 8 9 10 11 12 ··· 68 다음 728x90
