TIL_day4

230413 목요일

 

학습 주제

해시(Hash) - 완주하지 못한 선수

참가자 중에는 동명이인이 있을 수 있다는 것이 이 문제의 포인트였다. 만약 이름 대신 번호가 주어졌다면 배열이라는 자료형을 사용했겠지만, 이름이 주어졌고 해시 테이블의 형태로 만들어진 딕셔너리 자료형을 사용하였다.

이 코드의 복잡도는 O(n)-(Linear Time)이다.

만약 이 문제를 정렬을 이용해서 풀었다면 O(nlogn)의 복잡도를 가지므로 좋은 선택이 아니다.

# 해시(Hash) - dictionary 이용
def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x, 0) + 1
    for x in completion:
        d[x] -= 1
    dnf = [k for k, v in d.items() if v > 0]
    return dnf[0]

 

탐욕법(Greedy Algorithm) - 체육복

Greedy Algorithm 이란 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택하는 알고리즘이다.(현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.) 이 탐욕법으로 최적 해를 찾을 수 있는 문제는 현재의 선택이 마지막 해답의 최적성을 해치지 않는 경우이다. 대부분의 문제에 대해서는 최적의 해를 찾을 수 없는 가능성이 크기 때문에 주의해서 사용해야 하는 알고리즘이다. 그렇기 때문에 탐욕법을 사용해 문제의 해법을 찾을 경우에는 그 해법의 정당성에 대해 반드시 확인해야 한다!

 

아래의 방법 1에서는 O(n)의 복잡도를 가진다. 방법 2는 정렬을 사용하기 때문에 O(nlogn)의 복잡도를 가진다.

# 방법 1 - 효율성 good
def solution(n, lost, reserve):
    u = [1] * (n + 2)   # 모든 원소가 1인 배열 선언
    for i in reserve:
        u[i] += 1
    for i in lost:
        u[i] -= 1
    # 경계 값을 체크하지 않기 위해 맨 앞과 맨 뒤에 원소 값이 1인 원소 추가
    for i in range(1, n+1):
        # 앞 사람에게 빌려줄 수 있는지
        if u[i-1] == 0 and u[i] == 2:
            u[i-1:i+1] = [1, 1]
        # 뒷 사람에게 빌려줄 수 있는지
        elif 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])


# 방법 2 - 효율성 soso
# 학생 수가 많고, 학생 수에 비해 reserve 수가 매우 적을 때 사용
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)

 

정렬(Sort) - 가장 큰 수

numbers의 원소는 1000 이하라는 것을 이용하여 정렬 조건을 세우는 것이 이 문제의 핵심이고 이 부분으로 인해 이 문제는 O(nlogn)의 복잡도를 가진다.

def solution(numbers):
    numbers = [str(x) for x in numbers]
    numbers.sort(key=lambda x : (x * 4)[:4], reverse = True)
    
    return '0' if numbers[0] == '0' else ''.join(numbers)

 

탐욕법(Greedy) - 큰 수 만들기

 

어려웠던 내용

여태까지 피하고 싶었던 알고리즘을 드디어 마주하니...................................................... 생각보다 더 하기 싫다 우하하!

하지만 해야지 어떡해!!!!!!🤐