1번

문제

철수와 친구들은 다함께 용돈을 모은 총 x원을 모두 소진하여 중국집에서 배달을 시키려고 한다. 각 음식의 가격은 food_list로 주어질 때, x원을 소진하기 위한 최소한의 음식 갯수를 반환하는 함수 solution을 완성하시오.

  • 예시 입출력
x food_list return
20000 [100, 1500, 1200, 300] 16

나의 풀이

소스

def solution(x, food_list):
    food_count = 0
    food_list.sort(reverse=True)

    for food_pay in food_list:
      calc_count = x // food_pay

      if calc_count > 0:
        food_count += calc_count
        x -= food_pay * calc_count
    
    return food_count

print(solution(20000, [100, 1500, 1200, 300]))

설명

그리디를 적용. 가장 높은 가격부터 순서대로.

예시답안

def solution(N, food_list):
    result = 0
    food_list.sort(reverse=True)
    for food in food_list:
        result += N // food
        N = N % food
    return result

2번

문제

그래프를 DFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

  • 입력: 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
  • 출력: V부터 방문된 점을 순서대로 출력한다.
  • 예시 입출력
N M V edges return
4 5 1 [[1, 2], [1, 3], [1,4], [2, 3], [3, 4]] 1 2 3 4

나의 풀이

소스

N, M, V = 4, 5, 1
edges = [[1, 2], [1, 3], [1,4], [2, 3], [3, 4]]

def solution(N, M, V, edges):
    def make_graph(edges):
        graph = dict()

        for edge in edges:
          first = edge[0]
          second = edge[1]
          if first not in graph:
            graph[first] = [second]
          else:
            graph[first].append(second)
          
          if second not in graph:
            graph[second] = [first]
          else:
            graph[second].append(first)

        return graph

    def dfs(graph, start):
        visited = list()
        need_visit = list()

        need_visit.append(start)

        while need_visit:
            node = need_visit.pop()
            if node not in visited:
                visited.append(node)
                need_visit.extend(sorted(graph[node], reverse=True))

        print(' '.join(map(str, visited)))

    graph = make_graph(edges)
       
    print(graph)
    dfs(graph, V)

solution(N, M, V, edges)

설명

그냥 주어진 edges로부터 graph를 구하고, 그 graph로 graph dfs 알고리즘 적용.

예시답안

def solution(N, M, V, edges):
    visited = []
    adj_lists = [[]]*(N + 1)
    for i in range(1, N + 1):
        adj_list = list(map(lambda x:x[1], (filter(lambda x:x[0] == i, edges)))) + list(map(lambda x:x[0], (filter(lambda x:x[1] == i, edges))))
        adj_list.sort()
        adj_lists[i] = adj_list
 
    def dfs(node):
        visited.append(node)
        print(node, end=' ')
        for n in adj_lists[node]:
            if n not in visited:
                dfs(n)
    dfs(V)
 
N, M, V = 4, 5, 1
edges = [[1, 2], [1, 3], [1,4], [2, 3], [3, 4]]
solution(N, M, V, edges)

3번

문제

그래프를 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

  • 입력: 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
  • 출력: V부터 방문된 점을 순서대로 출력한다.
  • 예시 입출력
N M V edges return
4 5 1 [[1, 2], [1, 3], [1,4], [2, 3], [3, 4]] 1 2 3 4

나의 풀이

소스

import sys
from collections import deque

def solution(N, M, V, edges):
    def make_graph(edges):
        graph = dict()

        for edge in edges:
          first = edge[0]
          second = edge[1]
          if first not in graph:
            graph[first] = [second]
          else:
            graph[first].append(second)
          
          if second not in graph:
            graph[second] = [first]
          else:
            graph[second].append(first)

        return graph

    def bfs(graph, start): 
        visited = list()
        need_visit = deque(list())
        
        need_visit.append(start)
        
        while need_visit:
            node = need_visit.popleft()
            if node not in visited:
                visited.append(node)
                need_visit.extend(sorted(graph[node]))

        print(' '.join(map(str, visited)))

    graph = make_graph(edges)

    bfs(graph, V)

solution(N, M, V, edges)

설명

위 DFS처럼 edgs로부터 graph를 구하고 bfs를 적용. 효율을 위해 deque를 사용하였다.

예시답안

import sys
from collections import deque
 
def solution(N, M, V, edges):
    adj_lists = [[]]*(N + 1)
    for i in range(1, N + 1):
        adj_list = list(map(lambda x:x[1], (filter(lambda x:x[0] == i, edges)))) + list(map(lambda x:x[0], (filter(lambda x:x[1] == i, edges))))
        adj_list.sort()
        adj_lists[i] = adj_list
 
    def bfs(start): 
        q = deque()
        visited = []
 
        q.append(start)
        visited.append(start)
 
        while q:
            front = q.popleft()
            print(front, end=' ')
            for node in adj_lists[front]:
                if node not in visited:
                    q.append(node)
                    visited.append(node)
    bfs(V)
N, M, V = 4, 5, 1
edges = [[1, 2], [1, 3], [1,4], [2, 3], [3, 4]]
solution(N, M, V, edges)

4번

문제

방향 그래프에서 최단경로를 구하고자 한다.그래프에 대한 정보들로는 각 노드로부터 간선이 연결된 정보가 딕셔너리 a로 주어진다. 이 때 시작 노드(start)에서 마지막 노드(final)까지의 최소비용을 구하시오.

a start final return
{'A': {'B': 2, 'C': 5, 'D': 1}, 'B': {'C': 8}, 'C': {}, 'D': {'C': 3}} 'A' 'C' 4

예시답안

import heapq
 
def solution(a, start, final):
    distances = {node: float('inf') for node in a}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])
 
    while queue:
        current_dist, current_node = heapq.heappop(queue)
 
        if distances[current_node] < current_dist:
            continue
 
        for adjacent, weight in a[current_node].items():
            distance = current_dist + weight
 
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
 
    return distances[final]
 
a= {
    'A': {'B': 2, 'C': 5, 'D': 1},
    'B': {'C': 8},
    'C': {},
    'D': {'C': 3}
}
start = 'A'
final = 'C'
print(solution(a, start, final))

설명

  • 유향 그래프에서 노드간의 최소거리를 구하는 문제였습니다.
  • Dijkstra 알고리즘을 이용하면 답을 구할 수 있습니다.