728x90 C++/백준 DFS5 [c++] 2048 (Easy) (12100), 반례모음, DFS, 백트래킹, 재귀 문제https://www.acmicpc.net/problem/12100 열받아서 반례를 다 모아봤어요 반례모음 3 2 2 2 4 4 4 8 8 8 =>16 2 8 16 16 8 =>16 4 8 16 0 0 0 0 16 8 0 0 0 0 0 0 0 0 =>32 4 0 0 0 0 4 0 0 0 8 32 4 0 8 8 4 0 ->64 1 16 => 16 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 =>32 5 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 4 0 2 2 -> 32 5 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 2 2 2 2 0 4 2 -> 32 5 2 2 2 2 2 4 2 2 2 2 0 0 0 0 0 2 2 2 2 2 2 2 2.. 2023. 10. 10. [c++] N과 M(1~12) 유형별 정리, 백트래킹, DFS, 재귀 중복 선택 제외시 : check 필요(사용했다는 것을 기록) 오름차순/비내림차순 : 재귀 반복시 시작 범위 지정 필요 i=k //k=상태 번호 중복 선택 포함시 : check 필요 없음 중복 선택 + 오름차순/비내림차순 : 재귀 반복시 시작 범위 지정 필요 i=st int st = 0; if (k != 0) st = arr[k-1]; // 비내림차순일 경우 // if (k != 0) st = arr[k-1] + 1; // 오름차순일 경우 수열 숫자들이 주어질 시에 : sort(arr, arr+N)으로 정렬 후 수행해야 한다. 수열 숫자들에서 중복된 수가 존재시 : ex) 9 5 9 7 // 정렬 후 각 상태에서 tmp로 이전 값을 저장한 후, 다음 값 선택시 비교해서 동일하면 제외하도록 해야 한다. 아래.. 2023. 10. 9. [c++] N과 M(9) (15663), 백트래킹, 재귀, DFS 문제 https://www.acmicpc.net/problem/15663 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 4 4 2 예제 출력 1 복사 2 4 예제 입력 2 복사 4 2 9 7 9 1 예.. 2023. 10. 9. [c++] 부분수열의 합(1182), 백트래킹, dfs, 재귀 문제 https://www.acmicpc.net/problem/1182 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 예제 입력 1 복사 5 0 -7 -3 -2 5 8 예제 출력 1 복사 1 풀이 재귀적으로 DFS 수행, 트리 한쪽의 끝까지 도달한 후 return하면서 수행한다. - check[] 배열.. 2023. 10. 8. [C++] 백준 N-Qeen (9663), 재귀, DFS, 백트래킹 문제 https://www.acmicpc.net/problem/9663 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 복사 8 예제 출력 1 복사 92 풀이 이전 Queen들의 이동 방향성을 체크하는 것이 주된 키 2차 배열로 모두 체크하는 것 보다, 경향(기울기)을 파악해서 1차원으로 체크하면 O(1)로 체킹할 수 있다. 백트래킹을 이용하여 재귀적으로 DFS를 수행한다. 코드 알게 된 점 백트래킹을 통한 재귀의 과정에 대해서 .. 2023. 10. 8. 이전 1 다음 728x90
