[TIL] KDT_20230413

📚 KDT WEEK 2 DAY 4 TIL

코딩테스트 풀이와 알고리즘 학습

• 해시(Hash)
• 탐욕법(Greedy)
• 정렬(Sort)

 

---

 

해시(Hash) 알고리즘

• Set, Dictionary를 활용하여 탐색 시간 복잡도를 O(1)로 효율적 이용
• 선형 배열에서는 숫자로 탐색하는 경우에 O(1)로 효율적일 수 있음

예시 문제 : 완주하지 못한 선수

---

def solution(participant, completion):
    dic = {}
    
    for i in participant:
        dic[i] = dic.get(i,0) + 1
    for j in completion:
        dic[j] = dic.get(j,0) - 1
    
    result = [x for x,y in dic.items() if y > 0]
    return result[0]

간단한 알고리즘이었다.

Dictionary 구조에서 .get(x,y) 함수는 'x' 키 값이 존재하지 않으면 0 을 반환한다.

---

 

---

 

탐욕법(Greedy) 알고리즘

• 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택!
• 단, 현재의 선택이 마지막 해답의 최적성을 해치지 않아야 한다
• 모든 경우의 수를 따지지 않아도 그 순간마다 최선의 선택을 한다.

 

예시문제 : 체육복

---

def solution(n, lost, reserve):
    l = [1] * (n + 2) # 구현의 편리성을 위해 가장 앞과 뒤에 가상의 인물 추가
    for i in reserve:
        l[i] += 1
    for i in lost:
        l[i] -= 1
    
    for i in range(1, n+1):
        if l[i] == 2 and l[i-1] == 0:
            l[i], l[i-1] = 1,1
        if l[i] == 2 and l[i+1] == 0:
            l[i], l[i+1] = 1,1
    
    return len([x for x in l[1:-1] if x > 0]) # 가상의 인물을 제외하고 출력

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호 배열 lost, 여벌 체육복을 가져온 학생 번호 배열 reserve 이다.

자신의 번호 바로 앞 뒤로만 체육복을 빌려줄 수 있다고 할 때 최대한 많은 학생이 체육 수업을 듣게 해야한다.

여기까진 괜찮은데, 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있다고 한다.

 

그래서 사용한 알고리즘은.. 모든 학생들에게 체육복이 있다고 가정하고 ( 배열에 체육복 개수인 1 부여 )

입력받은 인자와 for문으로 각 번호마다 체육복의 개수를 구할 수 있다!

 

그 뒤로는 그리디로 그때그때 최적의 선택(왼쪽, 오른쪽에 체육복을 당장 빌려줘야 하는지)을 통해 구현한다.

---

 

---

 

정렬(Sort) 알고리즘

• 숫자의 비교가 필요한 알고리즘에 적합하다
• 정렬 후 다음을 구현하는 방법이 시간 복잡도에 도움을 줄 수도 있다.

 

예시 문제 : 가장 큰 수

---

def solution(numbers):
    li = [str(x) for x in numbers]
    li.sort(key=lambda x : (x * 4)[:4], reverse = True)
    
    if li[0] == "0": # 엣지 케이스 처리
        return "0"
    else:
        return "".join(li)

주어진 배열의 숫자 조합을 통해 가장 큰 수를 만들어내는 문제.

ex) 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210

 

처음 봤을 때는 구현하기 어려울 것 같았는데.. 코드는 많이 간단했다.

numbers의 원소가 0 이상 1,000이하라는 점을 활용해서

각 숫자로만 만들어진 네자릿수( (x*4)[:4] )를 통해 오름차순으로 정렬하고 문자열로 반환하면 끝..

 

방법은 간단하나 저걸 떠올리는 것이 어렵겠다..😂

---

 

---

 

🤔 공부하면서 어려웠던 내용

여러 코딩테스트 예시문제를 통해 적합한 알고리즘을 사용하는 방법을 배웠다.

보통 처음 내가 문제를 보고 생각했던 알고리즘보다 훨씬 간단하고 효율적으로 푸는 방법에 놀랐다..

아직 한참 부족하다고 생각했고.. 강사님 말대로 많은 문제를 풀어보는게 지금 나에게 가장 필요한 부분인 듯 하다 😭