[자료구조] 해시 & 그리디

 

 

≣ 목차

 

 

---

 해시(Hash)  

해시 개념

해시란 해시 테이블에 Key와 Value를 매핑해서 데이터를 저장하는 자료구조이다. 주로 데이터 탐색, 삽입, 집계등의 연산을 할때 유용하며, 인덱스 값이 숫자가 아닌 문자열이나 튜플을 때도 유용하다. 하지만 최댓값과 최솟값을 찾는 문제는 자료구조 전체를 탐색해야 하기 때문에 효율성이 떨어진다는 단점이 있다.

• 해시 (Hash) : 임의 값을 고정 길이로 변환하는 것
• 해시 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수 (Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해시 값 (Hash Value) 또는 해시 주소 (Hash Address) : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬록 (SLot) : 한 개의 데이터를 저장할 수 있는 공간

해시 예제

해시를 사용한 간단한 문제를 풀어보자.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

• 풀이 과정

해시의 구조와 동일한 파이썬의 딕셔너리 자료형을 통해 구현하며 이름이 key, 빈도수가 value이다.

1. 참가자의 이름과 해당 이름이 몇번 나왔는지를 세서 딕션리에 삽입한다.
2. 참가자의 이름과 완주자의 이름을 비교하며 해당 이름의 value를 -1

• 풀이 코드

def solution(participant, completion):
    d = {}
    for x in  participant:
        d[x] = d.get(x,0)+1
        
    for x in completion:
        d[x] -= 1
        
    fail = [k for k,v in d.items() if v>0]
    
    return fail[0]

 

---

 그리디(Greedy) 

그리디 개념

그리디 알고리즘이란 현재 상황에서 가장 최선의 상황을 선택하는 알고리즘이다. 여기서 주의해야 할 점은 그리디 알고리즘으로 도출한 결과가 항상 최적해가 아니라는 점이다. 그리디 알고리즘은 그 이름답게 현재 상황만을 고려하여 가장 최선의 것을 찾아나가는 알고리즘이다. 그렇기 때문에 어떠한 문제를 그리디로 해결하고자 한다면, 그리디를 통한 최종 결과가 최적해와 동일하다는 조건이 충족이 되는것을 확인하고 결정해야한다.

 

그리디 예제

그리디를 사용한 대표적인 문제를 풀어보자

 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

• 풀이 과정

빌려줄 학생들을 정해진 순서로 살펴야하고, 그 순서에 따라 우선하여 빌려줄 방향을 정해야 함

방법(1)
1. 학생 수+2 만큼 배열을 선언 (1로 초기화)
    => 처음 학생과 마지막 학생의 경우를 좀 더 쉽게 하기 위해서
2. 각자 가지고 있는 체육복의 수를 기록
     => 여분이 있는 학생은 +1, 도난 당한 학생은 -1
3. 번호 순서대로 스캔하면서 빌려줄 관계를 설정

방법(2) => 학생의 수가 많을때 유리
1. 여벌의 체육복을 가져온 학생들의 번호를 정렬
2. 해당 학생들 주변을 탐색하며 빌려야 하는 학생을 탐색 후 처리
만일 여벌을 챙긴 학생보다 분실한 학생이 더 적을 때는 분실한 학생을 정렬 후 주변에 빌릴 수 있는 학생을 탐색

• 풀이 코드

def solution(n, lost, reserve):
    uni = [1] * (n+2)
    for i in reserve:
        uni[i] += 1
    for i in lost:
        uni[i] -= 1
    for i in range(1,n+1):
        if uni[i] == 2 and uni[i-1] == 0:
            uni[i-1 : i+1] = [1,1]
        elif uni[i] == 2 and u[i+1] == 0:
            uni[i:i+2] = [1,1]
    cnt = [x for x in uni[1:-1] if uni[x]>0]
    return len(cnt)


def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s

    for x in sorted(r):
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)
    return n - len(l)