본문 바로가기

백트래킹9

[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++] 프로젝트 오일러 #96 Su Doku(백트래킹) Project Euler의 96번 문제는 스도쿠 퍼즐을 해결하는 알고리즘 설계를 다루고 있습니다. 스도쿠는 9x9 격자로 이루어진 퍼즐 게임으로, 각 행, 열, 그리고 3x3의 작은 박스에 1부터 9까지의 숫자를 중복 없이 채워 넣는 것이 목표입니다. 이 문제는 단순히 하나의 스도쿠를 푸는 것이 아니라, 여러 개의 스도쿠 퍼즐을 입력받아 각각을 해결한 뒤, 각 퍼즐의 해답에서 첫 번째 세 숫자를 추출하여 합산하는 과제를 제시하고 있습니다.프로그래머의 관점에서 이 문제를 접하면, 가장 먼저 고려해야 할 점은 스도쿠 퍼즐을 효율적으로 해결할 수 있는 알고리즘입니다. 일반적으로 사람이 스도쿠를 풀 때는 규칙을 기반으로 논리적 접근을 활용합니다. 특정 위치에 들어갈 수 있는 숫자의 후보를 좁혀가는 과정을 반복하.. 2024. 11. 18.
[C/C++] 프로젝트 오일러 #93 Arithmetic Expressions(백트래킹) 프로젝트 오일러 문제 #93, Arithmetic Expressions는 네 개의 숫자를 이용해 가능한 모든 정수 값을 만들고, 그 중 가장 긴 연속된 정수 집합을 찾는 문제입니다. 이 문제의 목표는 네 개의 서로 다른 숫자를 선택한 후, 사칙연산과 괄호를 자유롭게 조합하여 만들 수 있는 모든 가능한 정수를 계산하는 것입니다. 예를 들어, 주어진 숫자가 1, 2, 3, 4라면, 이 네 숫자를 사용해 다양한 수식을 만들어내고, 그 수식을 통해 결과로 얻을 수 있는 모든 정수를 구하게 됩니다.문제의 규칙은 다음과 같습니다.1. 네 개의 숫자는 모두 서로 달라야 합니다.2. 각 숫자는 한 번만 사용할 수 있습니다.3. 사칙연산(+, -, *, /)과 괄호를 사용하여 가능한 많은 정수를 만들어냅니다.4. 음수나.. 2024. 11. 14.
[C/C++] 백준 #2661 좋은수열(백트래킹) 이번 문제는 백트래킹을 이용해서 문제를 풀었습니다.현재 위치가 올바른지 아닌지를 검사하는데, 조금 더 우수한 알고리즘을 이용했다면, 더 좋게 할 수 있겠지만, 저는 단순한 알고리즘을 이용했습니다.  더 좋은 알고리즘을 찾기 위해서 노력을 안 한 것도 있었겠지만, 글을 쓰는 시점에서 생각해도 좋은 알고리즘을 찾는 것이 쉽지는 않습니다.  https://www.acmicpc.net/problem/2661#### 1. `solve` 함수이 함수는 재귀적으로 좋은 수열을 생성하는 역할을 합니다. 함수의 매개변수는 다음과 같습니다:- `v[]`: 현재까지 생성된 수열을 저장하는 배열- `c`: 현재까지 생성된 수열의 길이- `n`: 생성하고자 하는 수열의 길이bool solve(int v[], int c, int.. 2024. 5. 30.
[C/C++] 백준 #2580 스도쿠 (백트래킹) 스도쿠는 머리를 많이 사용하는 퍼즐로 유명합니다. 기본적으로 문제를 풀기 위해서 여러가지 경우를 머리속에 담고서 진행해야 하기 때문에 쉽게 풀지를 못 하지만, 컴퓨터 프로그램의 경우는 모든 경우를 살펴볼 수 있는 알고리즘 중 대표적인 백트래킹으로 이 문제를 손쉽게 풀 수 있습니다. 대중교통을 이용해서 여행을 다닐 때, 버스 터미널 등에서 손쉽게 살 수 있는 스도쿠 문제지가 있었죠. 지금은 귀찮아서라도 잘 안 풀게 되지만요. 백준 사이트에서 문제는 다음과 같습니다. https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각.. 2023. 12. 5.
[C/C++] 백준 #2529 부등호(탐욕 알고리즘) 이번 문제는 백트래킹(back tracking) 기법을 사용하면 편하게 풀 수 있는 문제입니다. 큰 수의 경우에는 9부터 원하는 개수만큼, 작은 수의 경우에는 0부터 원하는 개수만큼 선택해서 그것으로 백트래킹을 하면 됩니다. 저는 조금 다른 식으로 풀어보았습니다. https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 바로 탐욕 알고리즘을 이용해서 큰 수가 들어가야할 위치를 찾는 것이죠. 예를 들어서 (1) (4) ... 형.. 2023. 6. 24.

티스토리툴바