이것이 취업을 위한 코딩 테스트다 with 파이썬
이것이 취업을 위한 코딩 테스트다 with 파이썬의 내용
이진 탐색
순차 탐색
순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점 (그만큼 느리겠지?)
동작과정은 잘 정리된 블로그가 많으니 참고, 순차 탐색의 경우 코드만 보아도 이해할 수 있지 않을까
# 책의 코드는 자세하고 길게 설명해 아래의 코드로 축약
# array내에서 target의 인덱스를 반환하고 찾지못한다면 -1 반환
array = []
target = ""
def sequential_search(array, target):
for i in range(len(array)):
if array[i] == target:
return i # 인덱스 위치 반환
return -1 # 찾지 못한다면 -1 반환
index = sequential_search(array, target)데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N)
이진 탐색
이진 탐색은 배열의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
찾으려는 데이터와 중간 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
시간 복잡도 O(logN) 정확히는 O(log2N)
동작과정은 잘 정리된 블로그가 많으니 참고, 이진 탐색의 경우도 코드만 보아도 이해할 수 있지 않을까
이진 탐색을 구현하는 방법에는 재귀 함수를 이용하는 방법, 반복문을 이용하는 방법이 있다.
재귀 함수를 이용하는 방법
array = []
target = ""
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
return binary_search(array, target, 0, mid-1)
# 중간점의 값보다 찾는 값이 큰 경우 오른쪽 확인
else:
return binary_search(array, target, mid+1, end)
result = binary_search(array, target, 0, len(array)-1)
if result == None:
print("원소 존재하지 않음")
else:
print(result) # index 출력mid = (start + end) //** 2는 중간점을 의미한다. 2로 나눈 몫만 구하기 위해 몫 연산자(//)를 사용
반복문을 이용하는 방법
array = []
target = ""
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None # 못 찾은 경우
result = binary_search(array, target, 0, len(array)-1)
if result == None:
print("원소 존재하지 않음")
else:
print(result) # index 출력코딩 테스트에서의 이진 탐색
코드가 짧으니 이진 탐색을 처음 접한 사람이라면, 여러 차례 코드를 입력하며 자연스럽게 외워보자
이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니 가급적 외우길 권함
이진 탐색의 원리는 다른 알고리즘에서도 폭넓게 적용되는 원리와 유사하기 때문에 매우 중요
코딩 테스트의 이진 탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많음.
따라서 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근해보길 권한다.
처리해야 할 데이터의 개수나 값이 1,000만 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다는 점을 기억
이진 탐색 트리
이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
이진 탐색 트리는 부모 노드보다 왼쪽 자식 노드가 작다, 부모 노드보다 오른쪽 자식 노드가 크다
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮으므로, 책에서는 이진 탐색 트리를 구현하는 방법은 소개하지 않음
동작과정은 잘 정리된 블로그가 많으니 참고
빠르게 입력받기
입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다.
자세한 내용 여기의 빠르게 입력받기 참고
실전 문제
부품 찾기
앞에서 배운 이진 탐색으로 문제를 풀었다
# 가진 부품의 개수
n = int(input())
# 가진 부품들의 번호 리스트
array = list(map(int, input().split()))
# 부품 확인 요청 개수
m = int(input())
# 부품 확인 요청한 번호 리스트
purchase_list = list(map(int, input().split()))
# 이진 탐색을 하기전 정렬
array.sort()
# 반복문으로 작성한 이진 탐색
def binary_search(array, purchase, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == purchase:
return "yes"
elif array[mid] > purchase:
end = mid - 1
else:
start = mid + 1
return "no"
# 부품 확인 요청한 번호 리스트만큼 반복
for i in purchase_list:
print(binary_search(array, i, 0, len(array)-1), end=' ')두 번째 풀이로 계수 정렬이 있길래 책의 코드를 보지 않고 풀어보았다.
# 가진 부품의 개수
n = int(input())
# 가진 부품들의 번호 리스트
array = list(map(int, input().split()))
# 부품 확인 요청 개수
m = int(input())
# 부품 확인 요청한 번호 리스트
purchase_list = list(map(int, input().split()))
# 최대 부품 번호 + 1만큼의 리스트 생성
count = [0] * (max(array) + 1) # (max(array) + 1)
# 부품 번호가 있다면 1을 넣음
for i in array:
count[i] = 1
# 부품 확인 요청한 만큼 반복
for i in purchase_list:
if count[i] == 1: # 부품이 있다면 1이 들어가있다.
print("yes", end=' ')
else:
print("no", end=' ')책의 계수 정렬 코드
# 가진 부품의 개수
n = int(input())
array = [0] * 1000000
for i in input().split()
array[int(i)] = 1
# 부품 확인 요청 개수
m = int(input())
x = list(map(int, input().split()))
for i in x:
if array[i] == 1:
print("yes", end=' ')
else:
print("no", end=' ') 책의 set을 이용한 풀이
# 가진 부품의 개수
n = int(input())
array = set(map(int, input().split()))
m = int(input())
x = list(map(int, input().split()))
for i in x:
if i in array:
print('yes', end=' ')
else:
print('no', end=' ')
set을 생각 못하고 있었다.
떡볶이 떡 만들기
내 틀린 코드
# 떡의 개수 n, 요청한 떡의 길이 M
n, m = list(map(int, input().split()))
array = list(map(int, input().split()))
array.sort()
minimum = 0
maximum = max(array)
result = 0
while minimum <= maximum:
mid = (minimum+maximum) // 2
sum = 0
for i in array:
if i > mid:
sum += (i - mid)
if sum == m:
result = mid
elif sum < m:
maximum = mid - 1
else:
minimum = mid + 1
print(result)정답 코드
# 떡의 개수 n, 요청한 떡의 길이 M
n, m = list(map(int, input().split()))
array = list(map(int, input().split()))
array.sort()
minimum = 0
maximum = max(array)
result = 0
while minimum <= maximum:
mid = (minimum+maximum) // 2
sum = 0
for i in array:
if i > mid:
sum += (i - mid)
if sum < m:
maximum = mid - 1
else:
result = mid
minimum = mid + 1
print(result)무한 루프를 도는 원인을 못찾아서 확인해보니 최대한 덜 잘랐을 때의 가정을 못넣었다
난이도 2의 문제를 거의 다 풀었는데 아쉽지만 난이도 2가 풀만하다는 자신감이 붙은 문제
다이나믹 프로그래밍
다이나믹 프로그래밍을 설명하기 앞서 기존의 알고리즘으로 해결하기 어려운 문제 중 피보나치 수열을 살펴보자
피보나치 수열을 재귀함수를 사용하여 작성한 코드
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)이렇게 작성하면 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나는 문제가 있다.
O(2^n)의 지수 시간이 소요된다
이러한 문제를 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.
항상 다이나믹 프로그래밍을 사용할 수는 없으며 다음 조건을 만족해야 한다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모지제이션(Memoization: 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 결과를 그대로 가져오는 기법)을 사용하여 피보나치 수열을 해결해보자
# 한 번 계산된 결과를 Memoization하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)
- 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여
탑다운(Top-Down) 방식이라고 한다.하향식 - 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여
바텀업(bottom-up) 방식이라고 한다.상향식
반복적 피보나치 수열 소스코드
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수 반복문으로 구현, 바텀업 다이나믹 프로그래밍
for i in range(3, n+1):
d[i] = d[i - 1] + d[i - 2]다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다
- Bottom-Up 방식에서 사용되는 결과 저장용 리스트는
DP 테이블이라고 부른다. - Memoization은 탑다운 방식에 국한되어 사용되는 표현
코딩 테스트에서의 다이나믹 프로그래밍 문제는 대체로 간단하게 출제되므로, 책에서 다루는 문제만 바르게 습득해도 코딩 테스트에서 다이나믹 프로그래밍 문제를 풀기에는 큰 어려움이 없을것
특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.
시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문에 가능하다면 재귀 함수를 이용하는 Top-Down 방식보다는 Bottom-Up 방식으로 구현하는 것을 권장한다.
실전문제
1로 만들기
30분동안 고민해도 안풀려서 책의 코드를 봤다
x = int(input())
d = [0] * 30001
for i in range(2, x+1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i-1] + 1
# 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 2] + 1)
print(d[x])개미 전사
푸는데 성공했다..!
# 식량 창고 개수 n
n = int(input())
# 각 식량창고에 저장된 식량의 개수
array = list(map(int, input().split()))
# DP 테이블
d = [0] * 100
# 2 번째 식량창고까지는 최대 식량이 고정
d[0] = array[0]
d[1] = array[1]
# 3번째 식량창고부터 다이나믹 프로그래밍을 적용하여 1칸 앞의 식량을 얻을지 2칸 앞의 식량을 얻을지 결정
for i in range(2, n):
d[i] = max(d[i-1], d[i-2]+array[i])
print(d[n-1])책과 똑같은 풀이가 나왔다.
바닥 공사
다음에 다시 풀어봐야겠다
효율적인 화폐 구성
테스트로 2 15, 3, 4를 입력했었는데 4가 맞는데 5가 정답인줄 알고 왜 4가 나올까라는 고민을 10분동안 했다...
내가 푼 코드
# 화폐의 종류 n, 채워야하는 돈 m
n, m = list(map(int, input().split()))
# 화폐 배열 생성
array = []
# 화폐 배열 입력
for i in range(n):
array.append(int(input()))
array.sort() # 화폐 배열 정렬
# DP 테이블 생성
d = [100000] * (m+1)
d[0] = 0 # 0원은 0
# 바텀업 다이나믹 프로그래밍
for i in range(array[0], m+1):
for j in array:
if (i - j) >= 0: # 현재 값 - 화폐가 0원 이상이라면
d[i] = min(d[i-j]+1, d[i])
if d[m] == 100000: # 초기값이라면 가진 화폐들로 만들 수 없는 수
print(-1)
else:
print(d[m])책의 코드
# 화폐의 종류 n, 채워야하는 돈 m
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input()))
array.sort() # 화폐 배열 정렬
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m+1)
d[0] = 0 # 0원은 0
# 바텀업 다이나믹 프로그래밍
for i in range(n):
for j in range(array[i], m+1):
if d[j - array[i]] != 10001: # (i -k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
if d[m] == 10001: # 초기값이라면 가진 화폐들로 만들 수 없는 수
print(-1)
else:
print(d[m])최단 경로
-
최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘
-
최단 경로 알고리즘은 보통 그래프로 표현
-
실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 경로를 출력하도록 요구하는 문제가 많이 출제
-
학부 수준에서 사용하는 최단 거리 알고리즘은
다익스트라,플로이드 워셜,벨만 포드가 있지만 이 책에서는다익스트라와플로이트 워셜만 다룬다. -
앞서 공부한
그리디 알고리즘과다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다.
다익스트라 최단 경로 알고리즘
-
다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 -
0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작
-
다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류
알고리즘의 원리를 간략히 설명하면 다음과 같다
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 3번과 4번 과정을 반복
한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는다.
다익스트라 알고리즘을 구현하는 방법
- 구현하기 쉽지만 느리게 동작하는 코드
- 구현하기 조금 더 까다롭지만 빠르게 동작하는 코드
시험을 준비한다면 방법 2를 정확히 이해하고 구현할 수 있을 때까지 연습해야 한다.
동작 과정은 잘 정리된 블로그가 많으니 참고
방법 1. 간단한 다익스트라 알고리즘
-
O(V2)의 시간 복잡도를 가진다. V는 노드의 개수
-
단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.
-
코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 일반적으로 이 코드로 풀 수 있을것.
-
데이터의 개수가 10,000개를 넘어간다면 '개선된 다익스트라 알고리즘' 이용
간단한 다익스트라 알고리즘 소스코드
# 입력되는 데이터의 수가 많다는 가정하에 파이썬 내장 함수인 sys.stdin.readline() 사용
# 모든 리스트는 (노드의 개수 + 1)의 크기로 할당하여,
# 노드의 번호를 인덱스로 하여 바로 리스트에 접근할 수 있도록 했다.
# 그래프를 표현해야 할 때 많이 사용하는 일반적인 코드 작성법이므로 기억해두자.
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트 만들기
visited = [False] * (n+1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
min_value = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1, n+1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
# 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
for i in range(n-1):
# 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
now = get_smallest_node()
visited[now] = True
# 현재 노드와 연결된 다른 노드들 확인
for j in graph[now]:
cost = distance[now] + j[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[j[0]]:
distance[j[0]] = cost
# 다익스트라 알고리즘 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])방법 2. 개선된 다익스트라 알고리즘
- 최악의 경우에도 O(ElogV)를 보장한다. V는 노드의 개수, E는 간선의 개수
- 힙(Heap)을 사용한다.
우선순위 큐
우선순위가 가장 높은 데이터를 가장 먼저 삭제
일반적으로
PriorityQueue보다는heapq가 더 빠르게 동작하기 때문에heapq사용우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 결정한다. ex) (가치, 물건)으로 구성된다면 가치가 우선순위 값
파이썬의 우선순위 큐 라이브러리는 최소 힙에 기반
최소 힙을 최대 힙으로 사용하는 방법 숙지(넣을 때 -, 빼고 -)
heapq는 데이터의 개수가 N개일 때, 하나의 데이터를 삽입, 삭제할 때의 시간 복잡도는 O(logN)이다
동작과정은 잘 정리된 블로그가 많으니 참고
개선된 다익스트라 알고리즘 소스코드
# 최단 거리가 가장 짧은 노드를 선택하는 과정을 다익스트라 최단 경로 함수 안에서
# 우선순위 큐를 이용하는 방식으로 대체하기 때문에
# get_smallest_node() 함수를 작성할 필요가 없다.
import heapq
import sys
input = sys.stdin.readline()
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
# 도달할 수 없는 경우, 무한(INFINITY) 출력
if distance[i] == INF:
print("INFINITY")
else:
distance[i]플로이드 워셜 알고리즘
다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용할 수 있는 알고리즘플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘플로이드 워셜 알고리즘은다익스트라와 마찬가지로 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다- 단계마다 O(N2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 총시간 복잡도는 O(N3)이다. (예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다.)
- 2차원 리스트에 '최단 거리' 정보 저장
- 다이나믹 프로그래밍
- 점화식은 다음과 같다 Dab = min(Dab, Dak + Dkb)
구체적인 동작과정은 잘 정리된 블로그가 많으니 참고
플로이드 워셜 알고리즘 소스코드
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용은 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 수행된 결과를 출력
for a in range(1, n+1):
for b in range(1, n+1):
# 도달할 수 없는 경우 무한(INFINITY)라고 출력
if graph[a][b] == INF:
print("INFINITY", end=' ')
else:
print(graph[a][b], end=' ')
print()실전문제
미래도시
# 회사 개수 n, 경로 개수 m
n, m = map(int, input().split())
# 무한
INF = int(1e9)
# 무한으로 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
for i in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
# 판매할 회사 x, 소개팅 k
x, k = map(int, input().split())
for k in range(1, n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
result = graph[1][k] + graph[k][x]
if result >= INF:
print(-1)
else:
print(result)그래프 이론
지금까지 다루지 않았던 그래프 알고리즘을 다룬다
크루스칼 알고리즘: 그리디 알고리즘으로 분류
위상 정렬 알고리즘: 큐 혹은 스택을 활용해서 구현
- 코딩 테스트에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘
- 알고리즘 문제를 접했을 때 '서로 다른 개체가 연결되어 있다'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다.
- 최단 경로를 찾아야 하는 문제가 출제되었을 때, 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 이용할 수 있다.
서로소 집합
수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미
서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조- union-find 자료구조라고 불리기도 한다.
union과find2개의 연산으로 조작할 수 있다.- 트리을 이용해서 집합 표현
union연산을 효과적으로 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 한다.- 시간복잡도 : O(V + M(1 + Mlog2V))
union: 하나의 집합으로 합치는 연산
find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
기본적인 알고리즘
1.union 연산을 확인하여, 서로 연결된 두 노드 A, B확인
2.A와 B의 루트 노드 A', B'에 대하여 더 작은 루트 노드를 부모 노드로 설정
3.과정 반복
동작 과정은 잘 정리된 블로그가 많으니 참고
기본적인 서로소 집합 알고리즘 소스코드
# 특정 원소가 속한 집합을 찾기
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
# 노드의 개수와 간선(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
# 사이클이 발생하지 않았다면 union 수행
else:
union_parent(parent, a, b)
if cycle:
print("cycle")
else:
print("not cycle")크루스칼 알고리즘
크루스칼 알고리즘: 대표적인 최소 신장 트리 알고리즘
신장 트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘
- 그리디 알고리즘으로 분류
- 모든 간선에 대하여 정렬후에 가장 거리가 짧은 간선부터 집합에 포함시키나 사이클을 발생시키는 간선의 경우, 집합에 포함시키지 않는다.
- 최종적으로 신장 트리에 포함되는 간선의 개수 = 노드의 개수 - 1
- 시간복잡도: 간선의 개수가 E개일 때, O(ElogE)
알고리즘의 동작 과정은 잘 정리된 블로그가 많으니 참고
크루스칼 알고리즘 소스코드
# 특정 원소가 속한 집합을 찾기
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
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 모든 간선에 대한 정보를 입력받기
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)위상 정렬
위상 정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'
진입차수: 특정한 노드로 들어오는 간선의 개수
위상 정렬 알고리즘
1. 진입차수가 0인 노드를 큐에 넣는다
2. 큐가 빌 때 까지 다음 과정 반복
3. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
4. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.큐에서 원소가 V번 추출되기 전에 큐가 비면 사이클이 존재
- 위상 정렬의 시간복잡도는 O(V + E)
기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많으므로 이 페이지에선 사이클이 발생하는 경우는 고려하지 않는다.
위상 정렬 소스코드
from collections import deque
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 그래프 초기화
graph = [[] for i in range(v+1)]
# 방향 그래프의 모든 간선 정보 입력받기
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 정점 A에서 정점 B로 이동가능
# 진입차수를 1 증가
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = [] # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
for i in result:
print(i, end=' ')
topology_sort()실전문제
팀 결성
내 풀이
# 특정 학생이 속한 팀을 찾기
def find_team(team, x):
# 루트가 아니라면 찾을 때까지 재귀 호출
if team[x] != x:
team[x] = find_team(team, team[x])
return team[x]
# 두 학생이 속한 팀을 합치기
def union_team(team, a, b):
a = find_team(team, a)
b = find_team(team, b)
if a < b:
team[b] = a
else:
team[a] = b
#n , m: 입력으로 주어지는 연산의 개수
n ,m = map(int, input().split())
# 부모 테이블 초기화
team = [0] * (n+1)
for i in range(n+1):
team[i] = i
# m개의 연산 입력
for i in range(m):
k, a, b = map(int, input().split())
if k == 0: # 팀 합치기
union_team(team, a, b)
else:
if find_team(team, a) == find_team(team, b):
print("YES")
else:
print("NO")도시 분할 계획
마을을 2개로 분리를 하는 방법이 도무지 떠오르지 않아서 책의 코드를 참고했다
# 집의 개수 n, 길의 개수 m
n, m = map(int, input().split())
# 특정 원소가 속한 집합을 찾기
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
# 부모 테이블
parent = [0] * (n+1)
for i in range(n+1):
parent[i] = i
edges = [] # 모든 간선을 담을 리스트
result = 0 # 최종 비용을 담을 변수
for i in range(m):
a, b, cost = map(int, input().split())
# 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.append((cost, a, b))
# 간선을 비용순으로 정렬
edges.sort()
last = 0
# 간선을 하나씩 확인하며
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
last = cost
print(result - last)커리큘럼
책의 코드를 참고하였다
from collections import deque
import copy
# 듣고자 하는 강의의 수 n
n = int(input())
# 모든 강의에 대한 진입 차수 0으로
indegree = [0] * (n+1)
# 각 노드에 연결된 간선 정보를 담기 위한 그래프 초기화
graph = [[] for i in range(n+1)]
time = [0] * (n+1) # 강의 시간 1~n
for i in range(1, n+1):
# 강의 시간 time ,강의를 듣기 위해 들어야하는 강의 번호
input_list = list(map(int, input().split()))
time[i] = input_list[0]
class_num = input_list[1:]
for c in class_num:
if c == -1:
break
graph[c].append(i)
indegree[i] += 1
def topology_sort():
result = copy.deepcopy(time) # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
for i in range(1, n+1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
for i in graph[now]:
result[i] = max(result[i], result[now]+time[i])
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
for i in range(1, n+1):
print(result[i])
topology_sort()