커리큘럼/페이즈 1 · 기본기
5주차

해시: 맵과 셋

'본 적 있나?'와 '몇 번 나왔나?'를 O(1)에 답하는 도구예요.

개념

해시맵은 옷가게의 번호표 보관소라고 생각하면 쉬워요. 옷을 맡기면 번호표를 주고, 나중에 번호표만 내밀면 직원이 곧장 그 칸으로 가서 옷을 꺼내 줘요. 온 매장을 뒤지지 않아요. 여기서 번호표가 열쇠(key), 옷이 값(value)이에요. 열쇠만 주면 그 칸을 O(1)에 찾아 주는 게 해시의 전부예요.2주차에서 반복문 안의 includes가 O(n²)을 만든다는 걸 봤어요. 해시는 정확히 그 문제를 없애는 도구예요. 값을 넣어두면 '있었나?'를 평균 O(1)에 답해요.원리는 단순해요. 값을 해시 함수에 넣어 정수 하나를 얻고, 그 정수를 배열의 인덱스로 써요. 배열 인덱스 접근은 O(1)이니 조회도 O(1)이에요. 서로 다른 값이 같은 칸으로 가는 충돌이 생기지만, 구현체가 알아서 처리하니까 평균적으로는 상수 시간이 유지돼요.

맵과 셋, 무엇을 쓸까

  • 셋(Set) — 값의 존재 여부만 필요할 때. 중복 제거, '본 적 있나' 판정
  • 맵(Map) — 값에 무언가를 붙여야 할 때. 빈도수, 값 → 인덱스, 값 → 목록
하고 싶은 것JavaScriptPython
존재 확인set.has(x)x in s
값 꺼내기map.get(k)d[k] 또는 d.get(k)
기본값과 함께 꺼내기map.get(k) ?? 0d.get(k, 0)
빈도수 한 번에직접 세기Counter(nums)
키 개수map.sizelen(d)

빈도수 세기가 절반이에요

해시 문제의 상당수는 '빈도수를 센 다음 그 결과를 본다'로 풀려요. 세는 코드는 항상 같은 모양이니까 손에 붙여두면 좋아요.[a, b, a, c, a]를 왼쪽부터 하나씩 읽으며 맵이 커지는 과정을 따라가 볼게요. 원소를 볼 때마다 '이미 있으면 +1, 없으면 처음이니까 1'을 해요. get에 기본값 0을 주는 이유가 여기서 보여요 — 처음 보는 열쇠는 0 + 1로 시작하거든요.
[a,b,a,c,a] 빈도수 세기 — 맵이 한 원소씩 자라는 과정
읽은 값   한 일             맵 상태
  (시작)                    { }
   a      0 + 1 -> 1        { a:1 }
   b      0 + 1 -> 1        { a:1, b:1 }
   a      1 + 1 -> 2        { a:2, b:1 }
   c      0 + 1 -> 1        { a:2, b:1, c:1 }
   a      2 + 1 -> 3        { a:3, b:1, c:1 }
​
가장 많이 나온 값 -> a (3번)

패턴 코드

빈도수 세기
javascript
const count = new Map();
for (const x of items) {
  count.set(x, (count.get(x) ?? 0) + 1);
}
본 적 있는지 판정하며 진행하기지금까지 지나온 것만 셋에 넣어두면, 각 원소마다 O(1)에 짝을 찾을 수 있어요.
javascript
const seen = new Set();
for (const x of nums) {
  if (seen.has(target - x)) return true;
  seen.add(x);
}
return false;

이번 주 문제

이번 주 진행0 / 4
주차 진행률
이번 주 주제로 골라둔 문제예요. 채점은 프로그래머스에서 하고, 풀고 나면 여기에 체크해 두세요. 난이도 순으로 보여줘요.
프로그래머스 진행률
  • 완주하지 못한 선수
    Lv. 1풀기
  • 폰켓몬
    Lv. 2풀기
  • 전화번호 목록
    Lv. 2풀기
  • 의상
    Lv. 2풀기
  • 베스트앨범
    Lv. 3풀기

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.
  1. 해시 조회가 평균 O(1)인데 최악에는 O(n)이 될 수 있는 이유는?
  2. JavaScript에서 객체 대신 Map을 써야 하는 상황을 두 가지 말할 수 있는가?
  3. 내용이 같은 두 배열을 같은 키로 묶으려면 어떻게 해야 하는가?
← 4주차 · 완전탐색과 시뮬레이션6주차 · 체크포인트 1 →