패스트캠퍼스 챌린지 20일차

어떻게든 푼다! 완전 탐색

 - 가장 기본적으로 접근하는 방식이므로 많은 연습이 필요하다

 

완전탐색이란?

 - 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법

 - 그 중에서도 백트래킹을 통해야 하는 상황 해결

 • 모든 코테 문제에서 기본적으로 접근해봐야하므로 많은 연습이 필요하다

 

장점 : 부분 점수를 얻기 좋다

단점 : 전부 탐색하기에 시간 복잡도가 일반적으로 높다.

 

 

1. N개중 중복을 허용하고 순서대로 나열하는 알고리즘 구현 (재귀함수)

    // 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
    // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
    static void rec_func(int k) {
        if (k == M + 1) { // 다 골랐을 경우
            // selected[1...M] 배열이 새롭게 탐색된 결과
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            for (int cand = 1; cand <= N; cand++) {
                // k 번째에 cand 가 올 수 있으면
                selected[k] = cand;

                // k+1 번부터 M 번을 모두 탐색하는 일을 한다.
                rec_func(k + 1);
                selected[k] = 0;
            }
        }
    }

 

2. N개중 중복을 허용하지 않고 순서대로 나열하는 알고리즘 구현 (재귀함수)

    static void rec_func(int k) {
        if (k == M + 1) { // 1 ~ M 번째를 전부 다 골랐을 경우
            // selected[1...M] 배열이 새롭게 탐색된 결과
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            for (int cand = 1; cand <= N; cand++) {
                boolean isUsed = false;
                for (int i=1;i<k;i++)
                    if (cand == selected[i])
                        isUsed = true;
                // k 번째에 cand 가 올 수 있으면
                if (!isUsed) {
                    selected[k] = cand;
                    rec_func(k + 1);
                    selected[k] = 0;
                }
            }
        }
    }

 

배열 used를 사용하여 for문을 제거한 후 시간복잡도 낮추기

    static int[] selected, used; 
    
	static void rec_func(int k) {
        if (k == M + 1) { // 1 ~ M 번째를 전부 다 골랐을 경우
            // selected[1...M] 배열이 새롭게 탐색된 결과
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            for (int cand = 1; cand <= N; cand++) {
                if (used[cand] == 1) continue;
                // k 번째에 cand가 올 수 있으면
                selected[k] = cand;
                used[cand] = 1;
                
                ref_func(k+1);
                selected[k] = 0;
                // 재귀호출이 끝나면 사용을 초기화
                used[cand] = 0;
            }
        }
    }

 

3. N개중 중복을 허용하고 M개를 고르기

    static void rec_func(int k) {
        if (k == M + 1) { // 1 ~ M 번째를 전부 다 골랐다!
            // selected[1...M] 배열이 새롭게 탐색된 결과
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            int start = selected[k-1];
            if (start == 0) start = 1;
            for (int cand = start; cand <= N; cand++) {
                // k 번째에 cand 가 올 수 있으면
                selected[k] = cand;
                rec_func(k + 1);
                selected[k] = 0;
            }
        }
    }

 

4. N개중 중복을 허용하지않고 M개를 고르기

    static void rec_func(int k) {
        if (k == M + 1) {
            for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
            sb.append('\n');
        } else {
            for (int cand = selected[k-1] + 1; cand <= N; cand++) {
                // k 번째에 cand 가 올 수 있으면
                selected[k] = cand;
                rec_func(k + 1);
                selected[k] = 0;
            }
        }
    }

 

 

완전 탐색 문제를 접근할 때 유의할 점

 - 고를 수 잇는 값의 종류 파악하기

 - 중복을 허용하는지 확인

 - 순서가 중요한지 확인

 

 

 

20일차 인증

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]