Algorithm: 해시 - 의상

해시 문제 목록 링크 / 문제 링크 / Github 링크

import Foundation

func solution(_ clothes:[[String]]) -> Int {
    return 0
}

처음 짠 코드

import Foundation

func solution(_ clothes: [[String]]) -> Int {
    var clothesCategorized: [String:[String]] = [:]
    
    for i in clothes.indices {
        var items = clothesCategorized[clothes[i][1], default: []]
        items.append(clothes[i][0])
        clothesCategorized[clothes[i][1]] = items
    }

    let combinationCount = clothesCategorized
        .map({ $0.value.count })
        .map({ $0 + 1 })
        .reduce(1, *)
    
    return combinationCount - 1
}

개선 가능한 점

1. map 사용 최소화: map은 새로운 배열을 생성하므로, 불필요한 메모리 사용과 연산을 줄이기 위해 다른 방법을 사용할 수 있음
2. 문자열 사용 최소화: 결과값을 반환하는 데 불필요한 문자열 배열이 있음
3. 더 직관적인 변수 이름: 변수 이름을 조금 더 명확하게 만들 수 있음

개선한 코드

import Foundation

func solution(_ clothes: [[String]]) -> Int {
    var clothesCountByCategory: [String: Int] = [:]
    
    for cloth in clothes {
        let category = cloth[1]
        clothesCountByCategory[category, default: 0] += 1
    }

    let totalCombinations = clothesCountByCategory.values.reduce(1) { $0 * ($1 + 1) }
    
    return totalCombinations - 1
}

개선한 점

• 메모리 사용 감소: map에 의해 생성되는 중간 배열과 불필요한 문자열 배열을 제거해 메모리 사용량이 줄어듬
• 가독성 향상: 변수 이름과 루프 구조를 간결하게 하여 코드의 목적이 더 명확히 드러남

What I've learned:

Hash

Hash는 데이터를 특정한 규칙에 따라 고정된 길이의 값(해시값)으로 변환하는 방법 또는 그 결과를 의미한다. 이를 수행하는 함수는 해시 함수(Hash Function)라고 한다.

---

주요 특징

1. 고정된 길이 출력
   입력 데이터의 크기와 관계없이 항상 고정된 길이의 해시값을 생성한다. 예를 들어, SHA-256 해시 함수는 256비트 길이의 해시값을 반환한다.

2. 단방향성
   해시 함수는 단방향 함수이다. 즉, 해시값으로부터 원래 데이터를 역으로 추정하는 것이 거의 불가능하다.

3. 고유성(충돌 회피)
   서로 다른 입력 데이터는 거의 항상 서로 다른 해시값을 생성한다. 같은 해시값이 발생하는 경우를 해시 충돌(Hash Collision)이라고 하며, 좋은 해시 함수는 이러한 충돌 가능성을 최소화한다.

4. 빠른 계산
   해시 함수는 입력 데이터에 대해 빠르게 해시값을 계산할 수 있어야 한다.

---

주요 사용 사례

1. 데이터 무결성 확인
   파일의 해시값을 비교하여 데이터가 변조되지 않았는지 확인할 수 있다.
   예: 다운로드한 파일의 무결성 검증

2. 비밀번호 저장
   비밀번호를 해시값으로 변환하여 데이터베이스에 저장함으로써 원본 비밀번호를 알 수 없도록 보호한다.

3. 데이터 검색
   해시 테이블(Hash Table)은 데이터를 빠르게 검색하기 위해 해시를 사용한다.

4. 디지털 서명 및 인증
   데이터를 암호화하고 인증하는 데 사용된다.

---

예시: SHA-256 해시 함수

import CryptoKit

let input = "Hello, world!"
let inputData = Data(input.utf8)
let hashed = SHA256.hash(data: inputData)

// 해시값 출력
let hashString = hashed.compactMap { String(format: "%02x", $0) }.joined()
print(hashString) // 315f7c46e2b9b1ef99ef7c2f74c35d7a4f1dbcc8a0a2b78da8c3ad9ab8c21445

