[알고리즘] 해시(Hash) / 백준 1302, 1920 / 프로그래머스 의상, 베스트앨범

안녕하세요. 오늘은 알고리즘 - 해시 관련 글입니다.

최근 안드로이드 공부에만 몰두해 있었는데, 공고들을 보고 마음이 심란해져 늦게나마 알고리즘 공부에 다시 뛰어들었습니다.

앞으로는 알고리즘도 꾸준히 공부해보려고 해요.

첫 번째 글은 해시입니다.

 

해시(Hash)란?

“데이터를 섞어서(변환해서)” 특정한 위치로 보내주는 함수나 방법을 의미합니다.

즉, 어떤 입력(문자열, 숫자, 키 등)을 받아서, 그것을 인덱스(배열의 위치) 같은 것으로 바꾸는 과정이죠.

 

해시함수(hash function)는 임의 길이의 입력값을 받아서 고정 크기의 값으로 바꾸는 함수입니다. 이 값을 해시 값(hash value) 또는 해시 코드(hash code)라고 불러요.

 

ex)

• 문자열 "apple" → 해시 함수 → 정수 37
• 숫자 1234567 → 해시 함수 → 정수 45
• 객체 “학생” → 해시 → 정수 23

이 해시 값은 배열 같은 자료 구조의 인덱스로 사용이 가능합니다.

 

이제 해시가 무엇인지는 이해가 갑니다.

그럼 왜 이렇게 변환할까요?

 

배열에서는 인덱스가 붙어 있으니까, 인덱스만 알면 O(1) 시간(상수 시간)에 접근이 가능합니다.

하지만 우리가 다루는 데이터는 문자열, 복합 객체, 키-값 쌍 등이고, 그것들이 배열 인덱스 형태로 바로 존재하지는 않습니다.

 

따라서 해시는 키(key)를 배열 인덱스처럼 사용할 수 있게 중간 다리를 놓는 역할을 해주는 겁니다.

⇒ 키를 해시 함수로 변환 → 배열 인덱스 → 거기에 값 저장 또는 조회

이 과정을 통해 검색, 삽입, 삭제를 빠르게 할 수 있다는 장점이 있습니다.

 

이제 코드로 봅시다.

fun main() {
    // 키-값 쌍: HashMap
    val map = HashMap<String, Int>()        // 또는 hashMapOf<String, Int>()
    map["apple"] = 3                        // 삽입 / 갱신
    println(map["apple"])                   // 조회 (3)
    println(map.containsKey("orange"))      // 키 존재 확인 → false
    map.remove("apple")                     // 삭제

    // 고유 원소 집합: HashSet
    val set = HashSet<Int>()                // 또는 hashSetOf<Int>()
    set.add(10); set.add(10)                // 중복 무시 → {10}
    println(set.contains(10))               // true
    set.remove(10)
}

HashMap → 키(key)와 값(value)을 한 쌍으로 저장

HashSet → 값 자체만 저장, 중복 제거 용도

내부적으로 둘 다 해시 테이블(Hash Table) 구조를 사용합니다.

⇒ 삽입/삭제/검색 평균 시간복잡도는 O(1)

 

이때 제가 알아보며 궁금했던 점도 정리해볼게요.

val map = HashMap<String, Int>() 가 있을 때, 미리 value(Int)를 0으로 초기화해 둘 수는 없을까?

정답은 “없습니다”입니다.

HashMap은 필요한 key가 생길 때만 공간을 만드는 구조예요.

 

따라서

val map = HashMap<String, Int>()
map["apple"] = (map["apple"] ?: 0) + 1

이런 식으로

• "apple" 키가 처음 등장했을 땐 map["apple"]이 없으니까 null → ?: 0으로 0으로 간주
• 0 + 1 → 1로 저장
• 다음에 "apple"이 또 들어오면 기존 값 1 + 1 → 2로 갱신

으로 진행됩니다.

배열처럼 전부 0으로 미리 채워두고 진행하는 것이 아닌, 필요한 키가 생기면 그때 그 value가 null이면 0으로 간주하는 등의 방식으로 진행이 됩니다.

 

