길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 길이)
제한 사항 2. a, b의 길이는 1 이상 1,000 이하입니다. 3. a, b의 모든 수는 -1,000 이상 1,000 이하입니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
주어진 각각의 리스트를 동일한 인덱스끼리 곱한 리스트 값들의 총 합을 구하는 문제였습니다.
a와 b는 같은 길이의 리스트이므로 a 또는 b의 길이로 반복문을 순회합니다.
해당 인덱스의 a와 b의 값들을 곱한 값들을 더해서 리턴해줍니다.
💡 내가 해결한 방식은?
def solution(a, b):
return sum(a[i]*b[i] for i in range(len(a)))
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다. 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.
제한 사항 1. n은 2 이상 100 이하인 자연수입니다. 2. wires는 길이가 n-1인 정수형 2차원 배열입니다. 2-1. wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다. 2-2. 1 ≤ v1 < v2 ≤ n 입니다. 2-3. 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
가장 먼저 트리를 어떻게 저장할 지 고민해보아야 합니다. 각각의 노드와 해당 노드에 연결된 노드를 저장하는 딕셔너리 형태로 초기화합니다. 보통 트리를 초기화 할 때는 다음 형태의 초기화 방식을 기억하면 좋습니다.
from collections import defaultdict ... # 트리 defaultdict를 통해 초기화 graph = defaultdict(list) for x, y in wires: graph[x].append(y) graph[y].append(x) ...
여기서 defaultdict 함수를 사용함으로써 얻게 되는 장점은 다음과 같습니다.
해당 키 값이 존재하는지 아닌지 확인하지 않아도 됩니다. (없으면 자동 생성)
키를 생성하고 0 초깃값을 할당해줍니다.
트리 초기화를 했다면 문제는 입력받은 전선으로 나눌 때 발생하는 모든 경우의 수를 구해야 합니다. DFS 탐색을 통해 해당 문제를 풀이할 때 문제 해결 과정은 다음과 같습니다.
트리를 나누는 경우의 수를 순회합니다.
나누려는 간선 정보를 순회하면서 간선의 왼쪽과 오른쪽 노드를 구분합니다.
dfs를 통해 왼쪽 노드부터 시작하는 노드의 개수를 완전 탐색 합니다.
왼쪽 개수를 구했다면 전체 노드 개수 n개에서 오른쪽 개수를 구할 수 있습니다.
왼쪽 개수와 오른쪽 개수의 차를 통해 송전탑 개수가 가장 비슷한 최소 값을 구합니다.
노드의 개수가 비슷하기 위해서는 왼쪽과 오른쪽의 차이가 가장 작은 최솟 값을 구해야 합니다. 최솟 값이나 최댓 값을 구할 때 변수는 다음과 같이 초기화 해야 안전합니다.
min_diff = float('inf') # 최솟값일 경우 max_diff = -float('inf') # 최댓값일 경우
DFS 탐색할 때 방문 배열은 set 객체로 생성하여 중복되지 않도록 방지해야 한다는 점 잊지 말아야 합니다.
해당 문제는 트리를 초기화하고 DFS 를 사용하여 최솟 값을 구하는 전형적인 map 탐색 문제였습니다.
💡 내가 해결한 방식은?
dfs를 사용한 풀이
from collections import defaultdict
def solution(n, wires):
# 트리 defaultdict를 통해 초기화
graph = defaultdict(list)
for x, y in wires:
graph[x].append(y)
graph[y].append(x)
# 전선을 삭제하고 나누어진 트리 개수 탐색
def dfs(start, removed_edge, visited):
count = 1
# 시작 노드 방문 배열 추가
visited.add(start)
# 시작 노드에 연결되어 있는 노드들 dfs 탐색
for node in graph[start]:
# 방문 처리가 되지 않거나, 나눈 간선에 포함되지 않을 경우
if node not in visited and (start, node) != removed_edge:
count += dfs(node, removed_edge, visited)
return count
# 송전탑 개수가 100개 이하이므로 float('inf') 를 사용하는 것이 효율적
# 최소값이나 최대값을 찾을 때는 float('inf') or -float('inf')를 사용
# min_diff = 123456789
min_diff = float('inf')
# 트리 나누는 경우
for wire in wires:
# 삭제할 전선 초기화
removed_edge = (wire[0], wire[1])
# set 객체의 방문배열 초기화
visited = set()
# 나눈 전선의 왼쪽부터 시작하는 전선의 개수 dfs 탐색
cnt_left = dfs(wire[0], removed_edge, visited)
cnt_right = n - cnt_left
min_diff = min(min_diff, abs(cnt_left - cnt_right))
return min_diff
n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다. 단, 미로를 탈출하는 조건이 세 가지 있습니다.
1. 격자의 바깥으로는 나갈 수 없습니다. 2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
l: 왼쪽으로 한 칸 이동 r: 오른쪽으로 한 칸 이동 u: 위쪽으로 한 칸 이동 d: 아래쪽으로 한 칸 이동
예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다. 미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다. 예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.
.... ..S. E...
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. . 은 빈 공간, S는 출발 지점, E는 탈출 지점입니다. 탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다. 1. lldud 2. ulldd 3. rdlll 4. dllrl 5. dllud... ...
이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다. 격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.
제한 사항 1. 2 ≤ n (= 미로의 세로 길이) ≤ 50 2. 2 ≤ m (= 미로의 가로 길이) ≤ 50 3. 1 ≤ x ≤ n 4. 1 ≤ y ≤ m 5. 1 ≤ r ≤ n 6. 1 ≤ c ≤ m(x, y) ≠ (r, c) 7. 1 ≤ k ≤ 2,500
