[TIL - 4일 차] 데이터 엔지니어링 : 자료구조/알고리즘 풀기 (4)

해시(Hash) 대표 문제 풀이 : 완주하지 못한 선수

문제

문제

해시(Hash)

• 만약 이름 대신 번호가 주어졌다면? => 선형 배열
• 이름을 키(key)로 하여 해시 함수(Hash function)를 통해 해시 테이블(hash table)에 매핑

해시(hash)

풀이 (1)

사전(Dictionary)의 원소들을 해시를 이용해 O(1) 시간에 접근 가능
사전을 활용하여 "이름 : 이름 수"로 저장하여 마지막 남은 사람의 이름 반환

코드

• get(x, 0) : x라는 키가 존재하면 해당 값을, 존재하지 않으면 0을 반환
• 최종 시간 복잡도 : O(n)

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

풀이 (2)

정렬을 이용하여 일치하지 않는 원소가 있는지 확인

코드

• 정렬의 시간 복잡도가 O(n log n)이므로 최종 시간 복잡도는 O(n log n)
• 해시를 활용한 풀이가 더 적절함

for 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]

탐욕법(Greedy) 대표 문제 풀이 : 체육복

문제

문제

탐욕법(Greedy Algorithm)

• 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
• 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 탐욕법을 활용
• 빌려줄 학생들을 "정해진 순서"로 살피며, 순서에 따라 우선하여 빌려줄 방향을 선택

풀이 (1)

학생의 수는 최대 30명 이므로, 학생 수만큼 배열을 확보하고 체육복의 수 기록
번호 순서대로 탐색하면서 빌려줄 관계 선정

알고리즘의 복잡도

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

문제점

• 학생 수가 매우 많고, 여벌의 체육복을 가져온 학생이 적다면 많은 기억 공간 필요
• 실행 시간도 모든 학생을 살펴 보아야하기 때문에 오래 걸림

코드

def solution(n, lost, reserve):
    u = [1] * (n + 2)
    
    # O(n)
    for i in reserve:
        u[i] += 1
    
    # O(n)
    for i in lost:
        u[i] -= 1
    
    # O(n)
    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 + 1] == 0 and u[i] == 2:
            u[i:i + 2] = [1, 1]
    
    # O(n)
    return len[x for x in u[1:-1] if x > 0]

풀이 (2)

여벌의 체육복을 가져온 학생들의 번호를 정렬하고, 이것을 하나 하나 순서대로 살펴보면서 빌려줄 수 있는지 판단
여벌의 체육복을 가져온 학생들을 정렬하여 시간 복잡도는 O(k log k)
빌려줄 수 있는 학생을 찾는 작업은 해시를 적용하여 상수 시간에 처리

알고리즘의 복잡도

• 여벌의 체육복을 가져온 학생들의 번호 reserve를 정렬, O(k log k)
• 체육복을 빌려줄 수 있는 학생을 찾아 처리, O(k) * O(1)
• 최종 시간 복잡도 : O(k log k)

코드

def solution(n, lost, reserve):
    s = set(lost) & set(reserve) # 빌릴 필요 없는 학생
    l = set(lost) - s # 빌려야 하는 학생
    r = set(reserve) - s # 빌려줄 수 있는 학생
    
    # sorted(r) : O(k log k)
    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) 대표 문제 풀이: 가장 큰 수

문제

알고리즘 설계

• 대소 관계 비교를 위한 기준을 마련하고, 주어진 배열을 정렬
• 정렬된 배열을 이용하여 문자열 표현을 완성

풀이

빈 문자열로 수를 초기화하여 수의 목록을 정렬 및 꺼내어 현재 수에 이어 붙임
모든 수를 다 사용할 때까지 반복

코드

• 최종 시간 복잡도 : O(n log n)

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

탐욕법(Greedy) 대표 문제 풀이: 큰 수 만들기

문제

풀이

앞에서부터 하나씩 골라서 담되, 지금 담으려는 것보다 작은 것은 다시 뺌
k 개만큼 빼지 않았을 경우를 고려(98765)하여 자릿수 계산

알고리즘의 복잡도

• 각 자리의 수를 추가하거나 제거하는 경우 : O(n)
• 최종 시간 복잡도 : O(n)
• 앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않음

코드

def solution(number, k):
    collected = []
    
    for i, num in enumerate(number):
        while len(collected) > 0 and collected[-1] < num 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
    
    return ''.join(collected)

결론

느낀 점

• 해시, 탐욕법, 정렬의 개념과 필요한 자료구조와 알고리즘 형태를 알 수 있었음
• 문제 풀이 강의는 처음 접해봤는데, 시간/공간 복잡도 등을 자세하게 고려하는 요령을 조금이나마 알게 됨

어려웠던 내용

• 결국 코딩을 잘하기 위해서는 해당 문제를 보고 빠르게 수행할 수 있는 코드를 떠올리는 게 중요하다는 것을 느낌
• lambda, dictionary 메서드, enumerate 등 생소한 문법이 등장

참고링크

나무위키 : 해시

https://namu.wiki/w/%ED%95%B4%EC%8B%9C