---

추가 정보

해시 알고리즘은 보안성이나 속도에 따라 여러 종류가 있으며, 다음과 같은 알고리즘들이 자주 사용된다.

• MD5: 빠르지만 보안성은 낮아 현재는 잘 사용되지 않음.
• SHA-1: 보안성이 향상되었지만 충돌 문제가 발견되어 중요하지 않은 용도에만 사용.
• SHA-256/SHA-3: 높은 보안성과 신뢰성을 제공.
• Bcrypt, Argon2: 비밀번호 해싱에 적합한 알고리즘.

Key-Value 연산과 Hash의 연관성

Key-Value 연산은 Hash와 깊은 관련이 있으며, 특히 데이터를 빠르게 저장하고 검색하는 데 중요한 역할을 한다. 이 방식은 주로 해시 테이블(Hash Table)이라는 자료구조에서 사용된다.

---

1. Key-Value와 Hash의 관계

Key-Value 구조에서는 Key를 입력으로 받아 그에 대응하는 Value를 저장하거나 검색한다. 이때, Key를 빠르게 검색하기 위해 해시 함수를 사용한다.

작동 방식:

1. Key를 해시 함수에 입력하여 해시값(Hash Value)을 생성함.
2. 이 해시값을 기반으로 Value를 저장하거나 검색함.
3. 같은 Key에 대해 항상 동일한 해시값이 나오므로, 빠르고 효율적인 검색이 가능함.

---

2. Hash를 사용하는 이유

(1) 빠른 데이터 접근

• 해시 테이블은 평균적으로 O(1)의 시간 복잡도로 데이터를 검색하거나 삽입할 수 있다.
• 예:
  • 데이터베이스에서 특정 사용자의 정보를 검색할 때 Key(예: 사용자 ID)를 해시하여 빠르게 위치를 찾아 Value(예: 사용자 정보)를 반환.

(2) 충돌 관리

• 좋은 해시 함수는 충돌(서로 다른 Key가 같은 해시값을 갖는 경우)을 최소화한다.
• 충돌이 발생하더라도 체이닝(Linked List)이나 오픈 어드레싱(Open Addressing) 같은 방법으로 문제를 해결할 수 있다.

---

3. Key-Value 연산의 실제 사례

(1) 캐싱(Cache)

• Redis와 같은 인메모리 데이터베이스는 해시 기반의 Key-Value 구조를 사용하여 데이터를 매우 빠르게 읽고 쓴다.
• 자주 사용하는 데이터를 메모리에 캐싱하여 성능을 크게 향상시킨다.

(2) 사전(Dictionary)

• Python의 딕셔너리(dict), Swift의 Dictionary와 같은 자료구조는 해시 테이블을 기반으로 구현된다.

  var dictionary: [String: Int] = ["apple": 3, "banana": 5]
  print(dictionary["apple"]!) // 3
  // 여기서 Key인 `"apple"`은 해시 함수로 처리되어 Value인 `3`에 빠르게 접근한다.

(3) 데이터베이스 인덱스

• 데이터베이스에서 Key를 해시 값으로 인덱싱하면 대량의 데이터를 효율적으로 검색할 수 있다.

(4) 로깅 시스템

• 시스템 로그에서 중복된 메시지를 빠르게 찾고, 같은 메시지의 발생 빈도를 추적할 때 Key를 해시로 변환하여 관리합니다.

---

4. 장점 요약

• 속도: Key를 해시로 변환해 Value를 빠르게 조회.
• 효율성: 대량의 데이터에서도 일정한 시간 내 연산 가능.
• 확장성: 데이터 크기가 커져도 일정한 성능 유지 가능.

5. 한계

• 해시 충돌이 많으면 성능이 저하될 수 있음.
• 메모리를 효율적으로 사용하지 못할 수도 있음(해시 테이블의 크기가 고정된 경우).