본문 바로가기
반응형

백트래킹8

[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.
[C/C++] 백준 #2239 스도쿠(백트래킹) #2239 스도쿠 문제는 고전적인 백트래킹을 사용해서 푸는 문제입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 스도쿠는 가로와 세로가 각각 9칸을 가지고 있는 숫자 퍼즐입니다. 스도쿠의 숫자는 법칙이 있는데, 각각의 가로줄에 1부터 9까지의 숫자가 오직 한번씩만 사용되어야 하고, 각각의 세로줄에도 같은 법칙이 성립합니다. 그리고 3x3 짜리 작은 정사각형 안에도 1부터 9까지의 숫자가 오직 한번씩만 사용되어야 .. 2023. 4. 18.
728x90

티스토리툴바