해시 테이블(Hash Table)

해시 기법을 실제 자료구조로 구현한 것이 해시테이블입니다.

해시 테이블 구조

내부적으로 배열을 쓰고, 해시 함수를 통해 키를 배열 인덱스로 변환해서 값을 저장하는 자료 구조입니다.

키와 값의 쌍(key-value pair)을 저장하는 게 일반적입니다.

• key: 우리가 입력하는 이름, 문자열, 객체 등
• value: 그 key에 대응하는 데이터
• 해시함수: key → 정수 해시 값
• 배열 슬롯: 해시 값을 배열 내 인덱스로 변환해서 저장

⇒ 해시 테이블은 해시 함수를 이용해 키를 인덱스로 바꾸고, 배열 기반 구조에서 빠른 접근을 제공합니다.

 

저는 여기서 또 이런 의문이 들었어요.

HashMap은 key로만 value를 찾을 수 있는 걸까? value로 key를 찾을 수는 없나?

없습니다.

HashMap은 “key → value” 단방향 구조입니다.

따라서 반대로는 찾을 수가 없어요.

val map = hashMapOf("apple" to 3, "banana" to 5)
println(map["apple"]) // 3 조회
println(map[3])       // null

• key "apple"을 주면 3을 찾아줍니다.
• 하지만 3으로 "apple"을 찾는 건 불가능해요.

이유는 내부 구조 때문입니다.

HashMap은

“key → hashCode() → 인덱스 → value”로 작동해서,

value 쪽엔 해시 정보가 없거든요.

 

따라서 value를 활용해야 한다면 직접 모든 엔트리를 돌면서 찾아야 합니다.

해시 테이블로 할 수 있는 작업과 시간 복잡도

해시 테이블은 보통 다음 작업들을 지원합니다.

• 삽입(insert)
• 조회 / 검색(lookup, get)
• 삭제(delete)

이론적으로는 평균적으로 O(1) 시간에 모든 작업을 할 수 있어요.

즉, 입력 크기에 비례해서 시간이 늘어나지 않아, 아주 빠릅니다.

 

하지만 실제로는 완전히 항상 O(1)은 아니고, 경우에 따라 느려질 수 있습니다.

왜냐면 충돌이라는 문제가 있기 때문이에요.

해시의 핵심 문제: 충돌

충돌이란 뭘까요?

서로 다른 두 키(key)가 해시 함수를 거쳐 같은 해시 값, 즉 같은 배열 인덱스로 가는 경우입니다.

 

ex)

• "abc" → 해시 → 5
• "xyz" → 해시 → 5

이럴 때 둘 다 인덱스 5 위치에 저장해야 하는데, 배열 하나 자리에 두 개를 넣을 수 없으니 충돌이 납니다.

 

그럼 이러한 경우, 충돌을 어떻게 해결할까요?

충돌 해결 전략 1 - 체이닝(Chaining, 연결 리스트 방식)

배열의 각 슬롯(인덱스 위치)에 여러 개의 값을 저장할 수 있도록 리스트(혹은 연결 리스트, 혹은 버킷(bucket)) 구조를 두는 방법입니다.

• 인덱스 i → 연결 리스트
• 충돌이 나면 해당 슬롯의 리스트에 추가
• 조회할 때 리스트 내에서 키를 찾아야 함

ex)

0 → LinkedList [ (key1, value1) ]
1 → LinkedList [ (key2, value2), (key3, value3) ]  ← 충돌이 발생해서 두 개 있음
2 → 빈 리스트

이 방식은 구현이 직관적이고, 배열 크기 대비 많은 충돌이 있을 때도 어느 정도 유연합니다.

충돌 해결 전략 2 - 개방 주소법(Open Addressing)

충돌이 나면 “빈 슬롯(empty slot)”을 찾아서 다른 인덱스에 저장하는 방식입니다.

즉, 처음 충돌된 슬롯이 아니라 다음 빈 곳을 찾는 거죠.

 

이 방법에는 또 다양한 빈 슬롯을 찾는 방식이 있습니다.

