카테고리 없음

[알고리즘] 검색 알고리즘과 프로그래머스 해시 문제 (선형검색, 이진검색, 해시법)

judy@ 2023. 6. 29. 23:55

검색 알고리즘

[do it 자료구조와 함께 배우는 알고리즘 입문 파이썬 편] 참고하여 학습.

1. 선형 검색

  • 선형 검색: 선형으로 늘어선 배열에서 원하는 키값을 가진 원소를 찾을 때까지, 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
  • 보초(sentinel)법: 선형 검색 시 일반적으로는 배열의 끝에 도달하였는지와 원하는 키값을 만족하는지 두 가지 검사를 매 반복마다 실행하는데, 이를 줄이기 위한 방법. 배열을 복사하여 맨 끝에 목적하는 값을 추가하여 매 반복마다 원하는 키값을 만족하는지만 검사하게 함. 연산량을 반으로 줄일 수 있음

2. 이진 검색

  • 이진 검색: 순차적으로 정렬이 된 배열에서, 대상을 효율적으로 줄여나가며 검색하는 알고리즘.
  • 방법: 배열의 중앙과 키값을 비교하고, 키가 중앙 값보다 작으면 배열의 앞부분에 대해서, 크면 뒷 부분에 대해서 중앙값과의 비교를 수행하며 검색

3. 해시법

  • 해시법: 해시 함수를 통해 각 원소에 해당하는 해시값을 인덱스로 하는 해시테이블을 만든 뒤, 검색, 추가, 삭제를 해시테이블의 탐색을 통해 수행하는 방법
  • 선형, 이진 검색에 비해서 구현 자체는 복잡하나, task를 수행하는 데에 걸리는 시간은 훨씬 적게 듦. O(1)
  • 해시 함수로는 각각의 원소를 주로 전체 원소의 개수로 나눈 나머지를 사용함.
    • 키값이 int인 경우, 위처럼 수행하면 되지만 그 외 값들의 경우 hashlib 의 sha256을 사용하여 키 → 바이트배열 → 16진수 → 10진수로 변환하여 사용해야 함
  • 해시의 충돌(collision)이 발생하는 경우, 아래 두 가지 방법을 통해 피할 수 있음
    • 체인법(chaining): 해시값이 겹치는 경우, 연결 리스트를 사용하여 원소를 배치함. 해시 테이블의 각 버킷은 key, value, next의 속성을 가짐
    • 오픈주소법(open addressing): 해시값이 겹치는 경우, 기존 키 값에 1을 더하여 재해싱하는 방식으로 원소를 배치, 검색, 삭제함. 이 때, 버킷의 상태를 표시하는 status 속성을 추가하여, 비어있는지, 채워져있는지, 삭제되었는지를 나타냄

 

프로그래머스 해시 문제

 

고득점 kit 부분에 접근하면 해시 문제만 5개가 모아져있다. 근데, 내가 문제를 처음 접했을 때는 다 해시말고 다른 걸로 풀었었다. 억지억지로 해시로 푸는 방법을 찾다가 kiddo님의 블로그에 굉장히 잘 정리되어 있어 참고하며 문제를 다시 해석하고 풀어보았다.

 

