알고리즘 코딩테스트를 위한 개념 정리
그리디
기준에 따라 가장 좋은 것을 선택하는 알고리즘
- '가장 큰 순서대로' 등의 기준을 은연 중에 제공해줌. -> 정렬 알고리즘과 짝을 이룸.
- 문제 풀이를 위한 최소한의 아이디어 떠올리기 -> 정당성 검토 -> 안되면, DP 또는 그래프 알고리즘 고려해보기
구현
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
예 : 완전 탐색, 시뮬레이션
# 상하좌우 이동 문제
n = int(input())
x,y = 1,1
plans = input().split()
dx=[0,0,-1,1]
dy=[-1,1,0,0]
move_types=['L','R','U','D']
for plan in plans:
# 이동 후 좌표 구하기
for i in range(len(move_types)):
if plan == move_types[i]:
nx = x+dx[i]
ny = y+dy[i]
# 공간을 벗어나는 경우 무시
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
# 이동 수행
x, y = nx, ny
print(x,y)# 왕실의 나이트 문제
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0]))-int(ord('a'))+1
# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)]
result = 0
for step in steps:
# 이동하고자 하는 위치 확인
next_row = row + step[0]
next_column = column + step[1]
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)DFS/BFS
스택, 큐, 재귀함수 개념 이용
DFS (깊이 우선 탐색) : 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘.
- 스택, 재귀함수 이용
def dfs(graph, v, visited):
# 현재 노드를 방문 처리
visited[v]=True
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
# 2차원 리스트로 graph 표현
# 노드 개수 + 1 개의 요소
graph = [ [], [2,3,8], [1,7] ]
visited = [False]*3
# dfs 함수 호출
dfs(graph,1,visited)BFS (너비 우선 탐색) : 가까운 노드부터 탐색하는 알고리즘.
- 큐 이용
from collection import deque
def bfs(graph, start, visited):
queue=deque([start])
visited[start]=True
# 큐가 빌 때까지 반복
while queue:
v = queue.popleft()
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
# 2차원 리스트로 graph 표현
# 노드 개수 + 1 개의 요소
graph = [ [], [2,3,8], [1,7] ]
visited = [False]*3
# bfs 함수 호출
bfs(graph,1,visited)cf. 탐색 문제는 그래프 형태로 표현한 후 풀이하자 !
- 연결된 덩어리 파악 => dfs
- 가능한 최소 경로 탐색 => bfs
정렬
- 선택 정렬
- 리스트 첫 요소부터 비교 시작.
- 비교 후, 매번 가장 작은 요소를 선택해서 맨 앞으로 보낸다.
array=[13,2,5,259,1]
for i in range(len(array)):
min_index=i
for j in range(i+1,len(array):
if array[i] > array[j]:
min_index=j
# 스왑핑 !
array[i], array[min_index] = array[min_index], array[i]- 삽입 정렬
- 필요할 때만 위치 변경 -> 데이터가 거의 정렬 되어 있을 때, 효율적.
- 첫 요소는 정렬되어 있다고 판단 -> 두번째 요소부터 시작.
- 오른쪽으로 이동하면서 그 이전 요소들 사이에 해당 요소를 끼워넣음.
array=[13,2,5,259,1]
for i in range(1,len(array)):
# 인덱스 i부터 -1까지 감소하며 반복 !
for j in range(i,0,-1):
if array[j] < array[j-1] :
array[j], array[j-1] = array[j-1], array[j]
else:
# 자신보다 작은 요소를 만나면 그 위치에서 멈춤 !!
break- 퀵 정렬
- 병합 정렬처럼 처리 속도가 빠른 편.
- 리스트의 첫 요소를 '피벗'으로 설정 -> 피벗보다 작은 부분, 큰 부분으로 나누기 위해 요소들을 교환함.
- ( -> <- ) 방향으로 대소 비교
- 이후, 부분 부분으로 나눈 것들도 똑같은 방법으로 정렬하자.
array=[13,2,5,259,1]
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left += 1
while right <= start and array[right] >= array[pivot]:
right -= 1
if left > right:
array[pivot], array[right] = array[right], array[pivot]
else:
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
# end는 인덱스니까 (리스트 길이 -1)으로 지정 !
quick_sort(array,0,len(array)-1)- 계수 정렬
- 데이터 크기 범위가 '정수 형태'로 표현할 수 있을 때만 사용 가능
- 최대 데이터 - 최소 데이터 <= 1,000,000일 때 효과적.
- 모든 범위를 담을 수 있는 크기의 리스트를 선언 !
array=[13,2,5,259,1]
# 초기화 리스트 선언
count=[0]*(len(array)+1)
for i in range(len(array)):
count[array[i]] += 1
for i in range(len(range)):
for j in range(range[i]):
# 띄어쓰기를 구분으로, 등장한 횟수만큼 인덱스 출력 ~!
print(i, end=' ')- 정렬 라이브러리
- 퀵 정렬보다 빠름.
- 문제의 별도의 요구가 없을 경우에 사용하는 방법
array=[13,2,5,259,1]
array_1=[('바나나',2),('사과',5),('당근',3)]
# 1
result = sorted(array)
# 2
array.sort()
# 3
# key를 기준으로 정렬
def setting(data):
return data[1]
result = sorted(array_1, key=setting)이진 탐색
- 요소들이 정렬되어 있을 경우에, 빠르게 데이터 탐색 가능 !!
- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하는 알고리즘.
- 이진 탐색 트리에서도 이용됨.
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,mid+1,end)
else:
return binary_search(array,target,start,mid-1)
result = binary_search(array, target, 0, n-1)
if result == None:
print("존재하지 않는 원소임")
else:
# target이 리스트의 몇 번째에 존재하는 지 ?
print(result-1)- 파라메트릭 서치 유형의 문제가 대표적임.
- 최적화 문제를 결정 문제로 바꾸어 해결 ! (예. 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제)
DP
DP 풀이 문제의 조건
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
3. 완전 탐색으로 했을 때 시간이 매우 오래 걸린다.
DP 풀이 방법
1. 재귀 함수 이용 (탑다운)
2. 반복문 이용 (보텀업) ‼️
메모리제이션 기법 예시.
- DP 탑다운의 경우 -> 리스트에 결과 저장.
- '수열'처럼 연속적이지 않은 값의 경우 -> dict 자료형에 결과 저장.
# 적은 금액부터 큰 금액까지 확인 -> 차례대로 만들 수 있는 최소한의 화폐 개수 찾는 문제.
n,m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input()))
# 보텀업 방식
d = [10001] * (m+1)
d[0] = 0
# ( 만들고자 하는 금액 - 화폐 단위들 )을 각각 계산하여 DP 테이블에 저장.
for i in range(n):
for j in range(array[i], m+1):
if d[j-array[i]] != 10001:
d[j-array[i]]=min(d[j-array[i]]+1, d[j])
if d[m] == 10001:
print(-1)
else:
print(d[m])최단 경로
- 다익스트라 알고리즘
- 특정 노드에서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
- '음의 간선'이 없어야 함
- 그리디 알고리즘에 포함됨
: 해당 노드와 연결되어 있으면서, 방문하지 않은 노드 중
최단 거리가 가장 짧은 노드를 매번 선택 ! -> 최단 거리 갱신 - 힙 자료 구조 (우선순위 큐) 사용 -> (거리, 노드)로 저장. -> 자동으로 정렬됨.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
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())
graph[a].append((b,c))
def dijkstra(start):
q = []
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 + distance[i]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
if distance[i] == INF:
print("무한")
else:
print(distance[i]) - 플로이드 워셜 알고리즘
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
- DP 알고리즘에 포함됨.
- 3중 반복문으로 'A->B로 가는 최소 비용'과 'A->K->B로 가는 비용'을 비교 !!
- 노드의 개수가 적을 때 사용 가능.
INF = int(1e9)
n=int(input())
m=int(input())
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 = 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][k]+graph[k][b], graph[a][b])
# 수행된 결과 출력
for a in range(1,n+1):
for b in range(1,n+1):
if graph[a][b] == INF:
print("무한")
else:
print(graph[a][b], end=" ")
print()그래프 이론
- 트리를 이용해 서로소 집합 구하는 알고리즘
- union 연산을 반복 수행 -> 노드들의 연결성 파악 -> 서로소 집합 구하기
- union 연산 : 각각 루트 노드 찾기 -> 번호가 큰 노드가 작은 노드를 가리키도록 연결
- '경로 압축 기법'을 사용하여 루트 노드를 찾는 과정을 최적화함.
def find_parent(parent,x):
# if parent[x] != x:
# return find_parent(parent,parent[x])
# return 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)
# parent 테이블에서 자기 자신으로 초기화
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),end=" ")
print()
# 부모 테이블 내용 출력
for i in range(1,v+1):
print(parent[i], end=" ")- 무방향 그래프 내에서 사이클을 판별할 때 사용됨.
# 부모노드를 자기 자신으로 초기화하는 것까지 동일.
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("사이클 발생하지 않음")- 최소한의 비용으로 신장 트리를 찾는 알고리즘
- 신장 트리 : 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
- 크루스칼 알고리즘 ! : 모든 간선에 대하여 정렬 -> 가장 거리가 짧은 간선부터 집합에 포함시키기 (사이클이 발생하지 않는 것만 !!)
- 최소 신장 트리에 포함되는 간선의 비용 합 = 총 비용
# 부모노드를 자기 자신으로 초기화하는 것까지 동일.
edges = [] # 모든 간선을 담을 변수
result = [] # 총 비용을 담을 변수
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)- 위상 정렬을 사용하여 방향 그래프를 순서대로 나열하는 알고리즘
- 진입 차수 : 특정한 노드로 '들어오는' 간선의 개수
- 위상 정렬 알고리즘 : 진입 차수가 0인 노드를 큐에 삽입 -> 큐가 빌 때까지, 꺼낸 노드에서 출발하는 간선을 그래프에서 제거 + 새롭게 진입차수가 0이 된 노드를 큐에 삽입
- 모든 원소를 방문하기 전에 큐가 빈다 ? = 사이클 발생 !!!!!
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로 이동 가능 !!!!!
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = []
q=deque()
for i in range(1,v+1):
if indegree == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 모든 노드들의 진입차수 -1
for i in graph[now]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
# 위상 정렬 결과 출력
for i in result:
print(i, end=" ")
topology_sort()
냥