[1182] 부분수열의 합
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 2 초 | 256 MB | 99180 | 44948 | 29292 | 43.323% |
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
문제 풀이
이 알고리즘의 문제풀이는 수열이 있을때 크기가 양수인 부분수열중에서 그 수열의 원소가 더한 값이 S가 되는 경우의 수를 구하는 문제이다.
S는 부분 수열을 더한 값으로 1,000,000이 넘지 않는다. N이 20개가 최대의 개수이다.
20 * 1,000,000 = 20,000,000으로 int 자료형을 사용해도 괜찮다.
부분 수열이란
이 문제를 풀기 위해 알아야되는 지식이 있다. 바로 부분 수열이다.
- 부분 문자열
- 연속성을 가진다.
- 부분 수열
- 연속성을 가지지 않아도 된다.
필요한 변수 선언 및 입력 받기
s, numbers, answer는 우리가 답을 구할 때 필요한 값으로 함수안에서 편리하게 사용하기 위해 전역변수로 선언하였다.
BufferedReader를 사용하여 입력받게 작성하였다.
class Main {
static int s;
static int[] numbers;
static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
s = Integer.parseInt(firstLine[1]);
numbers = new int[n];
String[] numberStrings = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
numbers[i] = Integer.parseInt(numberStrings[i]);
}
<-----생략---->
재귀함수를 통해 여러 경우의 수를 구하기
아래 이미지를 보면 부분 수열의 모든 경우의 수를 구할때 2^n이 드는 것을 알 수 있다.
- i번째 수를 고르는 경우와 고르지 않는 경우 총 2가지가 있는 경우이다.
Base Case
- 수열의 모든 수에 대해 뽑을지 말지 모두 판단하는 경우
Recursive Case
- i번째 숫자까지의 결정에 대해 합을 알고 있을 때
- {i + 1} 번재 수를 포함한 경우
- {i + 1} 번째 수를 포함하지 않는 경우
public static void solve(int index, int sum) {
if(index == numbers.length) return; // Base Case
if(sum + numbers[index] == s) answer++; // 조건이 만족할 때
solve(index + 1, sum + numbers[index]); // index 번째 수를 고르는 경우
solve(index + 1, sum); // index 번째 수를 고르지 않는 경우
}
위의 solve 함수가 경우의 수를 계산한다.
전체 코드
시간 복잡도: (O(2^n))
import java.io.*;
class Main {
static int s;
static int[] numbers;
static int answer;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int n = Integer.parseInt(firstLine[0]);
s = Integer.parseInt(firstLine[1]);
numbers = new int[n];
String[] numberStrings = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
numbers[i] = Integer.parseInt(numberStrings[i]);
}
solve(0, 0);
System.out.println(answer);
}
public static void solve(int index, int sum) {
if(index == numbers.length) return;
if(sum + numbers[index] == s) answer++;
solve(index + 1, sum + numbers[index]);
solve(index + 1, sum);
}
}
[6603] 로또
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 128 MB | 66596 | 37932 | 26567 | 55.718% |
문제
독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.
로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.
예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.
각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.
문제 풀이
이 문제는 사전순으로 부분 수열을 출력하는 문제이다. 이 때 중복을 허용하지 않는다.
필요한 변수를 선언하고 입력을 받자.
이 문제는 TestCase가 여러 개가 있는 문제이다.
while문을 사용하여 여러 테스트 케이스에 대한 경우를 입력받자.
그리고 출력할 값들을 StringBuilder를 사용하여 한번에 모아 한번에 출력을 해주자.
- T: 수열의 개수
- numbers: 주어지는 수열
- result: 출력할 수열
class Main {
static int T;
static int[] numbers;
static int[] result;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
T = sc.nextInt();
if (T == 0) break;
numbers = new int[T];
for (int i = 0; i < T; i++) {
numbers[i] = sc.nextInt();
}
result = new int[6];
back(0, 0); // start index 추가
sb.append("\\n");
}
System.out.print(sb); // 마지막 빈 줄 제거 후 출력
}
재귀 함수를 사용하여 부분 수열을 조합하자.
- Base Case
- 탐색을 모두 진행하여 index가 로또의 개수(6)이 되면 종료하자.
- 만약 모두 진행하였다면 result를 출력해주는데 이때 StringBuilder에 숫자를 출력해주자.
- Recursive
- 같은 값은 중복이 안되게 하자.
- 다음 인덱스부터 선택을 하게 하면 중복을 피할 수 있다.
public static void back(int start, int depth) {
if (depth == 6) {
for (int val : result) {
sb.append(val).append(" ");
}
sb.append("\\n");
return;
}
for (int i = start; i < T; i++) {
result[depth] = numbers[i];
back(i + 1, depth + 1); // 다음 인덱스부터 선택
}
}
전체 코드
이 알고리즘의 시간복잡도는 O(N)이다.
import java.util.*;
class Main {
static int T;
static int[] numbers;
static int[] result;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
T = sc.nextInt();
if (T == 0) break;
numbers = new int[T];
for (int i = 0; i < T; i++) {
numbers[i] = sc.nextInt();
}
result = new int[6];
back(0, 0); // start index 추가
sb.append("\\n");
}
System.out.print(sb); // 마지막 빈 줄 제거 후 출력
}
public static void back(int start, int depth) {
if (depth == 6) {
for (int val : result) {
sb.append(val).append(" ");
}
sb.append("\\n");
return;
}
for (int i = start; i < T; i++) {
result[depth] = numbers[i];
back(i + 1, depth + 1); // 다음 인덱스부터 선택
}
}
}
[1208] 부분 수열의 합2
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 31765 | 8399 | 5740 | 25.073% |
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
문제 풀이
이 문제는 이전 문제 [1182]문제에서 N의 범위가 40으로 확장된 경우이다.
부분 수열의 원소의 합이 특정 값 S가 되는 경우의 수 N의 범위가 40까지 확장되었다.
만약 N이 40인 경우에는 2^40이기에 연산 횟수가 약 1조이다.
그렇다면 1초에 1억회를 계산한다 해도 3시간 정도 소요가 되는 것이다.
수열의 범위를 두개의 구간으로 나눠서 생각해보자.
그렇다면 계산할 수열의 범위를 두개로 나눠 보자.
임의의 값 K를 기준으로 LEFT [0, k], RIGHT [k, n] 두개의 구간으로 수열을 나눌 수 있다.
S - sum을 만드는 각각의 경우에 sum을 더하면 S가 된다.
- LEFT 구간에서 만들어지는 수열의 합을 Map에 저장해 둔다.
- RIGHT 구간에서 만들어지는 수열의 합 sum을 구한다.
- 1의 Map을 통해 S - (sum)을 만드는 경우의 수를, S의 경우의 수에 더한다.
- 2~3을 재귀를 통해 반복한다.(RIGHT 구간의 모든 수열만큼)
최적의 범위를 나누는 방법
Base Case와 Recursive Case
- Base Case
- 수열의 모든 수에 대해 판단하여 결정한 경우
- Recursive Case
- index 번째 숫자까지의 결정에 대해 합을 알고 있을때
- index + 1번째 수를 포함한 경우
- index + 1번째 수를 포함하지 않는 경우
- index 번째 숫자까지의 결정에 대해 합을 알고 있을때
필요한 변수 선언 및 입력값 받기
입력값과 출력할 값을 받는다.
이때 status를 선언하여 LEFT, RIGHT일때를 분리하자.
class Main {
static int s;
static int[] numbers;
static long answer;
static int status = -1;
static final int LEFT = 0;
static final int RIGHT = 1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
s = sc.nextInt();
numbers = new int[n];
for(int i = 0; i < n; i++)
numbers[i] = sc.nextInt();
<---생략--->
분리하여 함수 호출하기
status를 업데이트하여 LEFT와 RIGHT일때를 분리하자.
<---생략--->
status = LEFT;
solve(0, n/2, 0);
status = RIGHT;
solve(n/2, n, 0);
if(s == 0) answer--;
System.out.println(answer);
<---생략--->
재귀 함수
Map 자료구조를 이용하여 Sum을 기록하고 해당 Sum이 몇번이 있는지 prev를 이용하여 기록을 할 것이다.
예시로 sum이 4인경우가 2번이 있고 sum이 3인경우가 1번이 있다면 {4:2, 3:1}로 저장되는 것이다.
그리고 RIGHT일 경우 해당 s-sum을 키를 갖고 있는 Value값을 Map에서 찾아와 answer에 추가하는 것이다.
static Map<Integer,Integer> cnt = new HashMap<>();
public static void solve(int index, int end, int sum) {
if(index == end) {
if(status == LEFT) {
int prev = cnt.getOrDefault(sum, 0);
cnt.put(sum, prev + 1);
} else if (status == RIGHT) {
answer += cnt.getOrDefault(s - sum, 0);
}
return;
}
solve(index + 1, end, sum);
solve(index + 1, end, sum + numbers[index]);
}
전체코드
시간 복잡도 분석:
- LEFT 상태 (첫 번째 절반 탐색)
- solve(0, n/2, 0) 호출
- 각 요소당 2가지 선택지 (포함/미포함)
- 시간 복잡도: O(2^{n/2})
- RIGHT 상태 (두 번째 절반 탐색)
- solve(n/2, n, 0) 호출
- 각 요소당 2가지 선택지 (포함/미포함)
- 시간 복잡도: O(2^{n/2})
최종 시간 복잡도: O(2^{n/2})
import java.util.*;
class Main {
static int s;
static int[] numbers;
static int answer;
static int status = -1;
static final int LEFT = 0;
static final int RIGHT = 1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
s = sc.nextInt();
numbers = new int[n];
for(int i = 0; i < n; i++)
numbers[i] = sc.nextInt();
status = LEFT;
solve(0, n/2, 0);
status = RIGHT;
solve(n/2, n, 0);
if(s == 0) answer--;
System.out.println(answer);
}
static Map<Integer,Integer> cnt = new HashMap<>();
public static void solve(int index, int end, int sum) {
if(index == end) {
if(status == LEFT) {
int prev = cnt.getOrDefault(sum, 0);
cnt.put(sum, prev + 1);
} else if (status == RIGHT) {
answer += cnt.getOrDefault(s - sum, 0);
}
return;
}
solve(index + 1, end, sum);
solve(index + 1, end, sum + numbers[index]);
}
}
'알고리즘 > Recursion' 카테고리의 다른 글
| [코딩테스트] [1759] 암호 만들기 & [10971] 외판원 순회 2 & [14888] 연산자 끼워넣기 (2) | 2025.02.19 |
|---|---|
| [코딩테스트] [14267] 회사 문화 1 & [1068] 트리 & [5639] 이진 검색 트리 (0) | 2025.02.12 |
| [코딩테스트] [11725] 트리의 부모 찾기 & [1991] 트리 순회 & [15681] 트리와 쿼리 (0) | 2025.02.11 |
| [코딩테스트] 재귀함수 & [15654~15657] N과M (1) | 2025.02.07 |