[TIL_2023.10.20] 자료구조와 알고리즘 (5) : 힙, DFS/BFS, 동적 계획법 대표 문제 풀이

1주차 금요일, 5일차 Today I Learned

 

 

자료구조와 알고리즘 (5) 
: 힙, DFS/BFS, 동적 계획법 대표 문제 풀이

 

반응형

 

✏️ 학습 내용

1. 힙 대표 문제 : 더 맵게

Q. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.
- 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
스코빌 지수가 K 이상이 될 때까지 반복하여 섞어야 하는 최소 횟수를 리턴하는 함수를 작성하라.

제한 사항 :
- 음식의 스코빌 지수를 담은 scoville의 길이는 1 이상 1,000,000 이하, 원소는 0 이상 1,000,000 이하
- K는 0 이상 1,000,000,000 이하

일반적으로 문제를 풀 경우, 정렬시킨 후 앞에서부터 숫자를 합치며 K와 비교하며 연산하는 방식으로 진행된다.

이렇게 되면 최악의 경우, 수가 하나 남을 때까지 섞어야 한다. (n-1회) 각 단계 (섞는 일)에서 요구되는 계산량은 정렬된 리스트에 순서 맞추어 원소를 삽입하여 O(n)의 복잡도를 갖는다. 그래서 전체 문제 풀이의 복잡도는 O(n^2) 정도로 높다.

 

보다 나은 방법은 최소/최대 원소를 빠르게 꺼낼 수 있다면 가능하다. -> 최대 힙/최소 힙 이용!!

따라서 힙을 완전 이진 트리로 구성(heapify)하고, 삽입/삭제 연산을 수행하면 된다. 힙 구성은 배열을 이용해서 구현해서 O(NlogN) 복잡도, 삽입 및 삭제는 O(logN) 복잡도를 갖는다. 따라서 전체 복잡도는 O(logN)으로, 굉장히 효율적으로 변하게 된다. 참고로 힙은 정렬과 우선 순위 큐에서 응용할 수 있으며, 공간 효율성 또한 높다. 힙 정렬은 O(NlogN)의 복잡도를 가지며, 최악의 복잡도가 최적의 복잡도가 된다.

 

- import heapq

- heapq.heapify(L) : 리스트 L로부터 min heap을 구성

- heapq.heappop(L) : min heap L에서 최소값 삭제/반환

- heapq.heappush(L, x) : min heap L에 원소 x 삽입

import heapq

def solution(scoville, K) :
	answer = 0
    heapq.heapify(scoville)
    while True : 
    	min1 = heapq.heappop(scoville)
        if min >= K :
        	break
        elif len(scoville) == 0 :
        	answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_scoville = min1 + min2 * 2
        heapq.heappush(scoville, new_scoville)
        answer += 1
    return answer

힙을 이용하면 최소 또는 최대의 값을 빨리 꺼낼 수 있고, 삽입 및 삭제가 O(logN) 정도의 복잡도를 갖는다는 장점이 있다.

 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    count = 0
    while True :
        a = heapq.heappop(scoville)
        if a >= K :
            return count
        if len(scoville) == 0 :
            return -1
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a+b*2)
        count += 1

스코빌 지수를 계산하고 K 이상의 스코빌 지수를 얻을 때까지 연산을 반복한다. 힙을 사용하여 가장 낮은 스코빌 지수를 효율적으로 가져오고, 연산을 수행한 후 새로운 스코빌 지수를 다시 힙에 추가하는 방식이다. 시간 복잡도가 O(N log N)이며, N은 scoville 리스트의 길이이다. 힙 연산의 시간 복잡도가 주요 요인이며, 모든 연산에서 O(log N)의 시간이 소요된다.

 

---

 

2. 동적 계획법 대표 문제 : N으로 표현

동적 계획법 (Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 주어진 최적화 문제를 재귀적인 방식으로 보다 작은 부분 문제로 나눈 후, 부분 문제를 풀고 이 해를 조합하여 전체 문제의 해답에 이르는 방식이다. 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있다.

 

예를 들어, 피보나치 수열을 재귀함수로 구현한다면, f(n)을 구하기 위해서 n-1번 만큼의 재귀 호출이 수행된다. 따라서 복잡도가 지수 함수의 형태로 나타난다. 반면 동적계획법을 적용한다면, 문제의 부분해를 구한 다음 전체를 조합하면 되므로 복잡도가 선형 함수의 형태로 나타난다.

 

동적 계획법의 적용은 대표적으로 Knapsack Problem 예시가 있다. 가방의 용량, 물건들의 용량 및 가격이 정해져 있을 때, 가장 높은 값을 가지도록 물건들을 골라 배낭에 담는 문제이다.

 

여기서는 다른 문제를 살펴본다. N으로 표현하는 문제이다.

Q. 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 number를 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 리턴하는 함수를 작성하라.

제한사항 : 
- N은 1 이상 9 이하
- number는 1 이상 32,000 이하
- 수식은 괄호, 사칙연산 가능 (나누기 연산에서 나머지는 무시)
- 최솟값이 8보다 크면 -1을 리턴

동적 계획법으로 풀고자 한다면, 1) N을 n번 사용해서 만들 수 있는 수를 모두 구하고 → 2) number가 해당하는 n을 찾으면 된다.

 

