[데브코스 TIL] DAY5 자료구조/알고리즘 풀기(4)

오늘의 학습 주제

---

1. 해시(Hash)
2. 탐욕법(Greedy)
3. 정렬(Sort)
4. 탐욕법(Greedy)

 

1.해시(Hash)

---

해시 테이블은 키(key)와 값(value)으로 구성된 자료 구조
키를 해시함수에 넣을 때 나오는 고유한 값을 인덱스로 사용하여 테이블에 값을 저장하거나 검색한다

• 장점
  • 자료의 검색, 읽기, 저장 속도가 빠르다
  • 자료가 중복되는지 확인하기 쉽다 (집합이 중복을 허용하지 않는다)
• 단점
  • 보통 저장 공간이 더 필요하다
  • 충돌을 해결할 방법이 필요하다

• 충돌(collision)
  • key가 달라도 해시 값이 같을 때가 있는데, 이것을 충돌이라 한다.
  • 해결하는 방법은 두 가지이며, 파이썬을 개방 주소법을 사용한다.
    • 분리 연결법(Separate Chaining) : 충돌한 키의 자료를 연결 리스트로 저장
    • 개방 주소법(Open Addressing) : 충돌할 때 다음 빈자리를 찾아 자료를 저장

• 파이썬 딕셔너리
  • 파이썬은 사전을 구현할 때, 내부적으로 해시 테이블을 사용한다
  • 사전의 원소들은 해시를 이용해 O(1) 시간에 접근 가능

# 해시 : O(N)
def solution(participant, completion):
	d ={}
    for x in participant:
    	d[x] = d.get(x, 0) + 1
    for x in completion:
    	d[x] -= 1
    non_completion = [k for k, v in d.items() if k > 0]
    answer = non_completion[0]
    return answer
    
# 정렬 : O(NlogN) 테스트는 통과하지만...
def solution(participant, completion):
	participant.sort()
    completion.sort()
    for i in range(len(completion)):
    	if participant[i] != completion[i]:
        	return participant[i]
    return participant[len(participant)-1]

2.탐욕법(Greedy)

---

선택의 순간마다 당장 좋은 것만 고르는 방법
순간의 가장 좋아 보이는 것만 선택하기 때문에 나중에 미칠 영향을 고려하지 않는다.

• 조건
  • 탐욕적 선택 속성(Greedy Choice Property)
    앞의 선택이 이후의 선택에 영향을 주지 않는다. 지역적 선택이 전체 문제의 최적해를 도출할 수 있어야 한다.
  • 최적 부분 구조(Optimal Substructure)
    문제의 최종 해결 방법은 부분 문제의 최적 문제 해결 방법으로 구성한다. 문제를 해결하는 모든 단계에 대해서 해당 단계의 최적해가 도출되어야 한다.

# 알고리즘의 복잡도 : O(n)
여벌을 가져온 학생 처리 : reserve의 길이에 비례
체육복을 잃어버린 학생 처리 : lost의 길이에 비례
체육복 빌려주기 처리 : 전체 학생 수 n에 비례

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

# 만약 전체 학생 수에 비해 여벌의 체육복을 가져온 학생은 매우 적다면?
여벌의 체육복을 가져온 학생들의 번호를 정렬하고 : O(klogk)
이것을 하나하나 순서대로 살펴보면서
빌려줄 수 있는 다른 학생을 찾아서 처리한다 : 해시 적용해서 상수 시간 처리 O(k) X O(1)

def solutioin(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)

3.정렬(Sort)

---

특정한 기준에 따라 데이터를 늘어놓는 알고리즘

def soluftion(numbers):
  numbers = [str(x) for x in numbers] #O(N)
  numbers.sort(key=lambda x : (x*4)[:4], reverse=True) #O(NlogN)
  if numbers[0] == '0': #O(N)
      answer = '0'
  else:
      answer = ''.join(numbers)
  return answer

4.탐욕법(Greedy) 문제 풀이

---

def solution(number, k):
	collected = []
    for i, num in enumerate(number): 
    	while len(collected) > 0 and collected[i] < n and k>0:
        	collected.pop()
            k -= 1
        if k == 0:
        	collected =+ list(number[i:])
            break
        collected.append(num)
     
    collected = collected[:-k] if k>0 else collected
    answer = ''.join(collected)
    return answer #O(N)