알고리즘 3일차

송재곤/AI·소프트웨어학부(인공지능전공)·2025년 11월 29일

알고리즘 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략

공부 기록

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

어제 배운 내용 복습

핵심 키워드: 슬라이딩 윈도우, O(N), BufferedReader

1. 슬라이딩 윈도우 (Sliding Window)

개념: 고정된 크기( $M$ )의 구간 합이나 평균을 구할 때, 매번 다시 계산하지 않고 "앞의 값은 빼고 뒤의 값은 더하는" 방식.
공식: Sum = Sum - (나가는 값) + (들어오는 값)
효과: 이중 반복문 $O(NM)$ 을 단일 반복문 $O(N)$ 으로 최적화 가능.

2. Java 입출력 & 속도 최적화

입력: Scanner는 느리다. 실전에서는 BufferedReader + StringTokenizer 조합이 필수.
출력: 반복문 안에서 System.out.println 금지. StringBuilder에 모아서 한 번에 출력.
예외처리: main 함수 옆에 throws IOException을 붙여서 에러 처리를 JVM에 떠넘긴다.

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

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

1. 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘 -> 다항 시간 알고리즘

다항시간 알고리즘안에 선형시가 알고리즘이 존재

2. 시간 복잡도가 높으면 알고리즘의 수행시간이 더 빠르게 증가한다는 의미

3. 선택 정렬 알고리즘

모든 i에 대해 $A[i...N-1]$ 에서 가장 작은 원소를 찾은뒤 A[i]와 자리를 교체


public class Main{
	public static void main(String[] args){
    	BufferedReader br = new BufferReader(new InputStreamReader(System.in))
        int N = Integer.parseInt(bf.readLine());
        int[] A = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int k=0; k<N; k++){
        A[k] = Integer.parseInt(st.nextToken());
        }
        
    	for(int i=0; i<N; i++){
        	int minIndex = i;
        	for(j=i+1; j<N; j++){
        		if (A[j] < A[minIndex]){
            		minIndex = j;
                }
            }
            int temp = A[i];
            A[i] = A[minIndex];
            A[minIndex] = temp;
        }
    }
}

4. 삽입 정렬

A[i]에 있던 값을 하나씩 앞으로 옮겨가며 적절한 위치에 삽입
ex) 1 4 7 11 5의 결우 5는 11 -> 7-> 을 지나 4 뒤쪽으로 삽입됨

public class Main{
	public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int k=0; k<N; k++){
        	A[k] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=1; i<N; i++){
        	int j = i-1;
            int target = A[i];
        	while(j>=0 && A[j] > target){
               A[j + 1] = A[j];
                j--;
            }
            A[j + 1] = target;
        }
    }
}