✏️ 오늘 학습한 내용

1. Hash
2. Greedy

🔎 Hash

1) Hash Table이란

• 연관배열 구조를 이용하여 키(key)에 값(value)을 저장하는 자료구조
• key에 hash function을 적용해 그 결과(value)를 hash table에 저장
• 연관배열 구조(associative array) : 키 1개와 값 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값을 도출할 수 있다.
• 해시 함수(Hash Function) : key를 hash로 바꿔주는 역할을 한다. key를 일정한 값을 가지는 hash로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다.
• 해시(Hash) : hash function의 결과물이며, value와 매칭되어 저장된다.
• 해시 충돌(Hash Collision) : 서로 다른 key가 같은 hash가 되는 경우 충돌이 발생

2) Python dictionary

• key와 value로 이루어진 자료형
• 중괄호 {} 혹은 내장 함수 dict()를 사용해 선언
• value를 꺼내는 방법

	1. dict_name[key] # key에 해당하는 value 반환
    2. dict_name.get(key, t) # key가 없으면 t를 반환

• dictionary 순회 방법
  1. 직접 순회를 통해 key 접근

  for key in dict_name :
  	print(key)
  # key를 출력

  2. .items를 통해 key, value 접근

  for key, value in dict_name.items() :
  	print(key,value)
  # key와 value를 출력

  3. .values를 통해 value 접근

  for value in dict_name.values() :
  	print(value)
  # value를 출력

3) 문제 예시

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

4) 코드

def solution(participant, completion):
    answer = ''
    d = {}
    # dictionary에 key를 추가해주면서 1이란 value를 부여
    # 동명이인이 있으면 기존 value에 + 1
    # 즉, d에 key : value (이름 : 동명이인 수) 쌍을 추가
    for i in participant :
        d[i] = d.get(i,0)+1
    
    # 완주한 사람을 한명씩 value에서 감소시킴
    for i in completion :
        d[i] -= 1
    
    # 완주를 못한 마지막 사람은 value가 1
    for key,value in d.items() :
        if value > 0 :
            answer += key
    
    return answer

🔎 Greedy

1) 탐욕법(Greedy)란

알고리즘의 각 단계에서 그 순간에 최적이라 생각되는 것을 선택

2) 문제 예시

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

3) 코드

# 
def solution(n, lost, reserve):
    # 여분을 가져왔지만 도난당한 학생 (교집합)
    temp = set(lost) & set(reserve) 
    # 도난당한 학생
    l = set(lost) - temp 
    # 여분을 가지고 있는 학생
    r = set(reserve) - temp 
    
    # 앞 뒤를 확인하고 lost에 해당한다면 그 학생을 제거 
    for i in sorted(r): 
        if i-1 in l:
            l.remove(i-1)
            
        elif i+1 in l:
            l.remove(i+1)
            
    return n - len(l)