공부 기록 - Chapter 4.4

날짜: 2025년 11월 28일
학습 범위: ~ p.100

---

💡 책에서 새롭게 알게 된 내용 메모

책을 읽으며 중요하다고 느낀 개념, 공식, 팁을 적습니다.

1. 점화식을 통해 overflow를 해결할 수도 있음

2. Mantissa = fraction

• 소수의 표기 = $(-1)^n *(1+fraction)*2^{bias - exponent}$

3. O(N): 선형 시간 알고리즘 -> N값에 정비례

4. 이진탐색 : $\frac{N}{2}$을 반복적으로 수행함으로써 N을 하나씩 탐색하지 않고 값을 찾음

• ex) 1~N에서 $x$라는 미지수를 찾고 싶음. $x$보다 큰지 작은지는 알려줌

설정:
  low (범위 시작) = 1
  high (범위 끝) = N

반복 (low가 high보다 작거나 같을 때까지):
  1. 중간값(mid)을 구한다. -> (low + high) / 2
  
  2. 만약 (mid == x) 라면:
     - 찾음 -> 종료
     
  3. 만약 (mid < x) 라면: (x가 중간보다 큰 쪽에 있다)
     - x는 오른쪽에 있으므로, 왼쪽 절반을 버린다.
     - low를 mid + 1로 변경한다.
     
  4. 만약 (mid > x) 라면: (x가 중간보다 작은 쪽에 있다/Down)
     - x는 왼쪽에 있으므로, 오른쪽 절반을 버린다.
     - high를 mid - 1로 변경한다.

코드 

	public class BinarySearch {
    	public static void main(String[] args) {
       		int N = 100; // 1 ~ 100까지 숫자
       		int x = 73;  // 우리가 찾아야 할 미지수 (예시)
        
       		// 탐색 시작
        	int result = search(N, x);
       		System.out.println("찾은 숫자: " + result);
   		}

    	public static int search(int N, int target) {
       		int low = 1;      // 탐색 범위 시작
        	int high = N;     // 탐색 범위 끝
        
       		// low가 high보다 커지면 범위가 꼬인 것이므로 종료 (못 찾음)
       		while (low <= high) {
            	int mid = (low + high) / 2; // 중간 위치 계산
            
            	if (mid == target) {
                	return mid; // 정답을 찾음!
            	} else if (mid < target) {
                	// (중간값보다 크다 -> 오른쪽 구역으로 이동)
                	low = mid + 1;
            	} else {
                	// (중간값보다 작다 -> 왼쪽 구역으로 이동)
                	high = mid - 1;
            	}
        	}
        
        	return -1; // 못 찾았을 때
    	}
	}

---

문제 1. 이동평균 구하기

1) 문제 분석

• 요구사항: N개의 측정치가 주어질때 매달 M달 간의 이동평균을 계산하는 프로그램
• 내 생각(접근법):
  1. 각 위치에서 측정치의 합 / 측정치 개수

2) 풀이

public class Main {
    public static void main(String[] args) throws IOException {
        // 1. 입력 준비
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 예시: 12개의 데이터가 공백으로 구분되어 들어온다고 가정
        // 입력 예: 10.0 20.0 30.0 ...
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = 12; // 데이터 개수
        int M = 3;  // 이동평균 구간 (예: 3달 간의 평균)
        
        float[] weight = new float[N]; // 측정치 저장 배열
        
        // 2. 데이터 배열에 담기
        for(int i = 0; i < N; i++) {
            // 문자열 토큰을 꺼내서 float로 변환하여 저장
            weight[i] = Float.parseFloat(st.nextToken());
        }

        // 3. 이동평균 계산 (단순 이중 반복문 방식)
        // M-1번 인덱스부터 시작해야 M개를 묶을 수 있음 (예: 2번 인덱스여야 0,1,2 3개 가능)
        for(int i = M - 1; i < N; i++) {
            float sum = 0;
            
          
            for(int j = 0; j < M; j++) {
                sum += weight[i - j];
            }
            
            float avg = sum / M;
            System.out.print(avg + " "); // 결과 출력
        }
    }
}

3) 정답

2번도 정답이지만 N의 개수 즉 긴 기간동안의 이동평균을 계산하려면?

• 기존 방식 (이중 반복문):
  구간 1: 10 + 20 + 30 = 60 (연산 2회)
  구간 2: 20 + 30 + 40 = 90 (연산 2회) → 20+30을 또 계산
• 슬라이딩 윈도우:
  구간 1: 10 + 20 + 30 = 60
  구간 2: 60 - 10 + 40 = 90 (연산 2회) → 무조건 더하기/빼기 한 번씩만 하면 됨.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 예시 입력: 12개 데이터 (10.0 20.0 30.0 ...)
        // StringTokenizer st = new StringTokenizer(br.readLine()); // 실제 문제 풀이용
        
        String input = "10.0 20.0 30.0 40.0 50.0 60.0 70.0 80.0 90.0 100.0 110.0 120.0";
        StringTokenizer st = new StringTokenizer(input);
        
        int N = 12; // 전체 데이터 개수
        int M = 3;  // 이동평균 구간 (3달)
        
        float[] weight = new float[N];
        
        // 1. 데이터 입력 받기
        for(int i = 0; i < N; i++) {
            weight[i] = Float.parseFloat(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        
        // 2. [초기 세팅] 첫 번째 윈도우 (0월 ~ M-1월) 합 구하기
        float currentSum = 0;
        for(int i = 0; i < M; i++) {
            currentSum += weight[i];
        }
        
        // 첫 번째 구간(1~3월) 평균 기록
        sb.append(String.format("%.1f ", currentSum / M));

        // 3. [슬라이딩] 윈도우 밀기 (M월부터 끝까지)
        // i는 "새로 들어오는 데이터"의 인덱스입니다.
        for(int i = M; i < N; i++) {
            // 핵심 로직: 기존 합 + (새로운 값) - (빠져나가는 값)
            // 들어오는 값: weight[i]
            // 빠지는 값: weight[i - M] (현재 위치보다 M칸 앞에 있는 녀석)
            currentSum = currentSum + weight[i] - weight[i - M];
            
            // 평균 계산 후 버퍼에 담기
            sb.append(String.format("%.1f ", currentSum / M));
        }

        // 결과 출력
        System.out.println(sb.toString());
    }
}