본문 바로가기
반응형

백트래킹5

[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.
[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.
43. 프로젝트 오일러 #43 : 부분 문자열 나누어 떨어지기 이번 문제도 간단한 문제입니다. (난이도 5%) 문제 자체는 팬디지털(0~9까지의 숫자를 한번씩만 쓴 숫자)의 부분 문자열이 특정 소수로 나누어지는 가를 판별하면 됩니다. 가장 손쉽게 구현할 수 있는 방법은 백트랙킹(back tracking) 방법을 사용합니다. 속도를 조금이라도 빠르게 하기 위해서 숫자를 만들 때, 세개의 숫자를 쓰는 것이 아니라, 기존의 값에 10을 곱한 후 새로운 값을 더하는 방식으로 구현했습니다. (사실 그다지 이것에 의해서 속도 차이가 발생하지는 않을겁니다.) 간단한 형태의 자기호출 함수를 사용해서 만들었습니다. 소스에 대한 설명은 굳이 필요하지는 않을 듯 하네요. #include #include uint64_t SumPD(uint64_t n, int mask, int t); i.. 2016. 5. 25.
728x90

티스토리툴바