• 선형 탐사(linear probing): 충돌이 나면 인덱스 +1, +2, +3 .. 순서로 탐사
• 이차 탐사(quadratic probing): 충돌이 나면 +1², +2², +3² … 식으로 탐사
• 이중 해싱(double hashing): 두 개의 해시 함수를 써서 충돌 시 다른 해시를 사용하는 방법

개방 주소법은 메모리를 연속적으로 쓰는 장점이 있고, 캐시 효율이 좋지만, 탐사 거리가 길어지면 느려진다는 단점이 있습니다.

 

충돌이 많아지면 뭐가 나빠질까요?

• 연결 리스트가 길어져서, 조회 시 리스트를 순회해야 해요. → 시간이 늘어남
• 개방 주소법에서는 탐사 거리가 길어져서 빈 슬롯을 찾는 데 오버헤드가 커집니다.

즉, 해시 테이블의 성능이 O(1)에서 O(n) 쪽으로 떨궈질 수도 있습니다. 그래서 해시 함수 설계, 버킷 크기, 충돌 해결 방식 등이 중요해요.

 

그럼 이 해시 함수 설계, 뭘 고려해야 할까요?

해시 함수 설계 원칙

좋은 해시 함수는 다음 특성을 가지고 있어야 합니다.

• 결정적
• 같은 키를 입력하면 항상 같은 해시 값을 내야 합니다.
• 균등 분포
• 가능한 해시 값 범위(버킷들) 사이에 키들이 골고루 퍼지는 게 좋아요
• 빠른 계산 속도
• 충돌 최소화

이 기준들을 중요하게 생각하고 설계해야 해요.

 

Kotlin 제공 해시 함수

근데 사실 Kotlin의 모든 객체는 기본적으로 hashCode() 메서드를 가지고 있어요.

이게 바로 해시 함수 역할을 하는 거예요.

fun main() {
    println("apple".hashCode())
    println("banana".hashCode())
    println("apple".hashCode()) // 항상 같은 값 (결정적)
}

• 문자열 "apple"은 항상 같은 해시코드 반환 → 결정적
• "apple"과 "banana"는 해시코드가 다른 값 → 충돌 확률 낮음

하지만 무한히 많은 문자열에 대해 완벽히 충돌이 없을 수는 없습니다.

 

근데 사실 우리가 해시 함수를 직접 설계할 일은 거의 없습니다. ㅎㅎ

HashMap과 HashSet 등을 사용할 때 내부적으로 hascode가 동작해서 자동으로 인덱스를 설정해 주기 때문이에요.

따라서 우리가 해시를 사용할 때는 key와 value만 신경 쓰면 됩니다.

나머지 해시 계산, 충돌 관리, 인덱스 저장 등은 전부 내부에서 처리돼요.

 

그럼에도 위와 같은 내용을 돌아본 이유는 내부적 구조는 알고 써야 하니까 !

실전 문제 풀이

그럼 이제 해시가 뭔지, 어떻게 작동하는지 이해했으니 실제 문제에서 적용해 봅시다.

백준 1302 - 베스트셀러

이 문제는 책 제목이 여러 번 주어질 때, 가장 많이 나온 책 제목을 찾는 문제입니다.

key를 책 제목(String)으로, value를 책이 팔린 횟수(Int)로 잡으면 되겠죠.

private val br = System.`in`.bufferedReader()

fun main() = with(System.`out`.bufferedWriter()) {
    val map = HashMap<String, Int>()

    val n = br.readLine().toInt()
    repeat(n) {
        val title = br.readLine()
        map[title] = (map[title] ?: 0) + 1
    }

    var bestTitle = ""
    var bestCount = 0
    for ((title, count) in map) {
        if (count > bestCount || (count == bestCount && title < bestTitle)) {
            bestTitle = title
            bestCount = count
        }
    }

    write(bestTitle)
    close()
}

저는 이렇게 풀어서 통과했습니다.

입력값을 HashMap에 넣고 value 값인 count를 활용해 최댓값을 구해서 가장 많이 팔린 책의 title을 출력했어요.

 

백준 1920 - 수 찾기

이 문제는 두 개의 리스트가 주어졌을 때 두 번째 리스트의 숫자들이 첫번째 리스트에 있는지 확인하는 문제입니다.

