[코딩테스트 합격자 되기 08] 해시 Q&A

면접 질문

1. 해시 테이블에서 사용하는 해시의 개념은 무엇이며, 이러한 자료 구조가 배열, 리스트와 같은 다른 자료 구조와 비교하여 어떤 장점을 가지나요? 해시 테이블이 실생활에서 어떻게 사용될 수 있는지 예를 들어 설명하세요.

• 해시는 해시 함수를 사용하여 변환한 값을 인덱스로 삼아 키와 값을 저장하여 빠른 데이터 탐색을 제공하는 자료구조 입니다. 배열, 리스트 등은 인덱스를 활용하여 탐색을 빠르게 만들지만, 해시는 키를 활용해 데이터 탐색을 빠르게 합니다.
• 해시는 키와 데이터를 일대일 대응하여 저장하므로, 키를 통해 바로 데이터에 접근할 수 있습니다. 인덱스(숫자)로만 접근하는 배열보다 사람에게 접근성이 좀 더 좋은 자료구조입니다.
• 실생활에서의 예시로는 연락처가 있습니다. 최종으로 얻고자 하는 것은 번호 값(전화번호)이고, 이를 검색하기 위해 활용하는 정보는 키(이름) 입니다.

2. 해시 함수에서 "완벽한 해시 함수"란 무엇을 의미하나요? 현실적인 상황에서 완벽한 해시 함수를 구현하는 것이 어려운 이유는 무엇인가요? 해시 함수의 설계 시 고려해야 할 주요 요소를 설명하세요.

• 완벽한 해시 함수 : 충돌 없이 실제 키 값 집합을 테이블에 매핑하는 함수
• 해시 함수는 해시 충돌이 반환할 가능성을 항상 가지고 있다. 고유한 해시 값을 제공하는 것이 불가능할 수 있기 때문에 이론적으로나 현실적으로나 불가능하다.

3. 해시 충돌이 발생하는 근본적인 이유는 무엇인가요? 충돌이 발생할 가능성을 수학적으로 설명하고, 해시 테이블이 충돌을 허용할 수밖에 없는 구조적인 이유를 설명하세요.

• 해시 함수의 출력값 공간은 유한하지만, 입력값의 공간은 무한하거나 매우 큰 경우가 많기 때문이다.
• 충돌 발생 가능성은 생일 문제(Birthday Paradox) 와 유사하게 설명된다. 생일 문제는 23명만 있어도 2명 이상이 같은 생일을 가질 확률이 50% 이상이 되는 현상이다.

4. 해시 충돌을 해결하는 방법 중 "체이닝"과 "개방 주소법"을 비교하여 설명하세요. 이 두 방법이 사용하는 메모리와 시간 복잡도 관점에서의 차이를 기술하고, 각각의 방법이 실제 응용에서 적합한 시나리오는 무엇인가요?

• 체이닝 : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장하도록 해시 테이블의 구조를 변경 (링크드리스트 활용)
• 개방 주소법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다.

5. 체이닝 기법의 성능을 분석하세요. 체이닝 방식에서 성능 저하를 유발할 수 있는 문제는 무엇이 있으며, 이를 해결하기 위한 최적화 방법이나 대안은 어떤 것들이 있을까요?

• 체이닝 방식은 링크드리스트를 사용하므로 탐색 시간이 오래 걸린다는 단점이 있다. 최악의 경우 시간 복잡도는 O(n) 이 된다.
• 대안 :연결 리스트 대신 이진 탐색 트리 사용
  • 해시 충돌이 발생했을 때 각 버킷에서 데이터를 저장하는 자료구조로 연결 리스트 대신 균형 이진 탐색 트리를 사용하면 최악의 경우 시간복잡도를 O(log n)으로 줄일 수 있다.
  • 이는 자바의 hashmap에서 사용하는 방식이다.

 

6. 개방 주소법에서 사용되는 다양한 탐색 전략(예: 선형 탐사, 이차 탐사, 이중 해싱) 간의 차이를 설명하고, 각 전략의 장단점을 분석하세요. 어떤 상황에서 특정 전략을 사용하는 것이 더 적합한지 논의하세요

• 선형 탐사 방식 : 보통 한 칸 씩 값을 이동하며 빈 버킷을 찾아 충돌값을 삽입한다. 하지만 한 칸씩 값을 이동하므로 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생긴다.
• 이차 탐사 방식 : 충돌이 발생하면 제곱의 간격으로 탐색하는 방식. 예를 들어, 첫 번째 탐사는 1칸, 두 번째 탐사는 4칸, 세 번째 탐사는 9칸을 건너뛴다.
• 이중 해시 방식 : 두 번째 해시 함수를 사용해 탐사 간격을 동적으로 결정한다. 즉 충돌이 발생할 때마다 다른 해시 값을 기반으로 탐색한다.

7. 해시 테이블의 평균적인 시간 복잡도가 O(1)로 유지되기 위한 조건을 설명하고, 이 조건이 무너질 때 발생할 수 있는 최악의 시간 복잡도 O(n)이 발생하는 구체적인 시나리오를 제시하세요. 또한 이러한 상황을 방지하기 위해 사용할 수 있는 기법들은 무엇인가요?

