반응형 백트래킹18 백트래킹 vs DFS 알고리즘 문제를 풀다보면 DFS인 것 같은데 백트래킹으로 분류된 문제들이 있다. 헷갈린 부분이 있어서 이번 기회에 확실히 정리를 하고 넘어가고자 한다. * DFS (깊이 우선 탐색) 가능한 모든 경로를 다 탐색한다. 따라서, 불필요한 경로도 무조건 끝까지 탐색을 하기 때문에 경우의 수를 줄이지는 못한다. * 백트래킹 (Back-tracking) 답을 찾아가는 도중, 지금의 경로가 답이 될 것 같지 않으면 더이상 진행하지 않고 윗단계로 되돌아간다. 이를 가지치기라고 하는데, 불필요한 경우의 수를 줄일 수 있으므로 시간복잡도를 개선할 수 있다. 문제풀이에서는 DFS로 모든 경우의 수를 완전탐색하는 과정 중에 조건문을 걸어서 답이 절대로 나올 수 없는 상황을 정의하고, 해당이 되면 탐색 중단 후 그 이전으로 .. 2023. 2. 19. [백준] 2023번 - 신기한 소수 (Java)(△) https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 1. 신기한 소수란? 왼쪽부터 1자리, 2자리.... N자리까지 모두 소수인 수 예) 7331 : 7 - 73 - 733 - 7331 모두 소수이다. 2. N자리가 주어졌을 때 신기한 소수를 모두 찾아서 출력하자. 3. 입력범위가 N : 1 ~ 8이다. DFS 백트래킹으로 풀이가 가능하다. * 재귀함수 구현 1. 중복숫자 허용함(방문배열 사용X) 2. 순서다르면 다른 조합으로 인정 (i.. 2023. 1. 26. [백준] 6603번 - 로또 (Java) 1. 줄의 첫 숫자가 N이고, 뒤부터 로또에 사용될 정수들이 배열이 입력된다. 2. 중복방문을 허용하지 않는다. (방문배열 사용) 3. 순서가 바꾸어도 동일 조합으로 인정한다. (i=start부터 시작) 4. 종료조건은 level == N이다. import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; import java.util.HashSet; public class Main { static int N, S; static int sum = 0, count = 0; static int A[]; static int Ans[]; static boolean visited[]; void DFS(int start, int .. 2022. 12. 11. [백준] 1182번 - 부분수열의 합 (Java) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 종료조건은 tree level이 N까지 진행될 때이다. 2. 합이 S가 되면 count +1을 한다. - 합이 S가 되더라도 탐색은 계속 진행한다. 3. 모든 탐색이 끝나면 count를 출력한다. 4. 부분집합을 구하는 것이기 때문에 지금 수(A[i])를 더하거나 더하지 않는 수, 2가지 경우의 수로 나뉜다. - 현재 수(A[level])를 더하고 다음 l.. 2022. 12. 11. [백준] 15666번 - N과 M(12) (Java) https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복방문 허용함. (방문배열 사용X) 2. 순서다른 조합 허용안함. (i = start부터 시작) 3. 중복 조합 허용안함. (HashSet으로 포함 확인 후 제거) import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; import java.util.HashSet; public class Mai.. 2022. 12. 10. [백준] 15665번 - N과 M(11) (Java) https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복방문 허용함 (방문배열 사용X) 2. 순서다른 조합 허용함 (i = 0 부터 시작) 3. 중복 조합 허용안함 (HashSet으로 체크 후 제거) import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; import java.util.HashSet; public class Main { static.. 2022. 12. 10. [백준] 15664번 - N과 M(10) (Java) https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 입력받은 정수배열만 사용해야 함. 2. 중복수열 허용안함 (방문배열 사용함) 3. 순서 바뀌면 다른 조합으로 인정안함(i = start 부터 시작) 4. 입력 배열 중 같은 숫자가 있으면 중복 방문은 아니지만 같은 조합이므로 한번만 출력해야 함. - HashSet을 사용해서 중복 문자열이 있으면 머지하지 않고 스킵하도록 구현함. import java.util.Scanner; import .. 2022. 12. 10. [백준] 15663번 - N과 M(9) (Java) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 입력받은 정수배열만 사용해야 함. 2. 중복수열 허용안함 (방문배열 사용함) 3. 순서 바뀌면 다른 조합으로 인정(i = 0 부터 시작) 4. 입력 배열 중 같은 숫자가 있으면 중복 방문은 아니지만 같은 조합이므로 한번만 출력해야 함. - HashSet을 사용해서 중복 문자열이 있으면 머지하지 않고 스킵하도록 구현함. import java.util.Scanner; import java.ut.. 2022. 12. 10. [백준] 15657번 - N과 M(8) (Java) https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 정수 배열을 사용해야 한다. 2. 중복방문 허용함. (방문배열 사용X) 2. 순서 바뀌어도 다른 조합인정 안함(i=start로 시작함) import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; public class Main { static int N, M; static int A[].. 2022. 12. 10. 이전 1 2 다음 반응형