저는 key를 주어진 정수(Int), value를 있는지 없는지를 판단하는 0,1(Int)로 잡았어요.

private val br = System.`in`.bufferedReader()

fun main() = with(System.`out`.bufferedWriter()) {
    val n = br.readLine().toInt()
    var nList = intArrayOf()
    nList = br.readLine().split(" ").map { it.toInt() }.toIntArray()

    val m = br.readLine().toInt()
    var mIntList = intArrayOf()
    val mList = HashMap<Int, Int>()
    mIntList = br.readLine().split(" ").map { it.toInt() }.toIntArray()

    for(i in 0 until m){
        mList[mIntList[i]] = 0
    }

    for (i in 0 until n){
        if (nList[i] in mList){
            mList[nList[i]] = 1
        }
    }

    for (i in 0 until m){
        write(mList[mIntList[i]].toString()+"\\n")
    }

    close()
}

첫번째 리스트, 두번째 리스트를 모두 리스트에 집어넣은 뒤에 두번째 리스트를 HashMap에 넣고 진행했습니다.

뭔가 코드가 좀 지저분하기는 한데, 통과했습니다. 틀리지는 않았어요.

 

프로그래머스 - 의상

이 문제는 의상 종류별로 겹치지 않는 조합을 만드는 문제입니다.

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]], [["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]

위와 같이 입력이 들어올 때, 정말 어떤 의상인지는 중요하지 않고 의상 종류별 개수를 세어서 계산했습니다.

⇒ headgear = 2개, eyewear = 3개 이런 식으로

 

fun solution(clothes: Array<Array<String>>): Int {
    var answer = 1
    val map = HashMap<String, Int>()

    for (item in clothes) {
        val category = item[1]
        map[category] = (map[category] ?: 0) + 1
    }

    for ((type, count) in map) {
        answer *= (count + 1)
    }

    return answer - 1
}

따라서 clothes [i][1](의상 종류)만 뽑아서 key로 쓰고 해당 개수를 value로 사용했어요.

통과했습니다.

 

프로그래머스 - 베스트앨범

이 문제는 장르별로 가장 많이 재생된 노래를 두 개씩 모아 베스트앨범을 출시하는 문제입니다.

여기서는 사용해야 하는 값이 총 3개입니다.

장르, 재생 횟수, 공유번호.

그래서 고민이 많았어요.

어떻게 해시를 활용해야 할까.

 

일단 장르와 재생 횟수를 각각 key, value로 잡은 HashMap을 통해 가장 많이 재생된 장르를 구했습니다.

그리고 위의 HashMap을 장르를 key, 재생 횟수-고유번호를 list로 묶어서 value로 잡은 HashMap에 sort 조건으로 활용했습니다.

fun solution(genres: Array<String>, plays: IntArray): IntArray {
    var answer = intArrayOf()
    val map = HashMap<String, Int>()
    val map2 = HashMap<String, MutableList<Pair<Int, Int>>>()

    for (i in 0 until genres.size) {
        map[genres[i]] = (map[genres[i]] ?: 0) + plays[i]
        map2[genres[i]] = map2[genres[i]] ?: mutableListOf()
        map2[genres[i]]!!.add(Pair(plays[i], i))
    }
    val sortedMap =  map.toList().sortedByDescending { (_, value) -> value }.toMap()

    for (genre in sortedMap.keys){
        val sortedList = map2[genre]!!.sortedWith(compareByDescending<Pair<Int, Int>> { it.first }.thenBy { it.second })

        for (i in 0 until minOf(2, sortedList.size)){
            answer += sortedList[i].second
        }
    }

    return answer
}

어려웠지만, 통과해 냈습니다.

커서가 자꾸 답을 알려줘서 겨우 풀었어요.

 

---

이렇게 해시에 대해 알아보았습니다.

코테 준비를 위해 부랴부랴 공부를 시작했는데, 머리는 아프지만 생각보다는 재미가 있는 것 같아 앞으로도 포기하지 않고 꾸준히 열심히 해볼게요.

하기 싫지만 열심히 해볼게요