• 키가 고르게 해시 테이블에 분포하도록 설계한다.
• 모든 키가 동일한 해시 값을 갖는 경우 해시테이블의 모든 항목이 하나의 슬롯에 저장된다.
  • 체이닝 방식에서는 링크드리스트를 이용하기 때문에, 하나의 리스트에 모든 요소가 저장된다. 삽입, 삭제 검색의 시간 복잡도는 o(n)이 된다.
  • 개방 주소법의 경우에도 빈 슬롯을 찾기 위해 테이블 전체를 순회해야 하기 때문에 O(n) 의 복잡도를 가질 수 있다.

실전 문제

문제 1

학생들의 점수를 저장하는 딕셔너리가 있습니다. 이 딕셔너리에서 특정 학생의 이름을 입력받아 그 학생의 점수를 출력하는 함수를 작성하세요.

입출력 예:

• 입력: "홍길동"
• 출력: 85

입출력 예에 대한 설명: 입력으로 주어진 학생의 이름 "홍길동"에 해당하는 점수가 딕셔너리에서 85로 저장되어 있으므로 85를 출력합니다.

제약사항:

• 학생의 이름은 딕셔너리에 항상 존재한다고 가정합니다.
• 딕셔너리는 { "홍길동": 85, "이순신": 90, "장영실": 78 }와 같은 구조입니다.

solution

dic = { "홍길동": 85, "이순신": 90, "장영실": 78 }
def sol(str):
    return (dic[str])

sol("홍길동")

문제 2

주어진 딕셔너리에서 값이 특정 값보다 큰 키만을 추출하여 새로운 딕셔너리를 반환하는 함수를 작성하세요.

입출력 예:

• 입력: { "a": 10, "b": 20, "c": 5 }, 기준 값: 10
• 출력: { "b": 20 }

입출력 예에 대한 설명: 딕셔너리에서 값이 10보다 큰 키는 "b"뿐이므로, 새로운 딕셔너리는 { "b": 20 }입니다.

solution

dic = { "a": 10, "b": 20, "c": 5 }
num = 10

def sol(dic, num):
    answer = {}
    for key,val in dic.items():
        if(val) > num:
            answer[key] = val
    return (answer)

sol(dic, num)

제약사항:

• 입력 딕셔너리의 값은 모두 정수입니다.
• 기준 값은 양수입니다.

문제 3

두 개의 딕셔너리를 입력받아, 두 딕셔너리의 키와 값을 모두 합친 새로운 딕셔너리를 반환하는 함수를 작성하세요. 만약 같은 키가 존재할 경우, 값은 더한 값을 저장하세요.

입출력 예:

• 입력: { "a": 1, "b": 2 }, { "b": 3, "c": 4 }
• 출력: { "a": 1, "b": 5, "c": 4 }

입출력 예에 대한 설명: 두 딕셔너리에서 중복된 키 "b"의 값은 2와 3이므로 더한 값 5가 저장됩니다.

제약사항:

• 딕셔너리의 값은 모두 정수입니다.
• 중복된 키에 대한 처리만 고려하면 됩니다.

solution

dic1 = { "a": 1, "b": 2 }
dic2 = { "b": 3, "c": 4 }

def sol(dic1, dic2):
    answer = dic1.copy()
    for key, val in dic2.items() :
        if key in answer :
            answer[key] += val
        else : answer [key] = val

    return print(answer)

문제 4

문자열로 이루어진 리스트를 입력받아, 각 문자열의 길이를 값으로 가지는 딕셔너리를 반환하는 함수를 작성하세요.

입출력 예:

• 입력: ["apple", "banana", "pear"]
• 출력: { "apple": 5, "banana": 6, "pear": 4 }

입출력 예에 대한 설명: 입력 리스트의 각 문자열의 길이를 딕셔너리의 값으로 변환한 결과입니다.

제약사항:

• 리스트 내 문자열의 길이는 1 이상입니다.
• 문자열은 중복되지 않습니다.

l = ["apple", "banana", "pear"]

def sol(l):
    answer = {}
    for f in l : 
        answer[f] = len(f)
    return print(answer)

sol(l)

문제 5

학생들의 점수 딕셔너리에서 모든 학생의 평균 점수를 반환하는 함수를 작성하세요.

입출력 예:

• 입력: { "홍길동": 85, "이순신": 90, "장영실": 78 }
• 출력: 84.33

입출력 예에 대한 설명: 모든 학생의 점수의 합이 253이며, 학생 수 3으로 나누었을 때 84.33이 됩니다. 소수점 둘째 자리까지 출력합니다.

제약사항:

• 딕셔너리에는 최소 1명의 학생이 있습니다.
• 점수는 0 이상 100 이하의 정수입니다.

dic = { "홍길동": 85, "이순신": 90, "장영실": 78 }

def sol(dic):
    total = sum(dic.values())
    average = total/len(dic)
    print(round(average,2))

sol(dic)