target 이상이면서 가장 작은 조합을 구하고, 조합의 합과 target의 차이를 return 하라.
접근
N = 20이므로, 백트래킹으로 풀이하면 2 ** 20 ~= 1,000,000 정도일 것이다. 총합이 target 이상이 되면, target과의 차이를 현재 result 값과 비교하여 갱신한다.
모든 원소에 대하여 (추가하거나 / 추가하지 않거나)의 경우를 고려하고, 모든 원소를 탐색하면 result를 갱신한다.
코드
def solve(i, total):
global n, target, res
if i == n:
if total >= target:
res = min(res, total - target)
return
solve(i + 1, total + heights[i])
solve(i + 1, total)
T = int(input())
for tc in range(T):
n, target = map(int, input().split())
heights = list(map(int, input().split()))
res = 1e9
solve(0, 0)
print(f'#{tc + 1} {res}')
간단한 코드이지만, 2 * n개의 경우의 수를 고려하는 백트래킹 문제의 뼈대 코드인 듯하다.
시작점부터 도착점까지 가장 빠른 길을 찾아야 한다. -> BFS 섬(1)은 지나갈 수 없다. 소용돌이(2)는 지나갈 수 없다. 다만 한 번 통과한 경우 지나갈 수 있다. 소용돌이(2)는 0초부터 시작해서 2초 동안 유지되고 1초 동안 잠잠해지는 패턴을 반복한다.
접근
BFS 탐색을 하다가 소용돌이를 만났을 때는 판단을 해야 한다. 방문한 위치인 경우 -> 지날 수 있다 방문하지 않은 위치인 경우 time % 3 == 2인 경우, 지날 수 있다 이때 2를 0으로 바꿔야 한다. 한 번 방문한 뒤에는 언제든 지나갈 수 있기 때문에. 나머지의 경우, 지날 수 없다.
BFS 탐색을 하는 경우 큐에는 (x, y, time)이 담겨야 한다. 그래야 최단 경로를 판단할 수 있기 때문에 visited 배열은 (x, y, time)의 원소가 완벽하게 같은 경우 걸러낸다.
4방향 탐색이 아니라, 가만히 있기를 포함한 5방향 탐색이기 때문에, 방문 여부를 결정하기 위해 time이 필요하다.
코드
from collections import deque
dx = [1, -1, 0, 0, 0]
dy = [0, 0, 1, -1, 0]
def bfs(a, b, time):
q = deque()
q.append((a, b, time))
visited = []
visited.append((a, b, time))
while q:
x, y, t = q.popleft()
if x == ex and y == ey:
return t
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if matrix[nx][ny] == 1:
continue
if matrix[nx][ny] == 2:
if t % 3 == 2:
matrix[nx][ny] = 0
q.append((nx, ny, t + 1))
visited.append((nx, ny, t + 1))
else:
continue
if (nx, ny, t + 1) not in visited:
q.append((nx, ny, t + 1))
visited.append((nx, ny, t + 1))
testCase = int(input())
for tc in range(testCase):
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
sx, sy = map(int, input().split())
ex, ey = map(int, input().split())
result = bfs(sx, sy, 0)
print(f"#{tc + 1} {result}")
swea에서 해당 문제의 python 제출을 허용하지 않아, 정확한 정답 여부는 알 수 없다.
코테에서 유사한 문제를 풀었던 경험이 있어 어렵지 않게 풀었다.
"제자리에 있기"를 탐색 방향에 포함하는 것이 까다로운데, 시간까지 포함한 visited 배열로 관리하면 풀이할 수 있다.
from collections import deque
dx = [1, 1, -1, -1, 1, -1, 0, 0]
dy = [1, -1, 1, -1, 0, 0, 1, -1]
def openMatrix(x, y):
tmp = 0
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if matrix[nx][ny] == "*":
tmp += 1
matrix[x][y] = tmp
def clickZeroElement(a, b):
q = deque()
q.append([a, b])
matrix[a][b] = "*"
while q:
x, y = q.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if matrix[nx][ny] == 0:
q.append([nx, ny])
matrix[nx][ny] = "*"
elif matrix[nx][ny] != "*":
matrix[nx][ny] = "*"
testCase = int(input())
for tc in range(testCase):
n = int(input())
matrix = [list(input()) for _ in range(n)]
total = 0
for i in range(n):
for j in range(n):
if matrix[i][j] == ".":
openMatrix(i, j)
for i in range(n):
for j in range(n):
if matrix[i][j] == 0:
clickZeroElement(i, j)
total += 1
for i in range(n):
for j in range(n):
if matrix[i][j] != "*":
total += 1
print(f"#{tc + 1} {total}")
전형적인 삼성 스타일의 문제인 듯하다.
그래도 아주 어렵지는 않다.
클릭 수가 최소가 되게 하는 방법을 고민하다보면, 완전 탐색으로는 불가능하다는 것을 알게 된다.
A non-empty array A consisting of N integers is given.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].
Write a function:
def solution(A)
that, given an array A consisting of N integers, returns the maximum sum of any slice of A.
For example, given array A such that:
A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
the function should return 5 because:
(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..1,000,000];
each element of array A is an integer within the range [−1,000,000..1,000,000];
the result will be an integer within the range [−2,147,483,648..2,147,483,647].
문제 분석
Maximum slice 유형.
번역을 한다면 '배열에서 최대가 되는 부분합' 정도가 되겠다.
배열의 길이가 1,000,000 이하이므로 반드시 O(N) 이하의 시간복잡도로 풀어야 함.
배열의 원소의 범위는 [-1,000,000 ... -1,000,000] 이다.
Codility의 교육 자료에 있는 O(N)으로 풀이하려 했으나, 추가적으로 원소가 음수인 경우를 처리해야 한다.
풀이
def solution(A):
max_ending = max_slice = A[0]
for i in range(1, len(A)):
max_ending = max(A[i], max_ending + A[i])
max_slice = max(max_ending, max_slice)
return max_slice
max_ending과 max_slice를 명확히 하고 넘어가야 이 간단한 코드를 이해할 수 있다.
max_ending: 현재 인덱스까지의 부분 배열중에서 가장 큰 합
max_slice: 현재까지 찾은 모든 부분 배열 중에서 가장 큰 합
좀 더 설명해 보자면,
max_ending은 반복문을 실행하는 각 단계에서, 현재 부분 배열(지금 배열이 최선이라고 가정하고 계산 중인)의 최대 합을 계산한다.
max_slice은 모든 max_ending을 비교하여(실제로는 모든 값을 나열하고 비교하지 않는다. 하지만 모든 max_ending은 max_slice에 게 도전하게 된다.) 최대 합을 계산한다.
한 줄씩 이해해 보자.
`max_ending = max_slice = A[0]`
초기화 하는 부분이다.
배열의 첫 번째 원소로 초기화 한다.
0으로 초기화를 하면, 모든 원소가 음수인 경우 0을 반환하는 문제가 생긴다.
`for i in range(1, len(A)):`
첫 번째 원소로 초기화 했으니, 첫 번째 원소는 건너뛴다.
`max_ending = max(A[i], max_ending + A[i])`
가장 고민을 많이 한 부분이다.
max_ending을 갱신할 때 무엇과 비교해야 하는가?
max() 함수의 두 번째 인자는 현재 부분 배열에 새로운 값을 더한 것이다. 자연스럽다.
def solution(A):
result = 0
min_value = 200001
for i in range(len(A)):
if min_value < A[i]: # 0 <= P <= Q < N일 때, A[Q] - A[P]가 양수인 경우만 판단. 음수는 어차피 0으로 반환해야 함.
result = max(result, A[i] - min_value)
min_value = min(min_value, A[i]) # 계산 이후 최솟값 갱신.
return result
좌: Union-Find 수행 이후 서로소 관계를 파악 가능 / 우: 부모 노드(!= 루트 노드)만을 저장한다.
서로소 집합 자료구조에서는 손쉽게 집합의 형태로 연결 여부를 확인할 수 있다.
기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
오른쪽 그림의 예시에서는, 노드 3의 루트를 찾기 위해서 노드 2 -> 노드 1 순서로 접근해야 한다.
구현: 기본적인 형태
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
if parent != x:
return find_parent(parent, parent[x]) # 루트 찾을 때까지 재귀 호출
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 일반적인 문제 형태 ...
# 노드 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)
# 부모 테이블을 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# Union 연산
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합(루트 노드) 출력하기
for i in range(1, v + 1):
print(find_parent(parent, i))
기본적인 구현 방법의 문제점
출처: 유튜브 캡쳐
Union 연산이 편향되게 이루어 지는 경우 Find 연산이 비효율적으로 동작한다.
최악의 경우 Find 연산이 모든 노드를 다 확인해야 하므로 시간 복잡도가 O(V)이다.
이것을 개선하기 위해 `경로 압축`이 필요하다.
구현: 경로 압축
Find 연산을 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.
Find 함수를 재귀적으로 호출한 뒤에, 부모 테이블 값을 바로 갱신한다.
def find_parent(parent, x):
if parent != x:
parent[x] = find_parent(parent, parent[x]) # 부모 테이블을 즉시 갱신
return parent[x]
경로 압축 기법을 적용하면 부모 노드 테이블이 루트 노드를 가리킨다.
경로 압축의 과정에서, 각 Find 연산이 수행될 떄마다 경로 상의 모든 노드를 루트로 직접 연결하면서 트리의 높이를 평탄화한다.
(이때 부모 노드는 곧 루트 노드이다.)
경로 압축을 적용했을 때 Union-Find 연산의 시간 복잡도는 `O(α(N))`이다.
`α(x)`는 애커만 함수의 역함수이다.
애커만 함수는 재귀 함수의 일종으로 입력 값이 작더라도 매우 빠르게 증가한다.
반대로 역 애커만 함수는 x가 2^65536 일때 그 값이 4 ~ 5 정도이다. 거의 상수 시간이라고 할 수 있다.
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
if parent != x:
return find_parent(parent, parent[x]) # 루트 찾을 때까지 재귀 호출
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 일반적인 문제 형태 ...
# 노드 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)
# 부모 테이블을 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
cycle = False # 사이클 발생 여부
for i in range(e):
a, b = map(int, input().split())
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
else:
union_parent(parent, a, b)
if cycle:
print("사이클 발생")
else:
print("사이클 발생하지 않음")
신장 트리 Spanning Tree
출처: 유튜브 캡쳐
정의
모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
최소 신장 트리 MST, Minimum Spanning Tree
출처: 유튜브 캡쳐
최소한의 비용으로 구성되는 신장 트리
크루스칼 알고리즘 Kruskal Algorithm
출처: 위키피디아
정의
최소한의 비용으로 만들 수 있는 최소 신장 트리를 찾는 알고리즘.
대표적인 최소 신장 트리 알고리즘.
그리디 알고리즘으로 분류.
동작 과정
간선 데이터를 비용에 따라 오름차순으로 정렬
간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인
사이클이 발생하지 않는 경우, 최소 신장 트리에 포함
사이클이 발생하는 경우, 최소 신장 트리에 포함하지 않음
모든 간선에 대하여 2번의 과정을 반복
구현
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0] * (v + 1)
edges = [] # 모든 간선을 담을 리스트
result = 0 # 최종 비용
for i in range(1, v + 1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int, input().split())
edges,append((cost, a, b))
edges.sort() # 간선을 비용 순으로 정렬
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b): # 사이클이 발생하지 않는 경우 집합에 포함
union_parent(parent, a, b)
result += cost # 비용 더하기
print(result)
특징
간선의 개수가 E개일 때 `O(ElogE)`의 시간 복잡도를 갖는다.
가장 많은 시간을 요구하는 곳은 간선을 정렬하는 부분이다.
위상 정렬 Topological Sorting
출처: tutorialhorizon
정의
사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열.
순서가 정해져 있는 작업을 차례대로 수행해야 할 때, 그 순서를 결정하는 알고리즘이다.
예컨대, 라면을 끓이려면 물이 먼저 끓어야 한다. 특정 과목을 수강하려면 선수 과목을 수강해야 한다.
진입차수와 진출차수
출처: 유튜브 캡쳐
진입차수: 특정한 노드로 들어오는 간선의 개수
진출차수: 특정한 노드에서 나가는 간선의 개수
동작 과정: 큐 (진입 차수)
진입차수가 0인 모든 노드를 큐에 넣는다.
큐가 텅 빌 때까지 다음의 과정을 반복한다.
큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
결과적으로 각 노드가 큐에 들어온 순서가, 위상 정렬을 수행한 결과와 같다.
구현: 큐
from collections import deque
v, e = map(int, input().split())
indegree = [0] * (v + 1) # 모든 노드에 대한 진입차수는 0으로 초기화
graph = [[] for i in range(v + 1)] # 간선 정보를 담을 리스트
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 노드 A에서 B로 이동 가능
indegree[b] += 1
def queue_topological_sort():
result = []
q = deque()
for i in range(1, v + 1):
if indegree[i] == 0: # 진입차수가 0인 노드를 큐에 삽입
q.append(i)
while q:
now = q.popleft()
result.append(now)
for i in graph[now]:
indegree[i] -= 1 # 현재 노드와 연결된 노드의 진입 차수 1 빼기
if indegree[i] == 0: # 새롭게 진입 차수 0이 된 노드 큐에 삽입
q.append(i)
for i in result:
print(i, end=" ")
topological_sort()
동작 과정: 스택 (진출 차수)
방문하지 않은 임의의 노드에서 출발한다.
DFS를 수행하며 방문하는 노드를 스택에 담는다.
모든 정점을 방문할 때까지 1번을 반복한다.
모든 정점을 방문했다면 스택에 담긴 정점을 출력한다.
DFS는 깊이 우선 탐색이라는 사실을 떠올려보자.
하나의 노드에서 DFS를 수행하면 결국 리프 노드까지 내려갈 것이다.
리프 노드는 진출 차수가 0이다.
즉, 가장 마지막에 수행되어야 하는 작업이다.
가장 깊은 리프 노드가 스택에 먼저 담기고,
루트 노드가 가장 나중에 스택 최상단에 담길 것이다.
LIFO 형태의 스택을 차례대로 출력하면 위상 정렬의 결과와 같다.
임의의 노드를 선택해도 상관이 없는 이유는,
DFS는 선택한 노드보다 늦게 수행되어야 할 노드(더 깊은 노드)만 방문하는 원리이다.
탐색 중인 그래프가 DAG인지 확인하기 위해 사이클 유무를 판단할 수 있어야 한다.
방문 처리된 노드를 DFS 호출 과정에서 만나면 사이클이 존재한다는 뜻이다.
구현: 스택
v, e = map(int, input().split())
graph = [[] for i in range(v + 1)] # 간선 정보를 담을 리스트
visited = [False] * (v + 1) # 방문 처리
stack = []
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 노드 A에서 B로 이동 가능
def dfs(v):
visited[v] = True
for next in graph[v]:
if not visited[next]:
dfs(next)
stack.append(v)
def stack_topological_sort():
for i in range(1, v + 1):
if not visited[i]:
dfs(i)
while stack:
print(stack.pop(), end=" ")
stack_topological_sort()
위상 정렬 특징
시간 복잡도는 `O(V + E)`이다.
차례대로 모든 노드를 확인하며, 각 노드에서 나가는 간선을 차례대로 제거해야 한다.
위상 정렬은 DAG(Direct Acyclic Grpah, 방향이 있는 비순환 그래프)에 대해서만 수행 가능하다.
# 이해
# 문자열로 된 숫자를 조합해서, 생성 가능한 숫자 중 가장 큰 수 return
# 풀이
# numbers를 문자열의 배열로 변환
# 내림차순 정렬
# 배열 내의 원소를 하나로 합침
# 문제
# 문제의 조건에 따르면 우선순위가 다음과 같아야 함. 3 > 30
# 그러나 일반적인 정렬은 다음과 같이 정렬됨. 30 > 3
# 문제의 의도대로 정렬이 되려면, 3은 33으로 취급해야 함.
def solution(numbers):
str_numbers = list(map(str, numbers))
str_numbers.sort(key=lambda x: x*3, reverse=True)
print(str_numbers)
answer = ''.join(str_numbers)
return str(int(answer))
# 이해
# 주어진 배열을 h를 기준으로 둘로 나눈다.
# 이때 h 이상인 배열의 길이가 h 이상이 된다. h 이하인 배열의 길이가 h 이하가 된다. 이것이 h-index.
# 이분탐색처럼 느껴지기도 한다.
# 그러나 n의 크기가 1000 이하 이므로 O(N ** 2)으로 완전탐색해도 되겠다.
# 풀이
# 배열을 정렬한다.
# 피봇 h를 정한다. 대략 길이의 절반쯤 위치의 인덱스로
# 피봇을 기준으로 큰 값과 작은 값을 계산한다.
# 피봇을 적당히 옮겨서 h의 최댓값을 구한다.
def solution(citations):
citations.sort()
n = len(citations)
h_index = 0
for i, citation in enumerate(citations):
h = min(citation, n - i)
h_index = max(h_index, h)
return h_index
이 문제도 꽤 오래 고민했다.
`h = min(citation, n - i)` 부분이 직관적으로 와닿지 않았다.
h-index의 정의에 따르면,
"논문 중 h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용되었을 때, h의 최대값이 h-index"이다.
이를 효과적으로 계산하기 위해 다음 두 값을 고려하자.
citation: 현재 논문의 인용 횟수
n - i: 현재 논문을 포함해서 그 이상 인용된 논문의 수. (여기서 n은 논문의 총 수, i는 현재 논문의 인덱스(0부터 시작))
예를 들어, 논문이 인용 횟수에 따라 오름차순으로 정렬된 상태에서, 특정 위치 i에서의 논문 인용 횟수가 10회라고 가정하자.
그리고 이 논문이 전체 논문 중에서 상위 15번째에 위치한다면 (n - i = 15), 다음 두 가지를 고려해야 한다.
현재 논문은 10회 인용됨.
현재 논문을 포함하여 15편의 논문이 10회 이상 인용 .
여기서 h-index의 조건을 만족시키기 위해 두 값 중 작은 값을 선택하자.
즉, min(10, 15) = 10이다.
이는 이 논문이 적어도 10번 이상 인용된 10편의 논문 중 하나임을 보장한다.
그러나 만약 이 논문의 인용 횟수가 20회이고, 같은 조건에서 n - i = 15라면, min(20, 15) = 15가 된다.
이는 15편의 논문이 최소 15회 이상 인용되었음을 보여주며, h-index가 될 수 있는 후보이다.
