[TIL] KDT_20230414

📚 KDT WEEK 2 DAY 5 TIL

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

• 힙(Heap)
• 깊이, 너비 우선 탐색(DFS / BFS)
• 동적계획법(Dynamic Programming)

 

---

 

힙(Heap) 알고리즘

• 정렬(Heapsort)과 우선 순위 큐(priority queue)에 유용
• 최대, 최소 원소를 빠르게 찾는데 유용하다!
• 파이썬에 heapq 라이브러리를 통해 구현 가능

예시 코드

---

import heapq # Heap 라이브러리

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville) # 특정 리스트를 힙으로 만듦
    
    while True: # 아래 if 조건으로 반복 종료
        min1 = heapq.heappop(scoville) # 힙 pop
        
        if min1 >= K:
            break
        elif len(scoville) == 0: # 아무리 합쳐도 K를 넘지는 못했음
            return -1
        
        min2 = heapq.heappop(scoville)
        
        new = min1 + min2 * 2
        heapq.heappush(scoville, new) # 힙 push
        answer += 1
    
    return answer

스코빌 지수가 가장 낮은 음식 두개를 합쳐 모든 음식을 특정 스코빌 지수(K)를 넘도록 만드는 코드.

스코빌지수의 계산은 new = min1 + min2 * 2 이다.

파이썬의 heapq 라이브러리가 있어 구현이 매우 편리하다! 🤭

---

깊이 우선 탐색(DFS)

• 한 정점에서 인접한 모든 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 방문 진행
• 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아가야함
• 정점에서 길이 있으면 들어갈 수 있을 만큼 들어간(DFS) 다음, 막혔을 때 길이 보일 때 까지 되돌아가는 것!

---

def solution(tickets):
    ticketDic = {}
    for t in tickets: # Dictionary에 tickets 저장
        ticketDic[t[0]] = ticketDic.get(t[0], []) + [t[1]]
        
    for tD in ticketDic: # ticket마다 도착지를 역순으로 정렬
        ticketDic[tD].sort(reverse = True)
    
    stack = ["ICN"] #출발지
    resultPath = [] #경로
    while len(stack) > 0:
        top = stack[-1]
               
        if not top in ticketDic or len(ticketDic[top]) == 0: #다음 경로 자체가 없었거나, 더 이상 표가 없는 경우
            resultPath.append(stack.pop()) 
        else:
            stack.append(ticketDic[top][-1])
            ticketDic[top] = ticketDic[top][:-1]
            
    return resultPath[::-1]

 tickets 인자를 통해 [출발지, 도착지] 표 들의 배열을 받아 모든 경로를 순회하는 path를 만드는 문제다.

스택으로 구현한 DFS를 통해 구현한다.

알파벳 순으로 먼저 여행해야 하는 조건을 sort로 먼저 해결했고,

여행을 다니다 다음 경로가 없는 여행지를 만나면, 먼저 path에 넣어두고 마지막에 역순으로 출력하여 마지막 여행지로 만드는 게 인상적이었다. 👍

DFS의 구조와 문제의 관계를 이해하는 데에 오래 걸렸던 문제..😂

---

너비 우선 탐색(BFS)

• 한 정점에서 인접한 모든 정점을 먼저 순서대로 방문하고, 방문한 인접 정점을 기준으로 방문한 순서에 따라 너비 우선 탐색을 진행한다
• 큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행해야 한다!

 

---

 

동적 계획법(Dynamic Programming)

• 주어진 문제를 작은 부분 문제로 나누고, 해를 구한 뒤 재귀적인 방식으로 전체 문제의 해답을 구하는 방식
• 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정한다!
• 피보나치 수열, Knapsack Problem 등이 적용될 수 있다.

예시 코드

---

def solution(N, number):
    s = [set() for x in range(8)] #set으로 만들어 중복 제거 가능
    							  #주의 : 0부터 시작하지만, s[0]에는 N을 한번 사용한 집합이 될 것임.
    
    for i, x in enumerate(s, start = 1): # 먼저 N, NN, NNN... 과 같은 문자열 넣어놓기
        x.add(int(str(N) * i))
        
    for i in range(len(s)): 
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i-j-1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break
    
    else:
        answer = -1
        
    return answer

N을 사칙연산(괄호 포함)만을 사용해서 number를 표현할 수 있는 방법 중 최솟값을 구해야한다.

ex) N = 5, number = 12 \\ 12 = (55 + 5) / 5 ➡ answer = 4

문제는 간단하지만, 그 경우의 수가 매우 많아 복잡한 연산이 필요했었다.

하지만 동적 계획법을 이용하면, 코드로는 비교적 간단히 구현 가능하다.(연산도 훨씬 효율적이다)

s[i]에 전에 했던 연산들( i+1개의 N으로 만들 수 있는 숫자 집합)을 저장했다가 다음 연산에도 활용함으로써 효율적인 연산을 할 수 있게 된다!

 

---

 

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

사소하게 착각했던 부분이 걸림돌이 되어 이해하는데 많은 시간을 할애했었다..😥

그래도 이해하고 보니 나중에 꼭 필요한 알고리즘들이라는 게 몸으로 느껴졌다..

열심히 배웠으니 나중에 알아서 활용할 줄 알아야 할텐데..😇