본문 바로가기
반응형

알고리즘 PS/DFS15

[백준] 13023번 - ABCDE (Java)(△) https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 인접리스트 방식으로 입력값을 저장한다. 2. 중복값을 값을 허용하지 않기 때문에 방문배열을 사용한다. 3. 친구관계는 A-B, B-C, C-D, D-E로 4개로 고정이 되어 있다. 따라서 호출 level이 5가 되면 친구관계를 다 찾은 것이다. 5. level == 5이면 더 이상 다른 친구관계를 찾을 필요없이(가지치기) 1을 출력하고 종료하면 된다. 6. 그래프의 시간복잡도 O(V + E)이므로 2,000 + 2,000 = 4,000, 모든 노드에 대한 탐색은 4,000 * 2,000 = 8,0.. 2023. 1. 26.
[백준] 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.
[백준] 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.
[백준] 15656번 - N과 M(7) (Java) https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 배열은 DFS 탐색을 하기전에 오름차순으로 먼저 정렬을 한다. 2. 중복방문을 허용하기 때문에 방문배열은 사용하지 않는다. 3. 순서가 바뀌면 다른 조합으로 인식한다. - for (i = 0 to N)으로 해서 새로운 탐색을 할 때 처음부터 다시 시작한다. import java.util.Scanner; import java.util.Arrays; import java.lan.. 2022. 12. 9.
[백준] 15655번 - N과 M(6) (Java) https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 숫자를 수열로 출력한다. 2. 중복을 허용하지 않는다. - 방문배열을 사용해서 방문하지 않은 수라면 조합에 사용하고 방문처리한다. - level을 하나 높여서 재귀함수 호출한다. - 재귀 호출에서 돌아오면 방문처리를 리셋한다. 3. 순서가 바뀌어도 동일조합으로 인식한다. - for (i = start to N)으로 사용한다. - DFS(i, level+1)을 한다. impo.. 2022. 12. 9.
반응형

티스토리툴바