오늘부터 4일간 알고리즘 코칭이 시작됐다!
이전에 알고리즘 강의는 잘 따라가지 못했는데 이번기회에 확실하게 개념을 잡고자한다.
오늘은 그 첫번째 이야기다.
완전탐색이란?
완전탐색이란 말 그대로 '완전히 탐색하는 것'으로 모든 경우의 수를 모두 고려하는 것을 말한다.
이러한 완전 탐색에는 3가지 방법이 있다.
- 순열
- 조합
- 부분집합
구분 방법
그럼 이 3가지를 어떻게 구분할까?
첫번째 단계는 고르는 개수의 유무이다. 보통 N개 중 R개를 뽑으라는 문제 형식이 많은데 이렇게 R이라는 뽑는 개수가 정해져 있을 경우 완전 탐색 중에서도 순열과 조합 두가지로 좁혀지게 된다.
먼저 두가지 예시를 보고 위 개념을 좀더 학습해보자
E1. 백준 3040번_백설공주와 일곱난장이
문제를 읽어보면 9명의 난장이 중 7명을 골라 합을 기준으로 판별을 하게 된다.
여기서 9명 중 순서 상관없이 7명을 고르면되니 이 문제는 조합 문제가 된다.
E2. 백준 10971번_외판원 순회2
문제를 읽어보면 정확하게 몇개를 뽑는다는 말이 나와있지 않지만 결국 N개를 뽑아 줄을 세운다는 느낌을 받을 수 있다. 따라서 이 문제는 순열 문제가 된다.
이런식으로 뽑는 특정 개수가 주어지면 순열과 조합 두가지로 좁혀지고 더 나아가 뽑은 R개의 순서가 바뀌었을때 결과가 달라지면 순열, 결과가 같다면 조합으로 해결할 수 있다.
E3. 백준 2961_도영이가 만든 맛있는 음식
이 문제는 위의 문제들과 다르게 정확하게 몇개를 뽑는다는 말이 없다. 여기서 주어진 조건은 재료는 적어도 하나 사용해야한다. 인데 이말은 뽑는 개수가 1,2,3,.. 으로 0개만 아니면 된다는 말이 된다. 이럴때 뽑는 개수는 동적이게 되고 위의 문제들과 다르게 부분집합 으로 해결할 수 있게 된다.
코드 작성
그럼 위의 개념들을 토대로 하나씩 코드를 작성해 보자.
이해하기 쉽게 for문으로 먼저 작성해본뒤, 재귀를 통해 리팩토링하는 방식으로 진행하겠다.
순열
1) 반복문을 통한 순열
public class Permutation_for {
static int N = 4; // 전체 요소의 개수
static int[] arr = {1,3,5,7};
static int R; // 뽑을 개수
public static void main(String[] args) {
// 조건문이 없으면 중복수열이 된다.
for (int i = 0; i < N; i++) {
// arr[i]
for(int j = 0; j < N; j++){
// arr[j]
if(i == j) continue;
for(int k = 0; k < N; k++){
// arr[k]
if(i == k || j ==k ) continue;
System.out.println(arr[i] + " " + arr[j]+ " " + arr[k]);
}
}
}
}
}
먼저 반복문을 활용한 순열이다.
뽑으려는 개수만큼 반복문을 중첩시킨뒤, 같을 경우 continue하는 조건을 추가해 순열을 구현할 수 있다.
하지만 뽑을 개수가 동적으로 변할 경우 for문을 동적으로 추가해 줘야하는데 이 부분은 사실상 불가능하다.
2) 재귀를 활용한 순열(중복순열)
import java.util.Arrays;
import java.util.Scanner;
public class Permutation_recursive_중복순열 {
static int N = 4; // 전체 요소의 개수
static int[] arr = {1, 3, 5, 7};
static int R; // 뽑아야할 개수
static int[] result; // 뽑은 정보를 저장할 배열
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
result = new int[R];
permutation(0);
}
/**
* R = 2인 경우
* 요소 뽑기 반복
* idx에 담을 요소를 하나 뽑고, idx+1에 담을 요소 뽑기는 재귀로 넘김
*
* @param idx 요소를 뽑아서 담을 인덱스 or 현재까지 뽑은 요소의 개수
*/
static void permutation(int idx) {
// 기저 조건(종료조건)
if (idx == R) {
// 하나의 경우의 수가 완성된 상태
System.out.println(Arrays.toString(result));
return;
}
// 유도 파트(반복파트)
for (int i = 0; i < N; i++) {
// arr[i] => 뽑을 요소
// 요소 뽑기
// result[] = arr[i]; //담아 놓아야한다.
// 첫번째 호출은 0, 두번째 호출은 1 => 넣을 위치의 index 알아야한다.
result[idx] = arr[i];
// 다음 요소 뽑기는 재귀로 넘김
// j에서 i를 접근할 수 없다!
// idx + 1번째 담을것은 다음으로 넘기기
permutation(idx + 1);
}
}
}
여기서부터 조금 복잡해진다.
기존 반복문을 활용한 순열 구현의 경우 반복문의 중첩으로 해결을 했기때문에 j에서 i로 접근이 가능했다.
이말은 즉 이전에 뽑은 요소가 무엇인지 확인이 가능했다는 말이다.
하지만 재귀를 활용할 경우 매개변수로 전달하지 않는 이상 이전의 요소가 무엇인지 확인이 불가능하기 때문에 int idx 를 매개변수로 전달해 줌으로써 이전에 뽑힌 숫자가 무엇인지 알 수 있게 된다.
하지만 여기에도 문제가 있다.
이 경우 이전에 뽑은 요소도 또 다시 뽑기 때문에 중복순열이 된다는 점이다.
3) 재귀를 활용한 순열(일반순열)
import java.util.Arrays;
import java.util.Scanner;
public class Permutation_recursive_일반순열 {
static int N = 4; // 전체 요소의 개수
static int[] arr = {1, 3, 5, 7};
static boolean[] visited; //
static int R; // 뽑아야할 개수
static int[] result; // 뽑은 정보를 저장할 배열
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
result = new int[R];
visited = new boolean[N];
permutation(0);
}
/**
* R = 2인 경우
* 요소 뽑기 반복
* idx에 담을 요소를 하나 뽑고, idx+1에 담을 요소 뽑기는 재귀로 넘김
*
* @param idx 요소를 뽑아서 담을 인덱스 or 현재까지 뽑은 요소의 개수
*/
static void permutation(int idx) {
// 기저 조건(종료조건)
if (idx == R) {
// 하나의 경우의 수가 완성된 상태
System.out.println(Arrays.toString(result));
return;
}
// 유도 파트(반복파트)
for (int i = 0; i < N; i++) {
if (visited[i]) continue; // 이미 뽑은 요소
// arr[i] => 뽑을 요소
// 요소 뽑기
// result[] = arr[i]; //담아 놓아야한다.
// 첫번째 호출은 0, 두번째 호출은 1 => 넣을 위치의 index 알아야한다.
result[idx] = arr[i]; // 요소 뽑기
visited[i] = true; // 뽑은 요소 체크
// 다음 요소 뽑기는 재귀로 넘김
// j에서 i를 접근할 수 없다!
// idx + 1번째 담을것은 다음으로 넘기기
permutation(idx + 1);
visited[i] = false; // 뽑은 정보 되돌리기
}
}
}중복순열이 되는 문제를 해결하기위해 요소와 같은 개수의 boolean[] visited 배열을 통해 방문 여부를 체크하고 해제함으로써 방문한 요소를 확인하고 지나칠수있는 조건을 구현할 수 있다.
조합
1) 반복문을 통한 조합
public class Combination_for {
static int N = 4; // 전체 요소의 개수
static int[] arr = {1,3,5,7};
public static void main(String[] args) {
for(int i = 0 ; i < N ; i++){
// arr[i] 첫번째 뽑은 요소
for(int j = i+1; j < N ; j++){
// arr[j]
for(int k = j+1; k < N ; k++){
//arr[k]
System.out.println(arr[i] + " " + arr[j]+ " " + arr[k]);
}
}
}
}
}
반복문을 활용한 조합은 간단하다.
조합은 뒤에 뽑힐 수들이 앞에 뽑힌 수보다 크다 라는 점이다. 이 점을 활용해 반복문의 시작점을 조정해 준다면 조합을 구현할 수 있다.
2) 재귀를 활용한 조합
import java.util.Arrays;
import java.util.Scanner;
public class Combination_recursive {
static int N = 4; // 전체 요소의 개수
static int[] arr = {1, 3, 5, 7};
static int R; // 뽑아야할 개수
static int[] result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
result = new int[R];
combination(0, 0);
}
/**
* 첫번째, 두번째, 마지막 요소 뽑을때 생각하기
* <p>
* idx에 담을 요소 하나를 뽑고, idx+1에 담을 요소뽑기는 재귀로 넘긴다.
*
* @param idx 뽑은 요소를 담을 인덱스 or 현재까지 뽑은 요소의 개수
* @param start 뽑을 요소의 후보군들의 시작 인덱스
*/
static void combination(int idx, int start) {
// 기저 조건(종료조건)
if (idx == R) {
System.out.println(Arrays.toString(result));
return;
}
// 반복 파트(유도파트)
for (int i = start; i < N; i++) {
// arr[i] 뽑을 요소
// 요소 하나 뽑기
result[idx] = arr[i];
// 다음 요소 뽑기는 재귀로 넘긴다
combination(idx + 1, i + 1);
// combination(idx+1, start+1); >> 뽑았던거 다음거를 넣어줘야하는데 start + 1 을넘기면 안된다. >> 중복된다
}
}
}
재귀를 활용한 조합의 코드를 보면 매개변수가 2개 설정돼있는것을 볼 수 있다.
이 부분의 개념을 확실히 잡고 넘어가자
int idx: 뽑은 요소를 담을 인덱스 or 현재까지 뽑은 요소의 개수int start: 뽑을 요소의 후보군들의 시작 인덱스
가장 많이 하는 실수
combination(idx+1, i+1)을 combination(idx+1, start+1)로 잘못 적는 실수를 가장 많이 하는데 주의하자!
이렇게 1일차가 종료됐다.
내일도 화이팅!
