본문 바로가기

Set3

[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.
[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++] 백준 #2210 숫자판 점프(집합, 백트래킹) #2210은 실버 문제로 난이도는 높지 않습니다. 백트래킹 알고리즘을 이용해서 모든 경우의 수를 찾아내었고, 집합을 이용해서 중복을 제거해서 풀었습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 기본적으로 2차원 배열에서 백트래킹은 경계조건하고 상하좌우 움직임 등만 잘 처리하면 큰 무리가 없습니다. 집합 자료구조는 C++에서 제공하는 것이 두가지인데, 일반 집합 자료구조는 se.. 2023. 4. 17.

티스토리툴바