1주차 목요일, 4일차 Today I Learned
자료구조와 알고리즘 (4)
: 해시 (Hash), 그리디 (Greedy)/탐욕법, 정렬 문제
✏️ 학습 내용
1. 해시 (Hash)
해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다. 이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.
Dictionary의 경우 내부적으로 해시를 이용해 구현하기 때문에, 원소들을 해시를 이용해 O(1) 시간에 접근 가능하다.
- key, hash function, hash table (index, buckets)
(예제) 완주하지 못한 선수
Q. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주했다. 마라톤에 참여한 선수들의 이름이 담긴 배열과 완주한 선수들의 이름이 담긴 배열이 주어질 때, 완주하지 못한 선수를 출력하라.
제한사항 :
- 선수의 수는 1명 이상, 100,000명 이하이다.
- 참자가의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있다.
- 참가자 중에 동명이인이 있을 수 있다.
1. 참가자들 중 어떤 이름이 몇 명인지 카운트 한다.
2. 완주자 목록에 있는 이름은 1씩 감소시킨다.
# 해시를 이용한 풀이
def solution(participant, completion) :
d = {}
for x in participant :
d[x] = d.get(x, 0) + 1
for x in completaion :
d[x] -= 1
dnf = [k for k, v in d.items() if v > 0]
answer = dnf[0]
return answerdnf는 리스트 형태이므로, 따로 answer에 dnf[0] 값을 넣어서 리턴해주었다.
# 정렬을 이용한 풀이 : 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. 그리디 (탐욕법)
그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념으로, 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 한다. 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택한다.
탐욕법으로 최적해를 찾을 수 있는 문제도 존재한다. 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때가 그러하다.
(예제) 체육복
1. 학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다.
2. 빌려줄 학생들을 정해진 순서로 스캔하면서 빌려줄 방향을 정한다.
이는 학생의 수 최대가 30명이기 때문에 괜찮은 방법이다.
Q. 체육복을 도난당한 학생, 여분을 가져온 학생들이 있을 때 체육복 있게 수업을 들을 수 있는 학생 수를 구하라.
제한사항 :
- 전체 학생 수는 30명이다.
- 양 옆의 학생에게만 빌려줄 수 있다.
def solution(n, lost, reserve) :
u = [1] * (n + 2) # 전체 학생 + 2만큼의 배열을 생성
# 학생들이 가져온 수, 잃어버린 수
for i in reserve :
u[i] += 1
for i in lose :
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]
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])
# 여벌을 가져온 학생 처리 : reserve 길이에 비례 O(n)
# 체육복을 잃어버린 학생 처리 : lost 길이에 비례 O(n)
# 체육복 빌려주기 처리 : 전체 학생 수 n에 비례 O(n)
나는 아래와 같이 풀었다.
def solution(n, lost, reserve):
x = [1] * (n+2)
for l in lost :
x[l] -= 1
for r in reserve :
x[r] += 1
for r in reserve :
if x[r-1] == 0 and x[r] > 1 :
x[r-1] += 1
elif x[r+1] == 0 and x[r] > 1 :
x[r+1] += 1
return len([k for k in x[1:-1] if k>0])
만약 전체 학생 수가 매우 크다면 문제의 성질상 O(n)보다 낮은 복잡도 알고리즘은 어렵다. 그런데 여벌의 체육복을 가져온 학생이 매우 적다면 1) 여벌의 체육복을 가져온 학생들의 번호를 정렬하고, 2) 이것을 하나씩 순서대로 살펴보면서, 3) 빌려줄 수 있는 다른 학생을 찾아서 처리해야 한다. 이 때에는 1)의 정렬 처리가 O(klogk)가 되고, 3)의 처리는 해시를 적용해서 상수 시간에 처리할 수 있어 O(k)*O(1)이 된다. 따라서 O(klogk)가 된다.
def solution(n, lost, reserve):
s = set(lost) & set(reserve) # 도난 o, 빌려야 하는 학생
l = set(lost) - s # 체육복을 빌릴 필요 없는 학생
r = set(reserve) - s # 여분 o, 빌려줄 수 있는 학생
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)
(예제) 큰 수 만들기
Q. 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자 구하기
제한조건 :
- number는 1자리 이상, 1,000,000자리 이하인 숫자
- k는 1 이상 Number의 자릿수 미만인 자연수
1. 앞 자리부터 하나씩 골라서 담되, 큰 수가 나오면 앞에 나온 작은 수는 뺀다. (큰 수부터 작은 수로 이어지도록)
2. 제약 조건에 도달하면 나머지 수를 그대로 붙인다.
3. 빼야 할 횟수가 남아있으면 맨 뒤의 수를 뺀다.
=> 복잡도 O(n) 여기서 n은 자릿수
앞 단계에서의 선택 "앞 자리에 큰 수를 두는 것"이 이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않기 때문에 탐욕법이 적용 가능하다.
# 복잡도 O(n) (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
answer = ''.join(collected)
return answer
# 나의 풀이
def solution(number, k):
num = []
for i, n in enumerate(number) :
while len(num) > 0 and num[-1] < n and k > 0 :
num.pop()
k -= 1
num.append(n)
if k == 0 :
return ''.join(num) + number[i+1:]
if k > 0 :
return ''.join(num)[:-k]강의를 들었을 때는 collected=[] 으로 왜 비어있는 리스트로 시작하고, len(collected)>0 이 조건이 왜 필요한지 이해하지 못 했었는데 직접 코드를 풀어보니까 납득이 되었다. num에 넣을 원소는 모두 반복문 내에서 결정할 예정이니까 num=[] 처럼 비어있는 리스트로 시작하고, 맨 처음에는 비어있기 때문에 while문에서 인덱스에러가 나지 않도록 길이가 0 이상일 때, 즉 무언가라도 담겨있을 때의 조건을 추가해주었다.
while문의 내용은 만약 큰 수를 만나면 앞에 있던 작은 수를 삭제하는 내용이다. 그리고 해당 수는 자연스럽게 append를 하면 된다. 추가적으로 if문을 통해서 종료 조건을 지정하고, 뒤에 있는 숫자를 삭제하면 되는 경우의 처리도 해주었다.
3. 정렬 - 가장 큰 수 연습
Q. 0또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 찾아내라.
제한사항 :
- 길이는 1~100,000이며, 원소는 0~1,000이다.
문제 해결 방법 1 :
1) 빈 문자열로 수를 초기화한다
2) 가장 크게 만들 수 있는 수를 고른다.
3) 그 수를 현재 수에 이어 붙인다.
4) 모든 수를 다 사용할 때까지 반복한다.
=> 복잡도 O(n^2)
(더 나은) 문제 해결 방법 2 :
1) 빈 문자열로 수를 초기화한다.
2) 크게 만드는 것을 우선으로 수의 목록을 정렬한다.
- 대소 관계 비교를 위한 기준 마련하고, 이를 이용해 주어진 배열을 정렬
3) 목록에서 하나씩 꺼내어 현재 수에 이어 붙인다.
4) 모든 수를 다 사용할 때까지 반복한다
.=> 복잡도 O(nlogn)
def solution(numbers):
numbers = [str(x) for x in numbers]
numbers.sort(key=lambda x: (x*4)[:4], reverse=True)
if numbers[0] == '0' :
answer = 0
else :
answer = ''.join(numbers)
return answer# 나의 풀이
def solution(numbers):
n = [str(n) for n in numbers]
n.sort(key=lambda x: (str(x)*4)[:4], reverse=True)
return "".join(n) if n[0] != "0" else "0"
🔖 잘한 것과 잘못한 것
오늘 하루 내에 주어진 강의를 활용하여 실습 문제를 풀면서 내 것으로 만들기를 완료했다. 강의만 듣는 것과 직접 다시 풀어보는 것은 또 다르다!
📝 남아있는 의문과 개선점
해시에 대한 내용이 더 있으니 좀 더 개인적으로 공부하면서 이해력을 높여야겠다. 그리디는 아직 좀 헷갈린다. 실습 문제는 이해를 하겠는데 이것이 왜 그리디한가?를 이해하지 못한 것 같다. 해시와 그리디 모두 좀 더 풀다보면 체화될 것이다. 추가적인 학습이 필요하다.
그리고 lambda 함수에 컴프리헨션 구문을 이용하는 것은 아직 어렵다. 시도해보려고 했는데 잘 못 해서, 좀 더 학습한 후에 다시 도전해봐야 할 것 같다.
☁️ 소감
이번 주는 특히 바쁘다. 강의에서 다루는 주제의 분량이 많은데 처음 공부하는 분야이기도 하고, 이전에 등록해 놓은 자격증도 주말에 시험이라 공부해야 하기 때문이다. 강의를 듣고 복습을 충분히 하다가 심화 학습을 하면 좋겠는데, 지금은 강의를 듣고 (실습은 풀지도 못하고) 복습도 조금밖에 못 하고 (이전 강의들 복습할 것이 밀려있다) 자격증 공부를 시간을 쪼개서 해야 한다.
그래도 오늘은 크게 어렵진 않았다. 하지만 이 개념들을 체화하는 것이 중요할 것 같다. 근본이 되는 내용들이니까 충분히 학습하고싶다. 이래서 다들 자료구조와 알고리즘이 중요하다고 했구나!
'Data Engineering > grepp 데브코스 : TIL' 카테고리의 다른 글
| [TIL_2023.10.23] 웹 데이터 크롤 및 분석 (1) : 기본 HTML/CSS/JS (1) | 2023.10.23 |
|---|---|
| [TIL_2023.10.20] 자료구조와 알고리즘 (5) : 힙, DFS/BFS, 동적 계획법 대표 문제 풀이 (1) | 2023.10.20 |
| [TIL_2023.10.18] 자료구조와 알고리즘 (3) : 큐 Queues, 트리 Trees, 힙 Heaps (1) | 2023.10.18 |
| [TIL_2023.10.17] 자료구조와 알고리즘 (2) : 연결 리스트, 스택, 후위 표현/표기 (1) | 2023.10.17 |
| [TIL_2023.10.16] 자료구조와 알고리즘 (1) : 선형배열, 정렬/탐색, 재귀 알고리즘, 복잡도 (1) | 2023.10.16 |
