20250924 위상정렬, 투포인터, 슬라이딩 윈도우 알고리즘

오늘은 위상정렬, 투포인터, 슬라이딩 윈도우 알고리즘에 대해 배웠다.

 

위상 정렬

위상 정렬(Topological Sorting)은 방향 그래프의 정점들을 선형으로 배열하는 방법이다.

주로 사이클이 없고 의존성 문제에서 사용된다.

 

방법

1. 진입 차수 계산 : 각 정점의 진입 차수 (해당 정점으로 돌아오는 간선의 수)를 계산한다.

2. 큐에 추가 : 진입 차수가 0인 정점을 큐에 추가한다.

3. 정점 처리 : 큐에서 정점을 하나씩 꺼내어 결과 리스트에 추가하고, 그 정점과 연결된 모든 정점의 진입 차수를 감소시킨다. 만약 진입 차수가 0이 되는 정점이 있다면 큐에 추가한다.

4. 결과 확인 : 모든 정점을 처리했는지 확인한다. 처리된 정점의 수가 원래 정점의 수와 같다면 위상 정렬이 성공한 것이다.

 

예제 : 백준 1766번 문제집 문제

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 위상정렬 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); // 문제 수
		int M = sc.nextInt(); // 의존 관계 수
		
		// 그래프를 위한 인접 리스트 초기화 
		List<List<Integer>> graph = new ArrayList<>(N + 1);
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList());
		}
		
		// 진입 차수 배열 초기화
		int[] inDegree = new int[N + 1];
		
		// 의존 관계 입력 처리
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			graph.get(a).add(b);
			inDegree[b]++; // 후행 문제의 진입 차수 증가
		}
		
		// 3. 정점 처리를 위해 PQ를 사용
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		// 진입 차수가 0인 문제들을 큐에 추가
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) {
				pq.offer(i);
			}
		}
		// 결과 저장할 리스트
		List<Integer> result = new ArrayList();
		// 큐가 비어있지 않을 때까지 반복
		while (!pq.isEmpty()) {
			int cur = pq.poll();
			result.add(cur);
			// 현재 문제에 의존하는 문제들에 대한 할 일
			for (int n : graph.get(cur)) {
				inDegree[n]--; // 진입 차수 감소
				if (inDegree[n] == 0) { // 진입 차수가 0이 되면
					pq.offer(n); // 큐에 추가
				}
			}
		}
		
		for (int p : result) {
			System.out.print(p + " ");
		}
		
		sc.close();
	}
}

이 문제와 위상 정렬에 대한 이해는 주석으로 달았다.

 

 

투포인터

투포인터 알고리즘은 시간 복잡도를 줄이기 위한 아이디어이고 배열이나 리스트에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘이다. 일반적으로 배열이나 리스트가 정렬되어 있을 때 사용된다.

 

예시 문제

Q> 정렬된 정수 배열 arr과 목표 숫자 target이 주어졌을 때, 배열에서 두 원소의 합이 target과 같은 모든 쌍을 찾아라.

A> 일반적으로 findPairsWithSum1()처럼 이중 루프를 돌리는데 이러면 O(n^2)임. 단순히 두 수를 가리킬 인덱스 변수만 만들어 처리하면 O(n)

 

public class 투포인터 {

	public static void main(String[] args) {
		int[] sortedArr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
		int targetSum = 10;
		
		findPairsWithSum1(sortedArr, targetSum); // 일반적인 방식
		findPairsWithSum2(sortedArr, targetSum); // 투포인터 방식
		
	}
	
	// 일반적인 방식
	private static void findPairsWithSum1(int[] sortedArr, int targetSum) {
		
		boolean found = false;
		
		for (int i = 0; i < sortedArr.length - 1; i++) {
			for (int j = i + 1; j < sortedArr.length; j++) {
				int curSum = sortedArr[i] + sortedArr[j];
				
				if (curSum == targetSum) {
					 System.out.println("(" + sortedArr[i] + ", " + sortedArr[j] + ")");
					 found = true;
				}
			}
		}
		
		if (!found) {
			System.out.println("no pair");
		}
	}
	
	// 투포인터
	private static void findPairsWithSum2(int[] arr, int target) {
		int left = 0; // 왼쪽 포인터 0부터
		int right = arr.length - 1; // 오른쪽 포인터 인덱스끝부터
		
		boolean found = false; // 쌍을 찾았는지 확인하는 플래그
		
		// 정렬되어 있기 때문에 가능
		while (left < right) { // left 포인터가 right 포인터보다 작을 동안만 반복
			int curSum = arr[left] + arr[right];
			if (curSum == target) {
				System.out.println("(" + arr[left] + ", " + arr[right] + ")");
				found = true;
				left++; // 다음 쌍을 찾기 위해 두 포인터 모두 이동
				right--;
			} else if (curSum < target) {
				left++; // 현재 합이 목표보다 작으면 왼쪽을 증가
			} else {
				right--; // 현재 합이 목표보다 크면 오른쪽을 감소
			}
		}
		
		if (!found) {
			System.out.println("no pair");
		}
	}
}

가우스가 1부터 100까지 더한 값을 구할 때처럼 처음과 끝을 차근차근 처리하면서 구하는 방식이다.

 

슬라이딩 윈도우

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.

배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용하다.

 

예시 문제

Q> 정수 배열 arr와 정수 K가 주어졌을 때, 길이가 K인 부분 배열(연속된 K개의 원소) 중에서 그 원소들의 합이 가장 큰 값을 찾아라.

A> 일반적으로 findMaxSumSubarray1()처럼 이중 루프를 돌리는데 이러면 O(n^2)임. 매번 새로운 부분 배열을 다시 계산하는 대신, 윈도우가 한 칸 이동할 때 빠져나가는 원소는 빼고, 새로 들어오는 원소는 더하는 방식으로 계산을 재활용하여 O(N)의 시간 복잡도로 문제를 해결

 

public class 슬라이딩윈도우 {

	public static void main(String[] args) {
		int[] arr = {1, 4, 2, 10, 2, 3, 1, 0, 20};
		int k = 3;
		
		System.out.println(find1(arr, k));
		System.out.println(find2(arr, k));
	}

	private static int find1(int[] arr, int k) {
		int maxSum = Integer.MIN_VALUE;
		
		for (int i = 0; i <= arr.length - k; i++) {
			int curWindowSum = 0;
			for (int j = 0; j < k; j++) {
				curWindowSum += arr[i + j];
			}
			
			maxSum = Math.max(maxSum, curWindowSum);
		}
		
		return maxSum;
	}
	
	private static int find2(int[] arr, int k) {
		int curWindowSum = 0;
		int maxSum = 0;
		
		for (int i = 0; i < k; i++) {
			curWindowSum += arr[i];
		}
		
		maxSum = curWindowSum;
		for (int i = k; i < arr.length; i++) {
			curWindowSum = curWindowSum - arr[i - k] + arr[i];
			maxSum = Math.max(maxSum, curWindowSum);
		}
		
		return maxSum;
	}
}

투포인터, 슬라이딩 윈도우 둘 다 이중 for문의 시간 복잡도를 for문 한 번으로 시간 복잡도를 낮추게 하는 것을 볼 수 있다.

 

느낀 점

투포인터와 슬라이딩 윈도우를 처음 발견하고 써야겠다고 생각한 사람들이 참 똑똑한 것 같다. 신기하기도 하고

똑똑한 사람들이 만든 효율적인 알고리즘을 잘 기억하고 활용해봐야겠다.