빗물 받기·Top K 빈도·선택 정렬, 실행 과정을 눈으로 따라가기

DEV Community

Learn Trapping Rain Water, Top K Frequent and Selection Sort with Step-by-Step Visualization in DSA View View 👀👀

Hoi hoi! I’m @nyaomaru, a frontend engineer who has been obsessed with ramen lately. 😸🍜 Have you...

nyaomaru · 2026-09-09

개요 #

알고리즘 문제를 풀 때 막히는 지점은 문법이 아니다. 변수 하나하나는 다 이해했는데, 그것들이 동시에 어떻게 변하는지를 머릿속에 담아두기가 어렵다.

프런트엔드 엔지니어 nyaomaru가 만든 DSA View View는 바로 그 지점을 겨냥한 도구다. TypeScript로 구현한 코드를 직접 넣고 실행하면, 실행 중간의 상태 변화를 한 단계씩 앞뒤로 오가며 볼 수 있다. 앞선 글에서는 Two Sum, 이진 탐색, 버블 정렬, 유효한 괄호, 연결 리스트 뒤집기, 이진 트리 최대 깊이, 섬의 개수, 이진 트리 반전, 코스 스케줄을 다뤘다.

이번 글이 고른 문제는 세 개다. 빗물 받기(Trapping Rain Water), Top K Frequent Elements, 선택 정렬. 코드 분량은 크지 않다. 대신 문제마다 꽤 쓸모 있는 사고 패턴이 하나씩 들어 있다.

양쪽에서 문제를 좁혀 들어가기
먼저 세고, 빈도 기준으로 다시 정리하기
다음에 올 값을 반복해서 골라내기

도구 소개 글 보기 →

🌧️ 빗물 받기 (Trapping Rain Water) #

높이 배열이 이렇게 주어졌다고 하자.

[0, 1, 0, 2, 1, 0, 1, 3]

벽으로 그리면 대략 이런 모양이다.

              █
      █       █
  █   █ █   █ █
-----------------
0 1 0 2 1 0 1 3

위에서 비가 내린다. 일부는 흘러나가고, 일부는 더 높은 벽 사이에 갇힌다.

      █~~~~~~~█
  █~~~█~~~~~~~█
-----------------

물이 얼마나 고일까?

원문 작성자도 이 문제가 처음엔 헷갈렸다고 한다. 어떤 위치 위에 고이는 물의 양이, 그 위치가 아니라 다른 어딘가의 벽에 달려 있기 때문이다.

Photo by ardeshir etemad on Pexels

한 칸 위에 물이 얼마나 들어갈까 #

이런 상황을 떠올려 보자.

왼쪽 벽        오른쪽 벽
    █             █
    █      x      █
    █      █      █

수위는 더 낮은 쪽 벽을 넘을 수 없다. 그러니 가능한 최대 수위는 이렇게 된다.

Math.min(leftMax, rightMax);

여기서 현재 높이를 빼면 그 칸에 고이는 물의 양이다.

water = min(leftMax, rightMax) - currentHeight

기본 아이디어는 여기까지다. 그런데 모든 위치마다 양쪽을 다시 계산해야 할까? 그럴 필요 없다. 투 포인터를 쓰면 된다.

투 포인터 구현 #

function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;

  let leftMax = 0;
  let rightMax = 0;

  let water = 0;

  while (left <= right) {
    if (height[left] <= height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }

      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }

      right--;
    }
  }

  return water;
}

추적해야 할 값이 다섯 개다.

left
right
leftMax
rightMax
water

변수 하나씩 보면 다 알겠는데, 한꺼번에 놓고 보면 놓치기 시작하는 딱 그런 코드다. 더 작은 예제로 따라가 보자.

[2, 0, 1, 3]

양 끝에서 시작 #

처음 상태는 이렇다.

left = 0
right = 3

[2, 0, 1, 3]
 ↑        ↑
left    right

높이를 보면

height[left]  = 2
height[right] = 3

2 <= 3이니 왼쪽을 처리한다. 높이 2짜리 벽이 있으므로

leftMax = 2

그리고 left를 한 칸 옮긴다.

[2, 0, 1, 3]
    ↑     ↑
   left right

이제 물이 고인다 #

현재 높이는 0이다. 하지만 왼쪽에 높이 2짜리 벽이 있다는 걸 이미 안다. 오른쪽도 최소한 그만큼은 높다. 그러니 이 칸에 담기는 물은