완주하지 못한 선수 문제 (https://kid-do-developer.tistory.com/92)

위 블로그에서 제안하는 스크립트이며, 해시로 문제를 접근하는 방법에 대해 이해하기 매우 좋았다.

 

해시테이블을 만들고, 모든 해시를 더해서 기존 데이터의 총합을 만들어두고, 거기서 완주한 데이터에 대한 해시를 뺌. 나머지에 대한 값을 반환하면 완주하지 못한 사람이 누군지 알 수 있음.

 

def solution(participant, completion):
    hashDict={}
    sumHash=0
    
    for part in participant:
        hashDict[hash(part)]=part
        sumHash+=hash(part)
    
    for comp in completion:
        sumHash-=hash(comp)
        
    return hashDict[sumHash]

 

 

베스트앨범 문제

위 블로그에서 제안하는 방법을 이해하기 전에 내 힘으로 먼저 풀고 싶었고, 결론적으로 기존 대비 매우 효율적인 코드를 얻을 수 있었다.

def solution(genres, plays):
    indexes = [-i for i in range(len(genres))]
    
    hashtable = {g:[] for g in set(genres)}
    gdict = {g:0 for g in set(genres)}
    
    sorted_zip = sorted(zip(plays, indexes, genres), reverse=True,
                       key=lambda x: (x[0], x[1]))

    for p, i, g in sorted_zip:
        hashtable[g].append(-i)
        gdict[g] += p

    answer = []
    for g,_ in sorted(gdict.items(), key=lambda x:x[1], reverse=True):
        answer.extend(hashtable[g][:2])

    return answer
테스트 1 〉	통과 (0.02ms, 10MB)
테스트 2 〉	통과 (0.02ms, 10MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10MB)
테스트 5 〉	통과 (0.07ms, 10.1MB)
테스트 6 〉	통과 (0.09ms, 10.2MB)
테스트 7 〉	통과 (0.04ms, 10.4MB)
테스트 8 〉	통과 (0.03ms, 9.98MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.09ms, 10.1MB)
테스트 11 〉	통과 (0.02ms, 10.2MB)
테스트 12 〉	통과 (0.04ms, 10.1MB)
테스트 13 〉	통과 (0.08ms, 9.92MB)
테스트 14 〉	통과 (0.08ms, 9.99MB)
테스트 15 〉	통과 (0.02ms, 10.1MB)

 

기존에 판다스로 풀었던 결과

import pandas as pd

def solution(genres, plays):
    answer = []
    
    # table
    df = pd.DataFrame({'genres': genres, 'plays':plays})
    
    genres = df.groupby(by='genres').sum().sort_values(
        by='plays', ascending=False).index
    
    for g in genres:
        tmp = list(df[df['genres'] == g].sort_values(
            by='plays',ascending=False).index[:2])
        answer += tmp
    
    return answer
테스트 1 〉	통과 (18.44ms, 57.4MB)
테스트 2 〉	통과 (13.72ms, 57.5MB)
테스트 3 〉	통과 (13.14ms, 57.6MB)
테스트 4 〉	통과 (15.15ms, 57.9MB)
테스트 5 〉	통과 (19.61ms, 57.3MB)
테스트 6 〉	통과 (16.04ms, 57.6MB)
테스트 7 〉	통과 (13.94ms, 57.6MB)
테스트 8 〉	통과 (16.07ms, 57.8MB)
테스트 9 〉	통과 (13.02ms, 57.7MB)
테스트 10 〉	통과 (24.06ms, 58MB)
테스트 11 〉	통과 (18.24ms, 58MB)
테스트 12 〉	통과 (16.51ms, 58.1MB)
테스트 13 〉	통과 (21.80ms, 57.7MB)
테스트 14 〉	통과 (16.97ms, 57.3MB)
테스트 15 〉	통과 (19.51ms, 58.1MB)

이제와 새삼스럽지만, 여기에 효율성 테스트가 있었으면 나는 영원히 통과하지 못했을거야...

 

마무리

- 솔직히 말해서, 아직도 해시 알고리즘은 애매하게 이해됐다. hash() 메서드를 통해 해시 값을 만들어 키로 활용할 수 있고, 중첩되는 알고리즘을 처리하는 방법도 이해는 되었지만, 문제에 맞닥뜨렸을 때에는 구조가 복잡하고 코딩량이 많아 해시법 자체를 사용하는 건 뭔가 좀 무리인듯?

- 그래도 key, value를 사용해서 문제에 좀 더 효과적으로 접근할 수 있다는 방법을 알았으니, 그걸로 된 듯!

 

반응형