패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 강의 3주차

이번주는 Part5 단기완성 알고리즘 강의를 들었다.

이 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 강의가 좋은 점은

1. 자세하게 알고리즘을 설명해 주는 강의 (PART 1 ~ PART 4)

2. 급하게 코딩테스트를 준비해야 할 때 필요한 콤팩트한 강의 (PART 5)

3. SQL 강의 (PART 6)

가 한꺼번에 있다는 점이다.

1번 강의는 순차적으로 오픈되고 있어서, 차기 챕터가 오픈되기 전 PART 5. 류호석 님의 단기완성 알고리즘 강의를 듣기로 했다.

 

 

---

1. 완전탐색 

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

그 중에서도 *백트래킹(Back-Tracking)을 통해야 하는 상황을 해결하기.

* 백트래킹이란 현재 상태에서 가능한 모든 경로를 탐색하다가 원하는 값과 불일치하는 부분이 발생하면 , 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는 알고리즘이다.

 

 

1) 코테에 나오는 완전 탐색 종류

 

N개 중  1) 중복을 허용해서 2) 중복없이 M개를  A) 순서 있게 나열하기 B) 고르기

 

 

2) 완전 탐색은 함수 정의가 50%

앞으로 기본 함수 개형은 아래와 같을 것임.

// 재귀 함수
// 만약 M개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것!
// 아직 M개를 고르지 않음 => k번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다. 
static void rec_func(int k){}

public static void main(String[] args){
	input();
    //1번째 원소부터 M번쨰 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
    rec_func(1);
    System.out.println(sb.toString());

}

 

 

3) 완전 탐색 문제를 접근할 때는,

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

- 중복을 허용하는지

- 순서가 중요한 지

 

 

⭐️ 문제 풀기 

 

1. N개 중 중복을 허용해서, M개를 순서 있게 나열하는 방법

연습문제 : [BOJ 15651] https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

• 사람이 어떻게 풀까?
• 시간, 공간 복잡도 계산하기
  • 시간 : N=4, M=3 => 4^3 => O(N^M) => 최악의 경우 82만 => 구현 o (1초에 1억 번 연산 가능) 
  • 공간 : O(M)

package 완전탐색;

import java.util.Scanner;

public class BOJ15651_r {

    static StringBuilder sb = new StringBuilder();
    static void input(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        selected = new int[M+1];
    }

    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=1; cand<=N; cand++){
                selected[k] = cand;
                rec_func(k+1); //k+1 ~ M까지
            }
        }

    }

    static int N, M;
    static int[] selected;
    public static void main(String[] args){
        input();
        rec_func(1);
        System.out.println(sb.toString());
    }
}

 

 

2. N개 중 중복을 허용하지 않고, M개를 순서 있게 나열하는 방법

[BOJ 15649] https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

• 사람이 어떻게 풀까?
• 시간, 공간 복잡도 계산하기
  • 시간 : N=4, M=3 => 4! => O(N! / (N-M)!) => 8! => 4만 가지 => 구현 o
  • 공간 : O(M)
• 중복을 방지하기 위해 사용 여부 판별하는 배열 만들기 used[] (1이면 사용, 0이면 미사용)

package 완전탐색;

import java.util.Scanner;

// https://www.acmicpc.net/problem/15649
public class BOJ15649 {

    static StringBuilder sb = new StringBuilder();

    static void input(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        selected = new int[M+1];
        used = new int[N+1];
    }

    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=1; cand<=N; cand++){
                if(used[cand] == 1) continue;
                selected[k] = cand;  used[cand] = 1;
                rec_func(k+1);
                selected[k] = 0; used[cand] = 0;
            }
        }
    }

    static int N, M;
    static int[] selected, used;
    public static void main(String[] args){

        input();
        rec_func(1);
        System.out.println(sb.toString());
    }
}

 

=>  추가 설명 (좀 횡설수설...)

k는 깊이를 나타내고(수의 자릿수), cand는 자릿수를 채우는 (=사용할 수 있는 수)를 나타낸다.

인덱스를 1부터 사용할 것이므로 N+1, M+1의 배열을 만든다.

1~4까지의 숫자를 사용했는지를 판별하기 위해 used ={0,0,0,0} 배열을 만든다.

k가 1일 때부터 (=십의 자리 수) 탐색하면서, 만약 k가 3이 되면 selected 배열에 숫자가 완성되었음을 나타내므로 출력한다.

그게 아니라면 cand 변수로 N까지 for문을 도는데, used[cand]가 1인지 (1이면 사용) 확인하여 사용되지 않은 수라면

selected 배열의 k 번째 인덱스에 cand 를 넣어주고, cand를 사용했음을 used에 기록해준다.

이를 반복한다.

 

 

3. N개 중 중복을 허용해서, M개를 고르는 방법 (나열 x) (비내림차순)

[BOJ 15652] https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

• 사람이 어떻게 풀까?
• 시간, 공간 복잡도 계산하기
  • 시간 : N=4, M=3 => 4! => 4^3 보다 작다 => O(N^M) => 1677만보다 작거나 같다 => 구현 o
  • 공간 : O(M)

package 완전탐색;

import java.util.Scanner;

// https://www.acmicpc.net/problem/15652
public class BOJ15652 {

    static StringBuilder sb = new StringBuilder();
    static void input(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        selected = new int[M + 1];
    }

    static void rec_func(int k){
        if(k == M+1){
            for(int i=1;i<=M;i++) sb.append(selected[k]).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;
            }
        }
    }

    static int N, M;
    static int[] selected;
    public static void main(String[] args){
        input();
        rec_func(1);
        System.out.println(sb.toString());
    }
}

 

 

 

4. N개 중 중복을 허용하지 않고, M개를 고른다 (나열 x)

[BOJ 15650] https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

• 사람이 어떻게 풀까?
• 시간, 공간 복잡도 계산하기
  • 시간 : N=4, M=3 => O(N!/M!(N-M)!) => 70 => 구현 o
  • 공간 : O(M)

package 완전탐색;

import java.util.Scanner;

// https://www.acmicpc.net/problem/15650
public class BOJ15650 {

    static StringBuilder sb = new StringBuilder();
    static void input(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        selected = new int[M + 1];
    }

    static void rec_func(int k){
        if(k == M+1){
            for(int i=1;i<=M;i++) sb.append(selected[k]).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;
            }
        }
    }

    static int N, M;
    static int[] selected;
    public static void main(String[] args){
        input();
        rec_func(1);
        System.out.println(sb.toString());
    }
}

 

 

 

 

 

덧붙여서 이번 강의에서 활용되는 재귀함수에 대해 잘 정리해 놓은 글이 있어서 첨부한다.

https://velog.io/@newon-seoul/문과생이-적어보는-백트래킹-재귀와-DFS-를-곁들인

문과생이 적어보는 백트래킹 (재귀와 DFS 를 곁들인)

 

 

패스트캠퍼스 강의 링크 :  https://fastcampus.co.kr/dev_online_codingtest

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼

 

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