본문 바로가기

Algorithm/백트래킹7

[백준] 9663 N-Queen c++ 문제 링크 https://www.acmicpc.net/problem/9663 KEY 퀸을 서로 공격하지 않게 하기 위해서는 퀸을 같은 행, 열, 대각선에 놓지 않아야 한다. (0~마지막 행) 까지 모든 행을 조사하면서 에 맞는 퀸의 위치가 나올 경우 다음 행으로 넘어간다. 만약에 에 맞지 않을 경우 현재 행의 다음 열로 가서 에 부합하는지 확인한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include #include #include using namespace std; const int MAX = 15; int n; i.. 2023. 3. 9.
[백준] 10819 차이를 최대로 c++ 문제 링크 https://www.acmicpc.net/problem/10819 KEY 다른 유형과 별 다를 거 없는 간단한 백트래킹 문제이다. 그리디로 풀 수 있는지 계속 보다가, 마땅히 떠오르지 않아서 완전탐색을 하기로 결정했다. DFS재귀함수를 이용한 방법, 헤더가 지원하는 next_permutation메서드를 사용한 방법 두가지로 풀이했다. next_permutation을 이용한 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #include #include #include using namespace std; int n; vector arr; .. 2023. 3. 9.
[백준] 6603 로또 c++ 문제 링크 https://www.acmicpc.net/problem/6603 KEY 일반적인 백트래킹 문제로, 어렵지 않게 풀 수 있다. DFS종료 조건 : 결과 출력 배열(result)의 크기가 6이되면 출력하도록 하면 된다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include #include #include #include using namespace std; const int MAX = 50; int k; int arr[MAX]; vector result; //결과 출력 배열 void dfs(int idx) { i.. 2023. 3. 8.
[백준] 1759 암호 만들기 c++ 문제 링크 https://www.acmicpc.net/problem/1759 KEY 일반적인 백트래킹 기법에 조건을 체크하는 것이 추가된 문제이다. DFS로 완전탐색을 하다가 임시배열의 크기가 l이 되면 문제조건을 체크한 후, 출력한다. 사전 순 출력은 DFS탐색 전에 sort로 해결하였다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include #include #include #include #include using namespace std; const int .. 2023. 3. 7.
[백준] 1182 부분수열의 합 c++ 문제 링크 https://www.acmicpc.net/problem/1182 KEY 부분 수열은 자기 자신을 넣거나, 빼어 만드는 수열로, 2^n가지를 만들 수 있다. 따라서 이 문제 역시 자기 자신을 넣고 DFS를 할 것인지, 빼고 DFS를 할 것인지를 모두 고려하면 된다. 주의사항은 가령 -1 1 -3 3 수열에 목표값이 0이라고 할 때, 0이 되는 값을 찾았다고 해서 리턴을 하게 되면 (-1,1),(-3,3)만을 찾은 후 리턴하여 (-1,1,-3,3)을 찾지 못하게 된다. 따라서 idx가 n이 될때 리턴하도록 종료조건을 만든다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #inc.. 2023. 3. 7.
[백준] 14888 연산자 끼워넣기 c++ 문제 링크 https://www.acmicpc.net/problem/14888 Key +,-,*,/ 4가지의 연산기호를 인자로 받는 DFS함수를 만든다. 완전탐색을 하다가 카운트가 n이 되면 최대값과 최솟값을 구해주면 된다. 이 유형의 문제들은 보통 이런식으로 모든 연산에 대한 DFS를 탐색하는 식으로 이루어진다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include #include #include using namespace std; const int MAX = 12; int n; .. 2023. 3. 6.

티스토리툴바