반응형 Programming/Project Euler108 [C/C++] 프로젝트 오일러 #103 Special Subset Sums: Optimum(백트래킹) Project Euler #103: Special Subset Sums: Optimum이 문제는 “특수 부분집합”의 성질과 최적의 집합을 찾는 문제입니다.문제 설명1. 집합 S에 대해, S의 모든 부분집합이 서로 다른 합을 가져야 합니다.• 즉, S의 두 부분집합 A, B에 대해 \( \text{sum}(A) \neq \text{sum}(B) \) 여야 합니다.• 여기서 집합 A와 B는 같은 원소가 존재하지 말아야 합니다 (\( A \cap B = \emptyset \)).2. S의 부분집합이 특정 조건을 만족해야 합니다:• \( |A| > |B| \) 이면 \( \text{sum}(A) > \text{sum}(B) \) 여야 합니다. (\( |A| \) 는 부분집합 A의 원소 개수)3. S의 크.. 2024. 11. 24. [C/C++] 프로젝트 오일러 #102 Triangle Containment(수학) 프로젝트 오일러 문제 #102, “Triangle Containment”은 기하학과 좌표를 활용한 문제로, 수학적 사고와 프로그래밍 기술을 결합하여 해결해야 하는 문제입니다. 난이도는 15%로 평가되고 있으며, 특히 2D 좌표평면에서 삼각형과 점의 관계를 다루는 문제를 즐기는 이들에게 적합합니다.이 문제의 기본적인 목표는 주어진 수많은 삼각형들 중에서 원점(0, 0)이 포함된 삼각형의 개수를 찾는 것입니다. 각 삼각형은 세 점의 좌표로 표현되며, 파일에 저장된 데이터를 읽어와 이를 처리해야 합니다. 원점이 특정 삼각형 내부에 포함되어 있는지를 확인하기 위해서는 벡터와 내적, 교차곱 등의 기하학적 개념을 활용하거나, 삼각형의 넓이를 비교하는 방식 등 다양한 접근법을 사용할 수 있습니다.이 문제는 단순히 원.. 2024. 11. 23. [C/C++] 프로젝트 오일러 #101 Optimum Polynomial(다항식) 이 문제는 수학적 규칙을 따르는 점열(sequence)을 생성하는 다항식(polynomial)과 관련이 있습니다. 문제를 해결하기 위해 주어진 점열을 분석하고, 다항식의 특성을 활용하여 최적의 다항식을 찾는 것이 핵심입니다.문제 이해1. 점열의 생성문제는 특정한 다항식 \( U(n) \)을 통해 생성된 점열이 주어질 때, 이 점열을 근사하는 최적의 다항식을 찾는 것입니다. 점열의 각 항은 다음과 같은 형태를 가집니다: \( u(n) = U(n) \) 여기서 \( U(n) \) 은 n-차 다항식입니다.예를 들어, \( U(n) = n^3 - 2n^2 + n \) 일 경우, \( u(1) = 0, u(2) = 6, u(3) = 24, \dots \) 와 같은 점열이 생성됩니다. 2. 부분 점열문제는 \.. 2024. 11. 22. [C/C++] 프로젝트 오일러 #100 Arranged Probability(수학) 프로젝트 오일러 100번째 문제네요. Project Euler #100: Arranged Probability 문제는 확률과 이항 계수를 기반으로 한 수학적 사고를 요구하는 문제입니다. 이 문제의 주요 목표는 특수한 조건을 만족하는 정수 쌍을 찾는 것입니다. 문제를 이해하기 위해 배경과 개념을 먼저 살펴보겠습니다.문제는 다음과 같이 설정됩니다. 특정 “파란색”과 “총 디스크”의 개수가 주어졌을 때, 한 번 무작위로 디스크를 두 개 뽑는 경우, 둘 다 파란색일 확률이 정확히 1/2가 되는 조건을 만족하도록 하는 디스크의 배치를 찾는 것이 목적입니다.우선 기본적인 수식으로 표현해 봅시다.• 파란색 디스크의 개수를 b, 총 디스크의 개수를 n이라고 하겠습니다.• 두 개의 디스크를 뽑는 확률에서 둘 다 파란색일.. 2024. 11. 21. [C/C++] 프로젝트 오일러 #99 Largest Exponential(수학) 문제는 여러 쌍의 숫자로 이루어진 데이터에서 각 쌍이 \(a^b\) 형태로 표현될 때, 가장 큰 값을 가지는 쌍의 위치를 찾는 것입니다. 여기서 a와 b는 양의 정수입니다.예를 들어, 다음과 같은 쌍이 있다고 가정합니다:1. \(2^{11}\)2. \(3^7\)3. \(6^3\)각각의 값을 계산하면:• \( 2^{11} = 2048 \)• \( 3^7 = 2187 \)• \( 6^3 = 216 \)이 중에서 가장 큰 값은 2187이므로, 두 번째 쌍 (3, 7)이 답이 됩니다. 이 경우 결과는 2번째 줄을 나타냅니다.문제가 간단하게 보여도 제곱해야 하는 수가 크면, 실제 값의 크기는 컴퓨터로 계산하기 힘듭니다. \( 632382^{518061} \gt 519432^{525806} \) 의 경우와 같이 밑.. 2024. 11. 21. [C/C++] 프로젝트 오일러 #98 Anagramic Squares(완전 탐색) Project Euler 문제 98번은 “아나그램 수의 쌍”에 관한 문제입니다. 문제는 다음과 같은 상황을 제시합니다.먼저, 아나그램이란 한 단어의 문자들을 재배열하여 다른 단어를 형성하는 것을 말합니다. 예를 들어, “LISTEN”과 “SILENT”은 서로 아나그램입니다. 이 문제에서는 단어 목록이 제공되며, 이 목록에서 아나그램 쌍을 찾아야 합니다.여기에서 한 걸음 더 나아가, 아나그램 쌍에 특정 조건을 부과합니다. 각 아나그램 단어 쌍에 대해, 이를 숫자로 매핑하여 정사각형 수가 되도록 만들어야 합니다. 예를 들어, “CARE”와 “RACE”가 아나그램이라면, “CARE”를 숫자 1296으로, “RACE”를 숫자 9216으로 매핑했을 때 둘 다 정사각형 수라면 유효한 쌍이 됩니다.문제는 주어진 단어.. 2024. 11. 20. 이전 1 2 3 4 ··· 18 다음 728x90
