조합7 [C/C++] 프로젝트 오일러 #114 Counting Block Combinations I (조합) 프로젝트 오일러 114번 문제는 길이가 n인 일렬의 칸에 일정한 조건을 만족하도록 빨간 블록을 배치하는 방법의 수를 세는 것에 관한 문제입니다. 이 때 사용되는 빨간 블록은 최소 3칸 이상의 길이를 가져야 하며, 빨간 블록들 사이에는 적어도 하나 이상의 검은 칸이 존재해야 합니다. 또한, 빨간 블록을 전혀 놓지 않는 경우도 하나의 가능한 배치로 포함합니다.문제에서 정의하는 함수 f(n)은 길이가 n인 칸에 위와 같은 규칙을 적용했을 때 나올 수 있는 모든 가능한 배치의 수를 나타냅니다. 주어진 예시로, n=7일 때 f(7)의 값이 특정 수(17)로 제시되며, f(50)의 값도 매우 큰 수(16475640049)로 주어집니다. 문제는 이러한 함수 f(n)의 값을 확장해 나갈 때, f(n)이 1,000,00.. 2024. 12. 18. [C/C++] 프로젝트 오일러 #113 Non-bouncy Numbers(수학) Project Euler 문제 113번은 숫자가 “증가형(increasing)” 혹은 “감소형(decreasing)” 형태인 ‘비탄력적(non-bouncy)’ 수의 개수를 구하는 문제입니다. 이 문제의 핵심 개념을 다음과 같이 정리할 수 있습니다. 1. 증가하는 수(Increasing number): 왼쪽에서 오른쪽으로 읽을 때, 각 자리수가 이전 자리수보다 작아지지 않는(즉, 비내림(non-decreasing) 순서) 수를 말합니다. 예를 들어, 112233이나 8999는 모두 증가하는 수에 해당합니다. 2. 감소하는 수(Decreasing number): 왼쪽에서 오른쪽으로 읽을 때, 각 자리수가 이전 자리수보다 커지지 않는(즉, 비내림(non-increasing) 순서) 수를 의미합니다. 예를 들어.. 2024. 12. 13. [C/C++] 프로젝트 오일러 #106 Special Subset Sums: Meta-testing(점화식) Project Euler #106: Special Subset Sums: Meta-testing 문제는 주어진 집합에서 두 개의 부분집합을 비교할 때, 그 부분집합들이 특정 조건을 만족하는지를 검사하는 경우의 수를 구하는 문제입니다.문제를 간단히 설명하면,1. 집합: 크기 n 인 자연수 집합 \( \{1, 2, 3, \dots, n\} \)가 주어진다.2. 부분집합 조건: 두 부분집합 A 와 B 가 다음 조건을 만족하는지 확인해야 한다:• \( |A| = |B| \) (부분집합의 크기가 동일해야 한다.)• A와 B가 서로 다른 부분집합이어야 한다.• A와 B의 합을 비교하는 것이 의미 있으려면, A와 B를 “비교 가능한 형태”로 만들어야 한다.• “비교 가능”하다는 것은, 두 부분집합이 항목의 순서에.. 2024. 11. 27. [Python] 백준 #2407 조합(수학) 이번 문제는 \(_nC_r\) 조합을 구하라는 것입니다. 조합을 구하는 알고리즘은 수학을 알고 있다면 손쉽게 할 수 있습니다. 단지 문제는 숫자가 커지기 때문에 BigInteger 자료형을 제공하는 파이썬이나 자바를 이용하시는 것이 편합니다. https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 저는 파이썬을 이용했습니다. \[ _nC_r = \frac{n!}{(n-r)! r!} \] 이것을 그대로 구현하였습니다. 제가 작성한 소스입니다. """ // baekjoon #2407 // - by Aubrey Choi // - created at 2019-06-27 "".. 2023. 4. 29. [C/C++] 백준 #1759 암호 만들기(조합) 이번 문제는 조합을 이용하는 것입니다. 단지 조건이 좀 들어가 있습니다. 적어도 1개의 모음과 2개의 자음이 들어가야 합니다. 사실, 조합을 구한 다음에 모음의 개수를 세면, 그 외는 모두 자음이기때문에 손쉽게 풀 수 있습니다. 저는 재귀함수를 이용해서 풀었습니다. 모음의 개수를 따로 세어서 마지막에 검사를 했습니다. 재귀 함수를 사용하여 조합을 만들 수 있다면, 어렵지 않게 풀 수 있는 문제입니다. 암호의 길이가 길다면, 모음을 검사하는 비용이 클 수가 있기 때문에 주의가 필요하겠죠. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------------- // baekjoon #1759 - Making password.. 2022. 10. 11. [C/C++] 백준 #1010 다리 놓기(조합) 백준 #1010 다리 놓기 문제는 수학 중 확통의 경우의 수에 어느정도 개념이 있어야 풀 수 있는 문제입니다. 강을 사이로 왼쪽에는 N 개의 지역, 오른쪽에는 M 개의 지역이 있습니다. 이 N개의 지역에 하나씩 다리를 놓아서 오른쪽에 있는 M개의 지역을 연결하고자 하는데, 다리가 서로 엇갈리지 않도록 하는 경우의 수를 물어보고 있습니다. 경우의 수를 따지는 데에는 순열과 조합이 있는데, 이와 같이 엇갈리지 않게, 즉, 항상 정해진 순서대로(또는 증가하는 순서, 감소하는 순서 등) 나열해야한다면, 이것은 조합을 선택해야 합니다. 결국 이 문제는 M개 중에서 N개를 선택하는 문제가 되겠죠. 실제 백준 문제는 다음 링크를 봐주세요.https://www.acmicpc.net/problem/1010 101.. 2019. 12. 21. 이전 1 2 다음