leftMax - height[left]
= 2

water = 2

한 번 더 옮긴다.

[2, 0, 1, 3]
       ↑  ↑
      left right

이번엔

height[left] = 1
leftMax = 2

2 - 1 = 1, 물 한 단위가 더 쌓인다.

water = 3

마지막 벽까지 도달하면 끝이다. 🎉

왜 낮은 쪽을 먼저 처리해도 되나 #

여기가 핵심이다. height[left] <= height[right]라면, 오른쪽 어딘가에 현재 왼쪽 벽만큼은 높은 벽이 있다는 뜻이다.

그래서 지금 왼쪽 위치를 제한하는 건 오른쪽이 아니라 지금까지 본 왼쪽 최대 벽이다. 앞으로 나올 모든 벽을 몰라도 이렇게 계산할 수 있다.

leftMax - height[left];

반대쪽도 논리가 같다. height[right] < height[left]면 rightMax를 써서 오른쪽을 처리한다. 알고리즘은 미확정 구간을 계속 좁혀 나간다.

L → → →     ← ← ← R

복잡도 #

각 포인터가 배열을 한 번씩만 지난다.

Time:  O(n)
Space: O(1)

👀 실행을 직접 보기 #

시각화가 특히 잘 맞는 문제다. left, right, leftMax, rightMax, water가 서로 다른 시점에 바뀌기 때문이다.

아래 한 줄만 읽으면 이런 의문이 남는다.

water += leftMax - height[left];

• 왜 여기서 leftMax를 쓰지?
• 지금 rightMax는 뭐지?
• 왜 right가 아니라 left를 옮겼지?
• 지금까지 센 물은 얼마지?
• 배열의 어디까지가 아직 미처리지?

빗물 받기 시각화 실행해 보기 →

한 단계씩 보면 탐색 구간이 실제로 좁아지는 게 보인다.

L         R
↓         ↓
[2, 0, 1, 3]

    L     R
    ↓     ↓
[2, 0, 1, 3]

       L  R
       ↓  ↓
[2, 0, 1, 3]

이 알고리즘이 매 단계 던지는 질문은 사실 하나다. 지금 안전하게 풀 수 있는 쪽은 어디인가? 그쪽을 풀고 안으로 들어간다.

🔢 Top K Frequent Elements #

다음은 가장 자주 등장하는 K개를 찾는 문제다.

[1, 1, 1, 2, 2, 3]
k = 2

각 숫자의 등장 횟수를 세면

1 → 3번
2 → 2번
3 → 1번

답은 [1, 2]다. 개념은 간단한데, 구현은 어떻게 할까?

먼저 전부 센다 #

필요한 건 빈도다. Map을 쓴다.

const frequency = new Map<number, number>();

값마다 카운트를 올린다.

for (const num of nums) {
  frequency.set(num, (frequency.get(num) ?? 0) + 1);
}

[1, 1, 1, 2, 2, 3]을 넣으면

frequency = {
  1 → 3
  2 → 2
  3 → 1
}

여기서 상위 K개를 뽑아야 한다. 빈도 기준으로 전부 정렬해도 되지만, 더 흥미로운 방법이 있다.

빈도를 인덱스로 쓴다 #

가능한 최대 빈도는 nums.length다. 그만큼 버킷을 만든다.

const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);

인덱스가 곧 빈도다.

bucket[1] = 1번 등장한 값들
bucket[2] = 2번 등장한 값들
bucket[3] = 3번 등장한 값들

예제를 넣으면 이렇게 된다.

index 0 → []
index 1 → [3]
index 2 → [2]
index 3 → [1]

관계가 뒤집혔다는 게 포인트다. 원래는 이렇게 물었다.

이 숫자의 빈도는 얼마인가?

이제는 이렇게 묻는다.

이 빈도를 가진 숫자는 무엇인가?

전체 구현 #

function topKFrequent(nums: number[], k: number): number[] {
  const frequency = new Map<number, number>();

  for (const num of nums) {
    frequency.set(num, (frequency.get(num) ?? 0) + 1);
  }

  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);

  for (const [num, count] of frequency) {
    buckets[count].push(num);
  }

  const result: number[] = [];

  for (let count = buckets.length - 1; count >= 0; count--) {
    for (const num of buckets[count]) {
      result.push(num);

      if (result.length === k) {
        return result;
      }
    }
  }

  return result;
}

