[인공지능 데브코스] 1주차 day4 - 알고리즘 문제풀이(2)

12월 03일 목

어제에 이어서 프로그래머스 알고리즘 문제를 계속 풀었다. 아직 까진 문제의 난이도가 높지 않아서 큰 어려움은 없었다. 파이썬 코딩이 점점 익숙해 지고 있는 것 같다.

더 맵게 (Heap)

heap을 사용하는 문제로 파이썬에서 제공하는 heapq를 이용하여 풀었다.
heap을 사용해야 한다는 사실만 알면 구현은 간단하다.

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        
        v1 = heapq.heappop(scoville)
        v2 = heapq.heappop(scoville)
        v3 = v1 + v2*2
        heapq.heappush(scoville, v3)
        answer += 1
    return answer

 

N으로 표현 (DP)

dp를 이용해서 푸는 문제로 dp[i]를 문자 i개를 사용해서 만들 수 있는 모든 숫자의 set으로 설정하고 풀었다.
이때 모든 숫자를 이어붙이는 경우는 초기값으로 미리 넣어주어야 한다.
dp[i]는 dp [0] ~ dp[i-1]들로 표현이 가능하므로 1부터 원하는 숫자가 있을때 까지 반복하여 가장 적은 개수로 답을 구하는 방법을 찾았다.

def solution(N, number):
    if number == N: 
        return 1
    
    dp = [{int(str(N) * (i+1))} for i in range(8)]
    for i in range(1,8):
        for j in range(0, i):
            dp[i] |= sumSet(dp[j], dp[i-j-1])
        if number in dp[i]:
            return i+1
    return -1

def sumSet(set1, set2):
    ans = set()
    for i in set1:
        for j in set2:
            ans.add(i+j)
            ans.add(i-j)
            ans.add(i*j)
            if j!= 0:
                ans.add(i//j)
    return ans

 

여행경로 (DFS/BFS)

DFS/BFS를 사용하여 푸는 문제로 나는 DFS를 사용하여 풀었다.
dic을 선언하여 ([출발점], [[도착점1, 사용여부], [도착점2, 사용여부], ….]) 와 같은 형식으로 tickets를 저장하고 처음에는 앞에있는 티켓부터 사용한다는 규칙으로 dfs를 적용하였다.
그 전에 dic의 각요소를 sort하여 알파벳 순서가 되도록 하였다.
파이썬에서는 함수의 입력값이 항상 reference로 들어간다는 사실을 알았다.

def solution(tickets):
    dic = {}; l = len(tickets)
    for ticket in tickets:
        dic[ticket[0]] = dic.get(ticket[0], []) + [[ticket[1] , 1]]
    for a in dic:
        dic[a].sort()
    ans = ["ICN"]
    dfs(ans, "ICN", dic, len(tickets))
    return ans

def dfs(ans, key, dic, l):
    if l==0:
        return True
    if not key in dic:
        return False
    for c in dic[key]:
        if c[1] == 1:
            c[1] = 0
            ans.append(c[0])
            if dfs(ans, c[0], dic, l-1): 
                return True
            ans.pop()
            c[1] = 1