1. bisect
(1) 이진탐색 라이브러리 bisect
- bisect_left(array,x) : 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 왼쪽 인덱스를 반환
- bisect_right(array,x) : 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 오른쪽 인덱스를 반환
from bisect import bisect_left, bisect_right
array = [1,2,4,4,8]
x = 4
print(bisect_left(array,x))
print(bisect_right(array,x))2
4
(2) 값이 특정 범위에 속하는 데이터 개수 구하기
# 값이 [min_value, max_value]인 데이터의 개수를 반환하는 함수
def count_by_range(array, min_value, max_value):
right_index = bisect_right(array, max_value)
left_index = bisect_left(array, min_value)
return right_index - left_index
array = [1,2,3,3,3,3,4,4,8,9]
print(count_by_range(array,4,4))
print(count_by_range(array,-1,3))2
6
2. 파라메트릭서치(Parametric Search)
- 파라메트릭 서치란, 최적화문제를 결정하는 문제로 바꾸어 해결하는 기법
- 이진탐색을 이용하여 해결 가능
(1) 나무 자르기
-
문제설명
상근이는 나무 M미터가 필요하다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기에 높이 H를 지정하면, 톱날이 땅으로부터 H미터 위로 올라간다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다. 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오. -
입력조건
- 첫째줄에 나무의 개수 N(1≤N≤1,000,000), 필요한 나무의 길이 M(1≤M≤2,00,000,000)이 주어진다.
- 둘째줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
- 예시
4 7
20 15 10 17
- 출력조건 : 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다. (예시 : 15)
# 나무의 개수(N)와 필요한 나무의 최소 길이(M)을 입력
n, m = list(map(int, input().split()))
# 각 나무의 개별 높이 정보를 입력
array = list(map(int, input().split()))
# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)
# 이진 탐색 수행 (반복적)
result = 0
while(start <= end):
total = 0
mid = (start + end) // 2
for x in array:
# 잘랐을 때의 나무의 길이 계산
if x > mid:
total += x - mid
# 나무의 길이가 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
if total < m:
end = mid - 1
# 나무의 길이가 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
else:
result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1
# 정답 출력
print(result)15
(2) 랜선 자르기
-
문제설명
박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오. -
입력조건
- 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K(1≤K≤10,000), 그리고 필요한 랜선의 개수 N(1≤N≤1,000,000)이 입력된다. 항상 K ≤ N
- 둘째 줄부터 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231−1 보다 작거나 같은 자연수이다.
- 예시
4 11
802
743
457
539
- N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다. (예시 : 200)
# 데이터 입력받기
k, n = 4, 11
lanes = [802, 743, 457, 539]# 알고리즘 구현
# 랜선의 개수를 구하는 함수 (인자는 길이)
# 길이가 주어졌을때 몇개의 랜선을 만드는지 구하는 함수
def count_lanes(length):
count = 0
for lane in lanes:
count += lane // length
return count
# 이진 탐색을 위한 값 초기화
low, high = 1, max(lanes)
# 결과값 초기화
result = 0
# 이진탐색
while low <= high:
mid = (low + high) // 2
if count_lanes(mid) >= n: # n개 이상의 랜선을 만들수 있으면
result = mid # 가능한 길이 중 가장 큰 값 기록
low = mid + 1 # 더 길이를 시도하도록 (오른쪽 탐색)
else:
high = mid - 1 # 길이를 줄여서 다시 시도 (왼쪽 탐색)
# 결과 출력
print(result)200
3. 다이나믹 프로그래밍 (Dynamic Programming)
- 메모리를 적절히 사용하여 수행 시간 비효율성을 비약적으로 향상시키는 방법 (동적 계획법)
- 이미 계산된 결과(작은문제)는 별도의 메모리영역에 저장하여 다시 계산하지 않도록 함
- Top-Down, Bottom-Up 방식이 있음
- 다음 조건을 만족할 때 사용 가능
- 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 갑을 모아서 큰 문제를 해결할 수 있다.
- 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복으로 해결해야 한다.
(1) 예시 : 피보나치 함수(Fibonacci Function)
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(6))(2) 메모이제이션(Memoization)
- 한 번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함
- 다이나믹 프로그래밍에 국한된 개념은 아니며, 한번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그램을 위해 활용하지 않을 수도 있음
## 피보나치 함수 (탑다운(메모이제이션))
# 한 번 계산된 결과를 메모이제이션(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]
print(fibo(99))(3) Top-Down vs. Bottom-Up
- 탑다운(Top-Down)은 큰 문제를 해결하기 위해 작은 문제를 호출하는 것으로 메모이제이션이 사용됨
- 바텀업(Bottom-Up)은 작은 문제부터 차근차근 답을 도출
- 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식
- 결과 저장용 리스트를 DP테이블이라고 함
## 피보나치 함수 (바텀업)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 1,2의 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수를 반복문으로 구현 (바텀업)
for i in range(3, n + 1):
d[i] = d[i-1] + d[i-2]
print(d[99])(4) 1로 만들기
- 문제설명
- 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
- 입력조건 : 첫째 줄에 정수 N(1≤N≤1,000,000)이 주어진다. (예시: 10)
- 출력조건 : 연산을 하는 횟수의 최솟값을 출력한다. (예시 : 3)
f10
f9 f15
f3 f8 f4
f1 f2# N 입력 받기
n = 10
# 코드 구현
dp = [0] * 1000001 # DP테이블 (배열) 생성
# DP 프로그래밍 (바텀업)
# dp 초기값 세팅 << 최적의 해만 저장
dp[1] = 1
dp[2] = 1
dp[3] = 1
# 모든 n값에 대하여 값 저장
for i in range(4, n+1):
# 1을 빼는 경우
dp[i] = dp[i-1] + 1
# 2를 나누는 경우
if i % 2 == 0 :
dp[i] = min(dp[i], dp[i//2] + 1)
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
# 결과 출력
print(dp[n])3
def min_operations_to_one(n):
dp = [0] * (n + 1) # dp[i]는 i를 1로 만드는 최소 연산 횟수를 저장
for i in range(2, n + 1):
dp[i] = dp[i - 1] + 1 # 1을 빼는 연산
if i % 2 == 0:
dp[i] = min(dp[i], dp[i // 2] + 1) # 2로 나누는 연산
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1) # 3으로 나누는 연산
return dp[n]
min_operations_to_one(10)3
4. 그래프
- 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현
- 정점(노드, Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조
- |V| : 정점의 개수
- |E| : 그래프에 포함된 간선의 개수
- |V|개의 정점을 가지는 그래프는 최대 |V|(|V| -1)/2 간선을 가질 수 있음 - 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N관계를 가지는 원소들을 표현하기에
(1) 그래프 유형
- 무향 그래프 : 방향이 없는 그래프 (예: 친구관계, 양방향도로)
- 유향 그래프 : 방향이 있는 그래프 (예: 팔로우)
- 가중치 그래프 : 간선들에 가중치가 있는 그래프 (예: 비행기(금액))
- 사이클 없는 방향 그래프 (예: 트리)
- 완전그래프 vs. 부분그래프
- 완전그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
- 부분그래프 : 일부 정점이나 간선을 제외한 그래프
(2) 주요 용어
- 인접
- 두개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 함
- 완전그래프에 속한 임의의 두 정점들은 모두 인접 - 경로
- 간선들을 순서대로 나열한 것
- 단순경로 : 경로 중 한 정점을 최대한 한번 지나는 경로
- 사이클 : 시작한 정점에서 끝나는 경로
(3) 그래프 표현
- 간선의 정보를 저장하는 방식
- 인접 행렬
- |V| x |V|크기의 2차원 배열을 이용해서 간선정보를 저장
- 연결이 안되어 있다는 정보도 함께 저장
- 진입은 행, 진출을 열로 저장 - 인접 리스트
- 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
- 2차원 배열, 딕셔너리, 연결리스트로 표현 가능
- 연결된 정보만 저장 - 간선의 배열
- 간선(시작정점, 끝정점)을 배열에 연속적으로 저장
5. 최단 경로 알고리즘
- 가장 짧은 경로를 찾는 알고리즘
- 다양한 문제 상황
- 한 지점에서 다른 한점까지의 최단 경로
- 한 지점에서 다른 모든 지점까지의 최단 경로
- 모든 지점에서 다른 모든 지점까지의 최단 경로 - 다익스트라, 플로이드워셜, 벨만포드 등이 있음
(1) 다익스트라 최단경로알고리즘 (Dijkstra)
- 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
- 음의 간선(간선의 값이 0보다 작은값)이 없을 때 활용 가능
- 길은 음의 간선이 표현되지 않으므로 GPS의 기본 알고리즘으로 사용되기도 함 - 그리디 알고리즘으로 분류됨
- 매상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 - 동작과정
1. 출발 노드를 설정
2. 최단거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 업데이트
5. 3,4번을 반복
- 최단거리테이블은 각 노드에 대한 현재까지의 최단거리 정보를 가지고 있음
- 더 짧은 경로를 찾으면 해당 경로로 갱신 - 시간복잡도 : O(N2)
- 총 O(N)에 걸쳐 최단 거리가 가장 짧은 노드를 매번 탐색하고 확인하기 때문
# 노드의 개수, 간선의 개수를 입력받기
n, m = 6, 11
# 시작 노드 번호를 입력받기
start = 1
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
abc = [[1, 2, 2], [1, 3, 5], [1, 4, 1], [2, 3, 3],
[2, 4, 2], [3, 2, 3], [3, 6, 5], [4, 3, 3],
[4, 5, 1], [5, 3, 1], [5, 6, 2]]## 다익스트라 알고리즘
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 a, b, c in abc:
# 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])0
2
3
1
2
4
(2) 플로이드 워셜 알고리즘
- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
- 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행
- 매단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾는 과정 불필요 - 2차원테이블에 최단 거리 정보를 저장
- 다이나믹 프로그래밍 유형에 속함
- 동작과정
- 각 단계마다 특정한 노드 k를 거쳐 가능 경우를 확인
- a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사
- Dab=min(Dab,Dak+Dkb)
- 모든 노드 k에 대하여 최단거리테이블을 업데이트 - 시간복잡도 : O(N3)
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()4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
(3) 케빈 베이컨 6단계 법칙
-
문제설명
케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다. 케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다. 오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. -
입력조건
- 첫째 줄에 유저의 수 N(2≤N≤100)과 친구 관계의 수 M (1≤M≤5,000)이 주어진다.
- 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.
- 예시
5 5
1 3
1 4
4 5
4 3
3 2
3.출력조건 : 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다. (예시 : 3)
# 데이터 입력받기
n,m = 5,5
friends = [(1,3), (1,4), (4,5), (4,3), (3,2)]
# 필요한 자료 초기화
inf = int(1e9)
graph = [[inf] *(n+1) for _ in range(n+1)]
# 친구관계를 나타내는 정보 업데이트 (친구라면 1)
for a,b in friends:
graph[a][b] = 1
graph[b][a] = 1
# 자기자신의 경우는 0
for a in range(1, n+1):
for b in range(1, n+1):
if a==b:
graph[a][b] = 0
# 알고리즘 구현
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 = 0
min_value = n*m
for a in range(1, n+1):
links = [x for x in graph[a] if x!=inf]
if sum(links) < min_value:
min_value = sum(links)
result = a
print(result)3
hyeeun-techlog