1단계: 빈도 맵 만들기 #

빈 상태에서 시작한다.

frequency = {}

첫 1을 읽고, 또 하나, 또 하나.

1 → 1
1 → 2
1 → 3

2도 두 번.

1 → 3
2 → 1
2 → 2

마지막으로 3.

1 → 3
2 → 2
3 → 1

2단계: 버킷에 넣기 #

buckets[count].push(num);

1 → 3이니 buckets[3].push(1), 2 → 2니 buckets[2].push(2), 3 → 1이니 buckets[1].push(3).

0: []
1: [3]
2: [2]
3: [1]

3단계: 높은 빈도부터 읽기 #

가장 자주 나온 값이 필요하니 0이 아니라 끝에서 시작한다.

3 → [1]
2 → [2]
1 → [3]

1을 담는다.

result = [1]

하나 더 필요하니 아래로 내려가 2를 담는다.

result = [1, 2]

result.length === k가 됐으니 반환. 끝이다. 🎉

이 풀이가 흥미로운 이유 #

두 번째 자료구조가 보는 방향을 바꿔 준다는 점이다.

Map은 이렇게 말한다.

값 → 빈도

버킷은 이렇게 말한다.

빈도 → 값들

담긴 정보는 같은데 방향이 반대다. 그 덕에 가장 자주 나온 값을 찾는 일이 버킷을 뒤에서부터 훑는 것만으로 끝난다.

복잡도 #

모든 숫자를 한 번 세고, 고유한 숫자를 버킷에 나눠 담고, 버킷을 훑는다.

Time:  O(n)
Space: O(n)

👀 실행을 직접 보기 #

여기서는 변환이 두 번 일어난다.

nums
 ↓
frequency Map
 ↓
buckets
 ↓
result

완성된 코드만 읽으면 왜 자료구조를 두 개나 만드는지 놓치기 쉽다.

Top K Frequent 시각화 실행해 보기 →

실행 과정이 보이면 데이터의 모양이 바뀌는 흐름을 그대로 따라갈 수 있다.

[1, 1, 1, 2, 2, 3]
        ↓ count
1 → 3
2 → 2
3 → 1
        ↓ bucket
1: [3]
2: [2]
3: [1]
        ↓ highest first
[1, 2]

상위 K개를 마법처럼 찾아내는 게 아니다. 답이 읽기 쉬워질 때까지 정보를 재배치할 뿐이다.

👉 선택 정렬 (Selection Sort) #

마지막은 정렬이다. 앞선 글에서 버블 정렬을 다뤘으니, 이번엔 선택 정렬 차례다.

[5, 3, 4, 1, 2]

를 이렇게 만들고 싶다.

[1, 2, 3, 4, 5]

선택 정렬의 아이디어는 한 줄이면 끝난다.

남은 값 중 가장 작은 값을 찾아서 앞으로 보낸다.

그리고 반복한다.

첫 번째 패스 #

시작 상태다.

[5, 3, 4, 1, 2]
 ↑
 i

일단 첫 값이 가장 작다고 가정한다.

minIndex = 0

오른쪽을 전부 훑는다. 5 vs 3에서 3이 더 작으니

minIndex = 1

3 vs 4는 변화 없음. 3 vs 1에서 1이 더 작으니

minIndex = 3

1 vs 2는 여전히 1. 최솟값은 인덱스 3에 있다. 교환한다.

[5, 3, 4, 1, 2]
 ↑        ↑
 i       min

↓

[1, 3, 4, 5, 2]

첫 자리가 확정됐다.

[1 | 3, 4, 5, 2]
 ↑
정렬 완료

반복 #

다음은 인덱스 1부터다.

[1 | 3, 4, 5, 2]
     ↑
     i

[3, 4, 5, 2]에서 가장 작은 값은 2. 교환한다.

[1, 2 | 4, 5, 3]

또 반복해서 남은 최솟값 3을 찾고, 결국

[1, 2, 3, 4, 5]

정렬 완료. 🎉

구현 #

function selectionSort(nums: number[]): number[] {
  for (let i = 0; i < nums.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }

  return nums;
}

핵심 인덱스는 i와 minIndex 둘이고, 미정렬 구간을 훑는 j가 하나 더 있다.

