[항해99 취업 리부트 코스 학습일지] 2024.03.29.(금)

오늘 알고리즘 난이도가 훅! 올라가버려서 엉엉 울 뻔 했다.. 수학 문제도 그렇고

그렇지만 새로운 공부를 할 수 있어서 나름 뿌듯했다

 

오늘 새로 공부한 것들

1. 시간복잡도

for 문 여러번 돌게 되면 for문이 돌아가는 회수가 n² 이 된다..

 

2. 미리 알아두어야 하는 수학공식

확률에서 P와 C의 차이점

C(combination, 조합) : 순서 중요하지 않다.

- 예) 동전을 던젔을 때 앞면이 나올 확률

- 공식 : nCr = n! / (r! * (n-r)!)

 

P(probability, 확률) : 순서 중요하다

예) 52 장의 카드 더미에서 에이스를 선택할 확률

- 공식 : 확률의 공식은 여러가지이다..

  nPn = n!

  nPr = n! / (n-r)!

 

3.  이분탐색

반쪼개서 탐색하기!, 정렬된 순서에서 기준값이랑 비교해서 큰쪽으로 갈지 작은 쪽으로 갈 지 비교하기 때문에 

정렬이 정말정말 중요하다.

 

4. DFS, BFS

이건 따로 빼서 정리 중,, 오늘 완전 노가다했쟈나...

package src.com.company.day3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_15649_N과M_2 {
    /**
     * 1~N까지 자연수 중에서 "중복 없이" M개를 고른 수열
     * 1 ≤ M ≤ N ≤ 8 : 여기서 M은 N보다 같거나 작다(N이 큰수), N부터 주어짐
     * 출력조건 : "124~~" , 각 수열 숫자 공백구분, 다른 수열 개행문자("\n")
     */

    public static void main(String[] args) throws  IOException {

        /**
         * 알고리즘 : 백트래킹(재귀함수랑 차이가 뭐지? 질문하기) : 모든 조합 찾아 출력하기
         * 질문 2) 전역변수로 빼 두는것의 이점(코딩테스트 시?)
         * 대표 예시: 깃허브에 올려놓음(https://github.com/velyvel/sparta_reboot/blob/main/src/com/company/day3/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9_%EC%98%88%EC%8B%9C.java)
         * */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 3
        int N = Integer.parseInt(st.nextToken());
        // 2
        int M = Integer.parseInt(st.nextToken());
        //[0,0] 인 상태
        int[] arr = new int[M];
        //[false, false, false] 인 상태
        boolean[] isVisited = new boolean[N];

        combineNumbers(M, N,0, arr, isVisited);

    }

    public static void combineNumbers(int M, int N, int count, int[] arr, boolean[] isVisited){
        StringBuilder sb = new StringBuilder();
        /** 나의 의도 : 선택한개 개수(count)를 증가시켜 최댓값 M(2)이 되면 시작(조합 할 숫자찾기)
         * 1. count = M 재귀호출 멈추고 조합 출력
         * 2. 종료 조건 설정 : count < M 이 되면(집합을 만들지 못해) 선택 숫자 찾는 for문(아래 for문) 으로 간다. 
         * 3. 각 반복에서 i에 해당하는 것이 선택이 되지 않았다면, isVisited 와 count 변경 후 다른 거 찾기
         */

        /**
         * 1. count 가 0 이고 M이 2 이기 때문에 for문 탄다
         * 2. (1-0 종료 후 올라옴) count 가 1 이 된 상황 -> 다시 포문으로
         * 3. (1-1 종료 후 올라옴) count 가 2 가 된 상황 -> if 아래 for 문 탄다 현재 arr : {1,2} 인 상황이다.
         *  - sb에 쓰기 : 1 2
         *  - 출력 후 리턴 ->  마지막 isVisited[i] false -> [t,f,f]로 돌려놓기
         * 4. (1-1 종료 후 올라옴) count 는 계속 2
         *  - 1, 3 출력 -> 다시 아래 for문
         *  ... 이렇게 반복된다..
         *  즉, isVisited true의 인덱스 + 1 값을 출력해준다..
         */

        if(count == M) {
            for(int number : arr) {
                sb.append(number).append(' ');
            }
            //System.out.println();
            // 질문? '\n' 와 "\n"의 출력의 차이?
            sb.append('\n');
            System.out.print(sb);
            return;
        }
        // 그리고 굳이 sort 넣으려고 애썼다..
        /**
         * (count) - (i)
         * 0 - 0 : isvisited [f,f,f] -> [t,f,f], arr[1,0] -> 재귀
         * 1 - 0 부터 도는데 isVisited[0]은 true 라서 다시 올라감
         * 1 - 1 : isVisited[t,f,f] -> [t,t,f] -> 다시 재귀 호출
         * 2 - 1 : isvisited [t,f,t] -> arr{1,3} ->  다시 재귀 호출
         * */
        for (int i = 0; i < N; i++) {
            if(isVisited[i] == false) {
                isVisited[i] = true;
                arr[count] = i + 1;
                combineNumbers(M, N, count+1, arr, isVisited);
                // 이 코드 안넣어서 자꾸 에러났었음.. 다음 경우를 위해 원래 상태로 되돌려주기..
                isVisited[i] = false;
            }
        }
    }

}