백트래킹

[프로그래머스 Lv.2] 피로도 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 순열을 사용하여 모든 가능한 던전의 조합을 구하고, 각 조합들을 주어진 피로도 이내에 모두 탐험할 수 있는지 체크함으로써 해결할 수 있다. 즉, 일반적인 완전 탐색 방식으로 풀 수 있는 것이다.from itertools import permutationsdef check(k, permutation): # permutation에 들어있는 던전의 순열을 k의 피로도로 모두 통과할..

(C++) 백준 15683번 - 감시

문제 링크 : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 백트래킹을 사용하여 풀이하였다. 먼저 전체 사무실에서 CCTV가 위치한 곳의 좌표를 Queue에 넣는다. 다음으로 Queue의 Front에 위치한 CCTV가 스캔할 수 있는 지역을 체크한다. 체크한 뒤 사무실의 정보와 Queue를 함수의 변수로 넘겨가면서 Queue가 빌 때까지 재귀적으로 진행한다. #include #include #include #define X f..

(C++) 백준 15657번 - N과 M (8)

문제 링크 : https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 입력받은 수들을 정렬한 후 배열에 들어올 수가 이전에 배열에 삽입된 수보다 작지 않도록 조건만 달아주면 쉽게 풀 수 있다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int i..

(C++) 백준 15656번 - N과 M (7)

문제 링크 : https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 아주 간단한 백트래킹 문제로 N과 M (3) 문제처럼 특별한 조건이 없기에 다른 백트래킹 문제에 익숙하다면 어렵지 않게 풀 수 있는 문제이다. 입력받은 수들을 정렬한 후에 N과 M (3) 문제와 같이 풀이하면 된다. #include #include using namespace std; int n, m; int arr[10]; // ..

(C++) 백준 15655번 - N과 M (6)

문제 링크 : https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용한 풀이이다. 정렬을 한 후에 백트래킹을 하면서 이전에 들어간 수보다 들어갈 수가 더 적다면 그 경우는 건너뛰는 식으로 구현한다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int isUsed[..

(C++) 백준 15654번 - N과 M (5)

문제 풀이 : https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. N과 M (1)과 따로 입력값을 정렬해야 한다는 점만 제외하면 거의 동일한 문제이다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int isUsed[10]; void nNm(i..

(C++) 백준 15652번 - N과 M (4)

문제 링크 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 배열에 들어올 수가 이전에 배열에 삽입된 수보다 작지 않도록 조건만 달아주면 쉽게 풀 수 있다. #include using namespace std; int n, m; int arr[10]; void nNm(int idx){ if(idx == m){ // base condition for(int i = 0; i < m; i++){ cout..

(C++) 백준 15651번 - N과 M (3)

문제 링크 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 아주 간단한 백트래킹 문제로 특별한 조건이 없기에 다른 백트래킹 문제에 익숙하다면 어렵지 않게 풀 수 있는 문제이다. #include using namespace std; int n, m; int arr[10]; int isUsed[10]; void nNm(int idx){ if(idx == m){ // base condition for(..

(C++) 백준 15650번 - N과 M (2)

문제 링크 : https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹을 사용한 풀이이다. 백트래킹을 하면서 이전에 들어간 수보다 들어갈 수가 더 적다면 그 경우는 건너뛰는 식으로 구현한다. #include using namespace std; int n, m; int arr[10]; int isUsed[10]; void nNm(int idx){ if(idx == m){ // base condition for(int i = 0; i..

(C++) 백준 1182번 - 부분수열의 합

문제 링크 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 백트래킹을 활용하여 풀이하였다. 부분수열에 숫자 하나를 포함하거나 포함하지 않거나 하는 경우를 모두 시도하여 조건에 맞는 경우를 카운트하는 식으로 풀이하였다. #include using namespace std; int n, s, tmp, size, cnt; int num[20]; int used[20]; void subseqadd(int i..