부분 문제 풀이에 해당하는 n의 값들을 구하는 방법은 기본적으로 ➀ N을 n번 이어붙인 수를 하나 구하고, ➁ n-1가지 조합에 해당하는 수들을 각각 구해야 한다는 것이다.

 

n의 값들을 구하는 방법 : 

➀ N을 n번 이어붙인 수 하나 : "N" * n

➁ n-1가지 조합 : a + 사칙연산 + b

- a = 1부터 n-1까지

- b = n-a

발생할 수 없는 최악의 경우 : (숫자의 사용 횟수, 만들어지는 결과의 수효)
(1, 1), (2, 5), (3, 41), (4, 429), (5, 5073), (6, 64469), (7, 859385), (8, 11853949)
* 실제로 만들어지는 결과의 개수는 더 적다.

 

즉, 문제의 성질에 따라 동적계획법으로 풀어냄으로써 탐색해야 하는 범위를 효과적으로 줄일 수 있다.

 

def solution(N, number):
	s = [set() for x in range(8)]
    for i, x in enumerate(s, start=1) :
    	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

 

 

---

 

 

3. 깊이/너비 우선 탐색 (DFS/BFS) 대표 문제 : 여행 경로

이 문제를 해결하기 위해서는 그래프 (graphs)의 정점 (vertex, node) 및 간선 (edge, link), 유향 (directed) 및 무향 (undirected), 스택 (stack)과 큐 (queue)에 대해서 알아야 한다.

 

Q. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 리턴하는 함수를 구하라.

제한사항 : 
- 항상 "ICN" 공항에서 출발
- 모든 공항은 알파벳 대문자 3글자
- 주어진 공항 수는 3개 이상 10,000개 이하
- tickets[a, b] = a공항에서 b공항으로 가는 항공권
- 주어진 항공권 모두 사용
- 가능한 경로가 2개 이상일 경우 알파벳 순서에 따라 경로를 리턴
- 모든 도시를 방문할 수 없는 경우는 없다

 

스택을 이용하여 재귀적인 그래프의 깊이 우선 탐색응 응용하여 한 붓 그리기 문제를 해결하면 된다. 사전을 이용하여 각 공항에서 출발하는 항공권의 집합을 리스트로 표현한다. 단, 도착 공항들은 알파벳 역순이어야 한다. {출발 공항 : [도착 공항들]}

def solution(tickets) :
	routes = {}
    for t in tickets :
    	routes[t[0]] = routes.get(t[0], []) + [t[1]]
    for r in routes :
    	routes[r].sort(reverse=True)
    stack = ["ICN"]
    path = []
    while len(stack) > 0 :
    	top = stack[-1]
        if top not in routes or len(routes[top]) == 0 :
        	path.append(stack.pop())
    	else : 
        	stack.append(routes[top][-1])
            routes[top] = routes[top][:-1]        
    return path[::-1]

이 알고리즘의 복잡도는 5-6행의 정렬에 의해 결정된다.

 

def solution(tickets):
    # 각 출발지에서 가능한 도착지 목록을 저장하는 딕셔너리 routes 초기화
    routes = {}
    
    # 항공권 정보를 반복하여 처리
    for t in tickets:
        # 출발지를 키로, 도착지를 값으로 추가 (여러 도착지를 리스트로 저장)
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    
    # 각 출발지에서 가능한 도착지 목록을 내림차순으로 정렬
    for r in routes:
        routes[r].sort(reverse=True)
    
    # 스택 초기화 및 시작 지점 추가
    stack = ["ICN"]
    answer = []
    
    # 스택이 빌 때까지 반복
    while len(stack) > 0:
        top = stack[-1]
        
        # 현재 위치가 routes에 없거나, 더 이상 갈 수 있는 도착지가 없는 경우
        if top not in routes or len(routes[top]) == 0:
            answer.append(stack.pop())  # 경로에 현재 위치 추가 및 스택에서 제거
        else:
            stack.append(routes[top][-1])  # 가능한 도착지 중 하나를 스택에 추가
            routes[top] = routes[top][:-1]  # 사용한 도착지 제거

    # 역순으로 된 경로 반환 (ICN부터 시작하여 도착지까지)
    return answer[::-1]

 

 

---

☁️ 소감

새롭게 등장한 개념인 DS 문제와 탐색 알고리즘 관련 문제가 어려웠다. 이번에 챗GPT를 이용해서 코드에 대해 물어보며 작성을 했는데 꽤 도움이 되었다. 동적 계획법의 원리는 이해가 가지만 알고리즘을 구현하는 것은 어려운 것 같다. 원래부터가 복잡한 문제여서 그런 것일까.. 챗GPT에게 물어봐야겠다. 처음에는 어렵게 느껴질 수 있지만, 계속 공부하다 보면 보다 복잡한 문제도 효과적으로 해결할 수 있게 될 것 같다.