진짜_잘하고_싶거든요.zip

오늘의 학습 키워드 : 이분 탐색 , 파라메트릭 서치

1. 문제 : 백준 16401 과자 나눠주기

2. 내 풀이 

이분 탐색에 대한 개념은 알고 있었지만 파타메트릭 서치(이분탐색의 하위개념)에 대해서는 알지 못했다. 

그래서 공부를 좀 하느라 시간이 걸렸다. 

파라메트릭 서치 같은 경우는 "최적화문제"를 "결정 문제"로 바꿔서 해결하는 알고리즘이다. 이 개념은 유튜브 보고 이해를 했다..

결론적으로는 이분 탐색같은 경우는 입력받은 배열 같이 특정 값을 찾아 반절씩 쪼개면, 파라매트릭 서치는 배열이 아니라 내가 원하는 정답

- 이분 탐색 : 특정값을 찾는 문제 (배열안에 target 값 찾기 )

- 파라매트릭 서치 : 최대 몇 까지 가능? 최소 몇까지? 이런 느낌이다. 

- 이분탐색을 풀 때 처럼 파라매트릭 서치도 템플릿은 비슷하다(left, right, mid정하는 그런거,,)

처음에는 입력받은 배열 안에서 탐색을 하려고 하니까 머리가 안돌아갔다. 그래도 좀 공부를 하다보니 이해가 됐다. 

애초에 탐색하려는 범위가 과자의 길이 입력받은 값들이 아니라 결국 여기서 제일 큰 과자의 길이가 max가 되고 1~max 사이의 값 중에서 탐색을 하면 된다. 정답 후보는 이거다. 그리고 입력받은 과자의 길이들은 mid(target)값을 구할때 과자의 개수(cnt)를 구하는데 활용이 된다. 

시간복잡도 = O(N log(N))

3.코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class CT0414 {
    static int left = 1;
    static int right = 0;
    static int mid =0;
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());
       int M = Integer.parseInt(st.nextToken()); //조카 수
       int N = Integer.parseInt(st.nextToken()); //과자 수
       int[] lenarr = new int[N]; // 과자의 각 길이를 담을 배열 선언


       st = new StringTokenizer(br.readLine());
       for(int i=0; i< N; i++) {
           lenarr[i] = Integer.parseInt(st.nextToken());
           right = Math.max(right, lenarr[i]); // 제일 큰 값이 들어가게 됌
       }

       int result = 0;
       while(left <= right) {
           mid = (left + right) / 2;
           int cnt = 0; // 과자를 나눴을 때 과자의 개수
           for (int i = 0; i < N; i++) {
               cnt = cnt + lenarr[i] / mid;
           }
           
// 이 부분에서 조쿰 오류가 났었다
//           if (cnt < M) { // 조카 수 < 과자 수 (과자 길이 중어야함)
//               right = mid - 1;
//           } else if (cnt > M){ // 조카 수 > 과자 수 (과자 기링 늘려도 됌)
//               left = mid + 1;
//           } else {
//               break;
//           }

//개선된 코드
           if(cnt < M) {
               right = mid - 1;
           } else {
               result = mid;// 조건 만족하긴 하지만 더 크게 만족하는 값을 찾기 위해
               left = mid + 1;
           }
       }

       System.out.println(result);


    }


}

- 풀고 나서 보니까 테스트 케이스에서 답이 어떤것은 맞고 틀렸다..

- 조건문에서 아무래도 조건만 맞는다고 끝이 아니라 결국 더 큰 값을 만족해야하기 떄문에 mid값을 보관하고 한번 더 탐색해서 더 만족하는 값을 구할 수 있게 했다. 

오늘의 학습 키워드 : 투포인터 

1. 문제 : 백준 2559 수열 

2. 내 풀이 

1. 일단 n, k 입력 받고 n이 전체 수열의 크기만큼 배열 정해서 입력받았다. 

2. i를 플래그 기준으로 범위만큼의 값의 누적합을 비교하는 방식을 사용하려고 했다. 

but, 생각해보니 i를 기준으로 k 범위만큼의 합을 구할때 만약 k범위 안에 값이 입력받은 배열의 범위를 벗어나면 어쩌지? 

그래서 범위만큼을 더 할 때 범위를 벗어나면 누적합을 구하는 루프를 break로 벗어나게 했다.

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

public class CT0404 {

    public static void main(String[] args) throws IOException{
       //온도를 측정한 전체 날짜 수 2 <= n <= 100,000
        //합을 구하기 위한 연속적인 날짜 수  1 <= k <= n

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int max = Integer.MIN_VALUE;

        st = new StringTokenizer(br.readLine());
        int[] temperarr = new int[n];
        for (int i=0; i<n; i++) {
            temperarr[i] = Integer.parseInt(st.nextToken()); // n크기 만큼 온도 배열 입력받기
        }


        for(int i=0; i<n; i++) {
            int sum = 0;
            for(int j=0; j<k; j++) {
                // 연속된 날짜 수
                if(i + j >= n) break;
                sum += temperarr[i+j];
            }
            max = Math.max(max, sum);
        }

        System.out.println(max);
    }
}

.

.

.

.

시간 초과다

3. 다른 풀이 

3.1  슬라이딩 윈도우를 적용한 코드 

 // 1. 처음 k일의 합 구하기
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += temperarr[i];
        }

        int max = sum;

 // 2. 슬라이딩 윈도우로 합 갱신
        for (int i = k; i < n; i++) {
            sum = sum - temperarr[i - k] + temperarr[i];
            max = Math.max(max, sum);
        }

슬라이딩 윈도우 : 고정된 크기의 윈도우(구간)를 배열 위에서 한칸씩 이동시키켜 계산하는 방법

여기의 핵심 아이디어는 처음 k구간 sum으로 계산 후 -> sum - arr[왼쪽 끝] + arr[오른쪽 새 원소] 

방식으로 고정 크기의 윈도우를 유지하며 합의 값을 구하는 방식이었다. 

슬라이딩 윈도우를 사용해야 하는 상황 

- 배열에서 고정된 길이의 최대/최소 합 구하기 

- 문자열에서 고정된 길이의 패턴 찾기 

3.2 투 포인터를 적용한 코드 

int start = 0, end = 0, sum = 0;
int max = Integer.MIN_VALUE;

while (end < n) {
     sum += temperarr[end]; // end가 가리키는 값 추가

     // 현재 구간이 k개일 때
     if (end - start + 1 == k) {
          max = Math.max(max, sum);
          sum -= temperarr[start]; // start가 가리키는 값 제거
          start++; // 구간 시작점 앞으로 이동
     }
	end++; // 끝 포인터 이동
}

투 포인터 : 두개의 포인터(인덱스)를 사용해서  조건을 만족하는 부분 구간을 탐색하는 알고리즘 , 슬라이딩 윈도우와 비슷하지만 조건을 만족하는 '가변 길이' 구간을 찾을 때 유용하다. 

시작포인트와 끝 포인트를 같게 한다.

일단 마지막 포인터 (end)를 기준으로 while 루프를 돌린다. 이때 n을 넘지 않게 조건을 줘서 처음 내가 코드를 작성했을때 고려했던 부분이 여기에 반영이 됐다. 

그리고 구간이 성립이 될때만 시작 포인트를 옆으로 이동, 아니면 구간 성립(또는 구간 확장 - 다음 구간 이동의미)을 위한 끝 포인트 이동하는 방식이다. 이렇게 해서 누적합의 최대값을 구한다. 

4. 회고

단순히 맞는게 중요한게 아니라 시간 복잡도를 따지는게 어렵다 생각의 확장이 필요하다