슬라이딩 윈도우 설명: 선글라스 비유와 Ruby 코드

Source: Dev.to

선글라스 비유 😎🌄

당신이 언덕 위에 서서 긴 풍경을 바라보고 있다고 상상해 보세요. 이 풍경이 여러분의 배열이나 문자열을 나타내고, 여러분은 한 번에 고정된 부분만 볼 수 있는 특별한 선글라스를 가지고 있습니다 — 이것이 슬라이딩 윈도우입니다.

• 입력되는 요소: 윈도우 오른쪽에서 들어오는 새로운 요소.
• 제거되는 요소: 윈도우 왼쪽에서 나가는 요소.
• 상태 추적: 윈도우 안에서 흥미로운 무언가(예: 합계, 최대값, 고유 요소 개수)를 계속 추적합니다.

각 새로운 위치마다 모든 것을 다시 계산하는 대신 점진적으로 업데이트합니다:

1. 보이지 않게 된 것을 제거합니다.
2. 새로 보이게 된 것을 추가합니다.
3. 결과를 업데이트합니다.

슬라이딩 윈도우 없이

크기 k인 각 윈도우마다 처음부터 모든 것을 다시 계산해야 합니다 → 느림.

슬라이딩 윈도우와 함께

윈도우가 움직일 때 상태를 업데이트합니다 → 빠르고 효율적.

예제 1: 고정 크기 윈도우의 최대 합

# Landscape: array of trees
arr = [1, 2, 3, 4, 5]
k   = 3

# Initial window sum
window_sum = arr[0...k].sum
max_sum    = window_sum

# Slide the window
(1..arr.length - k).each do |i|
  window_sum = window_sum - arr[i - 1] + arr[i + k - 1]
  max_sum    = [max_sum, window_sum].max
end

puts "Maximum sum of a window of size #{k}: #{max_sum}"

설명

• arr[i - 1] 은 윈도우를 떠납니다.
• arr[i + k - 1] 은 윈도우에 들어옵니다.
• window_sum 은 점진적으로 업데이트되어 전체 재계산을 피합니다.

예제 2: ≤ k개의 서로 다른 문자를 갖는 가장 긴 부분 문자열

s = "abcba"
k = 2

count   = Hash.new(0)  # frequency of characters in the current window
left    = 0
max_len = 0

(0...s.length).each do |right|
  count[s[right]] += 1

  # Shrink window from the left while we have more than k distinct chars
  while count.size > k
    count[s[left]] -= 1
    count.delete(s[left]) if count[s[left]] == 0
    left += 1
  end

  max_len = [max_len, right - left + 1].max
end

puts "Length of longest substring with ≤ #{k} distinct characters: #{max_len}"

설명

• s[right] 를 추가하면서 윈도우를 오른쪽으로 확장합니다.
• 서로 다른 문자 수가 k 를 초과하면, 제약이 만족될 때까지 왼쪽에서 윈도우를 축소합니다.
• count 는 윈도우 안의 상태(문자 빈도)를 유지합니다.

핵심 정리

• 두 포인터(left와 right)는 자연스럽게 슬라이딩 윈도우를 나타냅니다.
• 점진적 업데이트에 집중하세요: 새로운 요소를 추가하고, 오래된 요소를 제거하고, 추적 중인 상태를 조정합니다.
• 선글라스 비유를 시각화하면 겉보기에 까다로운 기법을 직관적으로 이해할 수 있습니다.

팁: 선글라스 비유를 사용해 작은 손글씨 예제를 먼저 풀어보고, 그 단계를 코드로 옮겨 보세요. 이렇게 하면 개념이 강화되고 슬라이딩‑윈도우 문제를 해결하기가 훨씬 쉬워집니다. 😎