Algorithm/완전탐색

BOJ 15665 - N과 M (11)

15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복을 허용하여 M개를 골라서 순서있게 나열하는 중복순열 문제이다. N개의 수 중 중복되는 수가 있을 수 있다는 사실을 알아야 한다. N이 1 7 9 9 이고 M이 2인 경우를 생각해보자 중복을 허용하여 순서있게 나열하면 다음과 같다 1 1 1 7 1 9 1 9 7 1 7 7 7 9 7 9 9 1 9 7 9 9 9 9 9 1 9 7 9 9 9 9 문제의 조건이 중복되는 수열은 출력하지 않는 것이므로 LinkedHashSet에..

BOJ 15664 - N과 M (10)

15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 N개의 자연수 중 M개를 중복없이 골라서 순서있게 나열하는 순열문제이다. 여기에 비내림차순이어야 하므로 N개의 수를 정렬한 후 prev 인자를 통해 k번째 다음 자리인 k+1번 자리는 prev +1부터 탐색할 수 있도록 설정해준다. 여기서 N개의 숫자가 같은 것이 있을 경우를 생각해야 한다. N개의 숫자가 9 7 9 1 이고 M이 2인 경우를 생각해보자 정렬을 하고 순열을 구해보면 다음과 같다. 1 7 1 9 1 9 7 9 7 9 9 9 여기서 ..

BOJ 15663 - N과 M (9)

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 기존 중복을 허용하지 않고 순서있게 고르는 순열문제와 동일하지만 이번에는 N개의 수가 전부 다른 수가 아닐 수도 있기 때문에 좀 더 생각을 해봐야 한다. 만약 N개의 수가 1 4 4일 때, 중복을 허용하지 않고 2개를 순서있게 고르면 다음과 같다. 1 4 1 4 4 4 이렇게 되면 1 4가 중복되게 출력되는데 문제에서 중복 출력은 없도록 하라고 했으니 이걸 중복을 제거해주고 입력 ..

BOJ 15657 - N과 M (8)

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복을 허용하여 M개를 골라야 하고 비내림차순이어야 한다. 각 자리에서 백트래킹으로 모든 경우의 수를 탐색하는 완전탐색 문제이다. 그 중 중복을 허용하여 순서있게 고르는 것이므로 중복순열 문제이다. 재귀함수의 매개변수로 prev를 넘겨줘서 각 경우의 prev에 해당하는 숫자부터 탐색을 시작하도록 설정하면 (k자리의 숫자)

BOJ 15656 - N과 M (7)

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복을 허용하여 M개를 순서있게 나열하는 중복순열 문제이다. 각 자리에서 다음 자리에 올 수 있는 모든 경우의 수를 탐색한다. 2. 시간복잡도 중복순열 문제이므로 N개 중 M개의 자리를 뽑는 것과 같으므로 시간복잡도는 O(N^M)이다. N과 M의 최댓값은 7이므로 7^7 < 1초라서 가능한 풀이법이다. 3. 구현 import java.io.*; impo..

BOJ 15654 - N과 M (6)

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 아이디어 N개의 자연수 중에서 중복 없이 M개를 순서있게 나열하는 완전탐색의 순열문제이다. 각 자리에서 재귀호출로 다음 자리에 올 수 있는 모든 경우의 수를 탐색한다. 단, 중복을 허용해야 하고, 오름차순이어야 하므로 재귀함수에 prev인자를 넘겨줘서 다음 자리는 prev+1부터 탐색하게 하여 오름차순이 되도록 설계한다. N개의 자연수는 모두 다른 수이므로 prev인자를 통해 중복도..

BOJ 14888 - 연산자 끼워넣기

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 1. 아이디어 주어진 수열의 순서는 바뀌지 않으므로 그 사이사이 연산자만 끼워넣으면 된다. N-1개의 연산자를 중복 없이 순서있게 나열하여 모든 경우의 수를 탐색하는 완전탐색 문제이다. 모든 경우를 탐색하면서 최댓값/최솟값이 되는 경우의 연산자 조합을 찾는다. 2. 시간복잡도 완전탐색으로 구현하면 중복없이 순서있게 나열하는 순열문제이므로 O(..

[완전탐색] BOJ 15654 N과 M (5)

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1) 아이디어 N개의 숫자 중 중복없이 M개를 순서 있게 나열하는 문제이기 때문에 완전탐색의 순열 문제이다. 각 자리에서 재귀호출로 다음 자리로 올 수 있는 모든 경우의 수를 백트래킹으로 탐색하면 된다. 단, 중복을 허용하지 않으므로 visit[]으로 방문처리를 해서 방문안해본 경우만 탐색한다. 2) 시간복잡도 순열 문제이므로 O(N^M)인데 N과 M의 최댓값이 8 이므로 O(8^8) < 1억 3) 구현 // 언어 : JAVA , (성공/실패) : 1/0..

[Algorithm] 완전탐색 - 조합

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 완전 탐색 문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다. 장점 : 부분 점수를 얻기 좋음 단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음 완점 탐색 종류 N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 N개중 중복없이 M개를 순서 있게 나열하기 : 순열 N개중 중복을 허용하여 M개를 고르기 : 중복조합 N개중 중복없이 M개를 고르기 : 조합 완전 탐색 문제 접근 시 고를 수 있는 값의 종류 파악 중복 여부 순서를 따지는 지 N개중 중복없이 M개를 고르기 : 조합 백준 15652) N과 M (2) htt..

[Algorithm] 완전탐색 - 중복조합

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 완전 탐색 문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다. 장점 : 부분 점수를 얻기 좋음 단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음 완점 탐색 종류 N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 N개중 중복없이 M개를 순서 있게 나열하기 : 순열 N개중 중복을 허용하여 M개를 고르기 : 중복조합 N개중 중복없이 M개를 고르기 : 조합 완전 탐색 문제 접근 시 고를 수 있는 값의 종류 파악 중복 여부 순서를 따지는 지 N개중 중복을 허용하여 M개를 고르기 : 중복조합 백준 15652) N과 M (..