자료구조/알고리즘 - 파이썬 (TIL 5)

석형원·2024년 3월 29일
TIL자료구조

TIL

목록 보기
5/52

✏️ 오늘 학습한 내용

1. Heap 문제 풀이
2. DP 문제 풀이
3. DFS/BFS 문제 풀이

🔎 Heap 문제 풀이

1) 문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

2) 참고 사항

  • 알고리즘의 복잡도

    • Worst Case :
      • 수가 하나 남을 때까지 섞어야 하는 경우 (n-1)
    • 각 단계 (섞는 일) 에 요구되는 계산량 :
      • 정렬된 리스트에 순서를 맞추어 원소 삽입 O(N)
    • 전체 문제 풀이의 복잡도 :
      • O(N^2)

  • 보다 나은 방법

    • Heap을 사용 (최소/최대 원소를 빠르게 꺼냄)
    • Heap을 기반으로 만든 priority queue를 사용

  • Heaps

    • 성질 : 최대/최소 원소를 빠르게 찾음
    • 연산
      • 힙 구성 (heapify) - N*O(logN)
      • 삽입 (insert) - O(logN)
      • 삭제 (remove) - O(logN)

  • heapq 모듈

    • priority queue와 동일
    • import heapq 를 통해 호출
    • 빈 리스트(heap)를 생성 후 heapq 함수 호출
    • heapq.heappush(heap, item) : item을 heap에 추가
    • heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
    • heapq.heapify(x) : 이미 생성된 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

  • Priority queue

    • from queue import PriorityQueue 를 통해 호출
    • 기본적으로 오름차순 정렬
    • pq = PriorityQueue() : pq 선언
    • pq.put(x) : pq에 우선 순위에 알맞게 원소를 넣음
    • pq.get() : pq에서 가장 작은 원소(우선 순위)를 반환
    • pq.qsize() : pq 안의 원소 수를 반환
    • pq.empty() : pq가 비어있는지 확인하여 boolean값으로 반환
    • tuple형태로도 사용가능
      • pq.put((우선순위, 값))
      • 이때, 우선 순위에 음수를 넣어 내림차순도 가능
      • ex)
      	pq.put((-4,4))
	pq.put((-2,2))
	print(pq.get()[1])
	# -> 4

3) 문제 풀이

  • 풀이

    1. pq 혹은 heapq의 구조에 scoville 원소들을 넣어 내림차순으로 정렬되게 만든다.
      ( heap sort - O(log N) )
    2. 가장 작은 원소를 두 번 뽑고 연산을 적용하여 다시 집어넣는다.
      ( 가장 작은 원소가 K 이상이 될 때까지 반복 )

  • priority queue를 사용

from queue import PriorityQueue

def solution(scoville, K):
    answer = 0
    pq = PriorityQueue()
    for i in scoville :
        pq.put(i)
    
    while 1:
        a = pq.get()
        if a >= K :
            break
        if pq.empty() :
            return -1
        b = pq.get()
        pq.put(a+b*2)
        answer += 1
        
    return answer
  • heapq를 사용
import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while 1:
        a = heapq.heappop(scoville)
        if a >= K :
            break
        if len(scoville)==0 :
            return -1
        b = heapq.heappop(scoville)
        heapq.heappush(scoville,a+b*2)
        answer += 1
        
    return answer
  • 문제점
    • Python의 경우, PriorityQueue는 Thread-Safe 하고 heapq는 Non-safe하기 때문에 PriorityQueue가 더 오래걸린다.
    • 심하게는 10~30배까지 차이가 난다.
    • 이 문제에서도 동일한 알고리즘이지만 PriorityQueue는 시간초과가 걸린다.
    • 코딩 테스트는 heapq를 사용하자...

🔎 DP 문제 풀이

1) 동적계획법(Dynamic Programming)

주어진 최적화 문제를 재귀적인 방법으로 보다 작은 부분 문제로 나누어 풀어, 이 해들을 조합해 전체 문제의 해를 구하는 방법

2) 문제 설명

N으로 표현
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.

이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

3) 문제 풀이

  • 풀이

DP의 핵심은, 가능한 경우의 값을 모두 순차적으로 기록(저장)하여,
똑같은 경우의 값을 구하기 위해 이전에 했던 연산을 반복하지 않도록 하는 것이다.

이 문제의 경우, 사용한 횟수가 1인 수부터 시작해서 최대 값인 8까지 순차적으로 모든 연산을 계산해가며 리스트에 저장을 할 것이다.

여기서 핵심은 사용 횟수가 N+1인 경우를 구할 때, 우리가 이전까지 사용 횟수가 1~N인 경우를 구했다는 것을 이용하는 것이다.

N+1 = 1 + N = 2 + (N-1) = 3 + (N-2) = ...
( 1, 2, 3, 4, ..., N-3, N-2, N-1, N )

위와 같이 1~N에서 양 끝 값들을 더한 값이 N+1이 된다는 점을 고려하면, 이 연산들로 N+1이 되는 모든 경우를 계산할 수 있다.

( 단, 중복을 방지하기 위해 연산 결과를 set() 구조에 저장을 한다. )

  • 코드
def solution(N, number):
    answer = -1
    dp = []
    # N 사용 횟수가 1부터 8까지인 모든 경우를 계산
    for i in range(1,9) :
        num = set()
        # NN
        num.add(int(str(N)*i))

        # K = 1 + K = 2 + K-1 = 3 + K-2 ...
        for j in range(i-1) :
            # a : 앞에서부터 1, 2, 3, ..., K
            # b : 뒤에서부터 K, K-1, K-2, ..., 1
            
            for a in dp[j] : 
                for b in dp[-j-1] :
                    num.add(a+b)
                    num.add(a-b)
                    num.add(a*b)
                    if b != 0 :
                        num.add(a//b)
        
        if number in num :
            answer = i
            break
        
        dp.append(num)
    
    return answer

🔎 DFS/BFS 문제 풀이

1) 문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
  • 주어진 공항 수는 3개 이상 10,000개 이하입니다.
  • tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
  • 주어진 항공권은 모두 사용해야 합니다.
  • 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
  • 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

2) 문제 풀이

  • 풀이

    DFS를 사용해 ICN부터 다음 목적지를 순차적으로 선택해 끝까지 가보고 티켓을 다사용하지 못했다면, 다시 티켓 하나 사용전으로 돌아와서 다른 목적지를 고르는 방식으로 진행.

    주의사항 : 티켓을 사용하면 그때마다 체크해줘야하고 다시 사용전으로 돌아올 때, 체크했던 티켓을 원상복구 시켜줄 것

  • 코드

def dfs(start, tickets, t_size) :
    global answer
    global check
    global comp
    # 티켓을 다 소모하지 못했음
    if t_size == len(tickets) :
        comp = True
        return
    for i in range(len(tickets)):
        if start == tickets[i][0] and check[i]==0 :
            answer.append(tickets[i][1])
            check[i] = 1
            dfs(tickets[i][1],tickets,t_size+1)
            # 티켓을 다 소모하지 못한 경우,
            # check를 해제하고 이 경로는 제거
            if comp == False :
                check[i] = 0
                answer.pop()

def solution(tickets):
    global answer
    global check
    global comp
    answer = []
    check = [0 for _ in range(len(tickets))]
    comp = False
    tickets.sort()
    answer.append("ICN")
    dfs("ICN",tickets,0)
    return answer
profile
석형원
데이터 엔지니어를 꿈꾸는 거북이, 한걸음 한걸음
이전 포스트

자료구조/알고리즘 - 파이썬 (TIL 4)

다음 포스트

HTML 기본 (TIL 6)

0개의 댓글