왜 '선택' 정렬인가 #

매 패스마다 남은 값 중 최솟값을 선택하기 때문이다.

최솟값 찾기
  ↓
선택
  ↓
앞으로 보내기
  ↓
반복

이게 알고리즘의 전부다.

복잡도 #

위치마다 남은 값을 전부 훑는다.

Time: O(n²)

배열을 제자리에서 정렬한다.

Space: O(1)

원문 작성자도 프로덕션의 큰 데이터셋을 정렬할 때 선택 정렬을 고르진 않겠다고 적었다. 다만 학습용 알고리즘으로는 눈으로 보기 좋은 편이다.

👀 실행을 직접 보기 #

구현에 중첩 반복문이 들어 있다.

for (let i = 0; i < nums.length - 1; i++) {
  let minIndex = i;

  for (let j = i + 1; j < nums.length; j++) {

코드만 읽다 보면 이런 게 흐려진다.

• 어디까지가 이미 정렬된 구간이지?
• i는 어디 있지?
• j는 어디 있지?
• 지금 minIndex는 뭘 가리키지?
• 교환은 정확히 언제 일어나지?

선택 정렬 시각화 실행해 보기 →

시각화하면 패턴이 단순하게 드러난다.

[5, 3, 4, 1, 2]
          ↑
        최솟값

[1 | 3, 4, 5, 2]
              ↑
            최솟값

[1, 2 | 4, 5, 3]

완성된 구간이 왼쪽에서 오른쪽으로 계속 자란다. 남은 값 중 최솟값을 골라 다음 자리에 놓고, 또 반복한다.

🧠 세 문제가 남기는 것 #

세 문제는 겉보기엔 전혀 다르다. 그런데 각각 쓸모 있는 사고방식을 하나씩 담고 있다.

빗물 받기 — 양쪽 정보를 비교해서 지금 안전하게 풀 수 있는 구간을 판단한다.

지금 내가 충분히 알고 있는 쪽은 어디인가?

Top K Frequent Elements — 데이터를 세는 건 첫 단계일 뿐이다. 답을 꺼내기 쉬운 구조로 다시 정리한다.

내게 정말 필요한 것을 기준으로 정보를 재배치할 수 있을까?

선택 정렬 — 확정된 자리를 하나씩 늘려가며 답을 만든다.

이 자리에 들어갈 값은 무엇인가?

정리하면 투 포인터, 빈도 버킷, 선택. 세 가지 다른 사고 모델이다.

앞선 문제들과 마찬가지로, 어려운 쪽은 문법이 아니라 변하는 상태다.

어느 포인터가 움직였지?
지금 최댓값은 뭐지?
Map 안에는 뭐가 들었지?
어느 버킷이 바뀌었지?
minIndex는 어디지?
어디까지 끝났지?

머릿속에 담고 있기엔 양이 많다. 그래서 보자는 것이다. 👀👀

🎯 마무리 #

이번 글이 다룬 건 세 가지다.

• 투 포인터로 푸는 빗물 받기
• 빈도 버킷으로 푸는 Top K Frequent Elements
• 선택 정렬

그보다 중요한 건, 실행되는 동안 상태가 어떻게 변하는지를 따라가 봤다는 점이다.

빗물 받기에서는 두 포인터가 안쪽으로 좁혀 들어가는 동안 leftMax, rightMax, water가 바뀌는 걸 봤다.

left →       ← right

Top K Frequent Elements에서는 같은 데이터가 표현을 바꿔 가는 걸 봤다.

array
  ↓
frequency Map
  ↓
buckets
  ↓
result

선택 정렬에서는 정렬된 구간이 한 칸씩 자라는 걸 봤다.

nyaomaru가 DSA View View를 만든 이유가 바로 이것이다. TypeScript 구현을 작성하거나 불러와서 직접 만든 입력으로 실행하고, 실행 과정을 앞뒤로 오가며 확인할 수 있다.

DSA View View 사용해 보기 →

GitHub 저장소 보기 →

원문 작성자는 다음에 다뤘으면 하는 DSA 문제가 있으면 댓글로 알려 달라고 덧붙였다.

이 글은 위 출처를 바탕으로 한국 독자를 위해 재작성한 기사입니다. 원문의 사실과 수치에 근거하며, 별도의 견해를 포함하지 않습니다.