코딩테스트 낙서장2
~
지난 한 주 의문의 잠수를 타면서 뇌가 깨끗해졌습니다. 그로 인해 주요 개념들을 다시 복습하고자 글을 새로 작성했습니다. 이 글에는 주요 개념만 간단하게 채워나갈 예정입니다.
그리디
- 그리디는 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘으로, 탐욕적으로 문제를 푸는 알고리즘입니다.
# 그리디 알고리즘: 거스름돈
coins = [500, 100, 50, 10]
n = 1260
cnt = 0
for coin in coins:
cnt += n // coin
n %= coin
print(cnt)
구현
- 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정입니다. 세부적으로 보면 완전 탐색은 모든 경우의 수를 전부 다 계산하는 문제 유형이고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형입니다.
'''시뮬레이션'''
# L, R, U, D
dx = [+0, +0, -1, +1]
dy = [-1, +1, +0, +0]
p = {
'L': 0,
'R': 1,
'U': 2,
'D': 3
}
def in_range(x, y):
return 0 <= x < n and 0 <= y < n
n = int(input())
x, y = 0, 0
plans = input().split()
for plan in plans:
nx, ny = x + dx[p[plan]], y + dy[p[plan]]
if in_range(nx, ny):
x, y = nx, ny
print(x, y)
'''완전탐색(Brute Force)'''
H = int(input())
cnt = 0
for h in range(H+1):
for m in range(60):
for s in range(60):
if '3' in str(h)+str(m)+str(s):
cnt += 1
print(cnt)
DFS
- DFS(Depth-First Search)는 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 구현에 스택과 재귀 함수를 사용합니다.
def DFS(graph, n, visited):
visited[n] = 1
print(n, end=' ')
for i in graph[n]:
if not visited[i]:
DFS(graph, i, visited)
graph = [
[1, 2, 7],
[0, 6],
[0, 3, 4],
[2, 4],
[2, 3],
[6],
[1, 5, 7],
[0, 6]
]
visited = [0] * 8
DFS(graph, 0, visited)
BFS
- BFS(Breadth First Search)는 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘입니다. 구현에 큐를 사용합니다.
from collections import deque
def BFS(graph, start, visited):
q = deque()
q.append(start)
visited[start] = 1
while q:
cur = q.popleft()
print(cur, end=' ')
for i in graph[cur]:
if not visited[i]:
q.append(i)
visited[i] = 1
graph = [
[1, 2, 7],
[0, 6],
[0, 3, 4],
[2, 4],
[2, 3],
[6],
[1, 5, 7],
[0, 6]
]
visited = [0] * 8
BFS(graph, 0, visited)
정렬
- 선택 정렬: 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꿔나가는 정렬 방법(N^2)
- 삽입 정렬: 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 정렬 방법(N^2)
- 퀵 정렬: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식의 정렬 방법(N log N)
- 계수 정렬: 특정한 조건이 성립될 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘(N+K)
- 거품 정렬: 서로 인접한 두 원소의 대소를 비교하여 조건에 맞지 않는 것들의 자리를 교환하는 정렬 방법(N^2)
lst = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
# 선택 정렬
def selection_sort(lst):
for i in range(len(lst)):
minidx = i
for j in range(i+1, len(lst)):
if lst[minidx] > lst[j]:
minidx = j
lst[i], lst[minidx] = lst[minidx], lst[i]
# 삽입 정렬
def insertion_sort(lst):
for i in range(len(lst)):
for j in range(i, 0, -1):
if lst[j] < lst[j-1]:
lst[j], lst[j-1] = lst[j-1], lst[j]
else:
break
# 퀵 정렬
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
tail = lst[1:]
lstleft = [x for x in tail if x <= pivot]
lstright = [x for x in tail if pivot < x]
return quick_sort(lstleft) + [pivot] + quick_sort(lstright)
# 계수 정렬
counting = [0] * (max(lst)+1)
def countsort(lst):
for n in lst:
counting[n] += 1
for i in range(len(counting)):
for _ in range(counting[i]):
print(i, end=' ')
# 거품 정렬
def bubble_sort(lst):
for i in range(len(lst)):
for j in range(1, len(lst)-i):
if lst[j-1] > lst[j]:
lst[j-1], lst[j] = lst[j], lst[j-1]
이진 탐색
- 이진 탐색은 O(n)인 순차 탐색보다 효율이 좋은 탐색 기법으로, 정렬되어있는 리스트에 대해 O(log n)의 시간복잡도로 탐색을 할 수 있는 방식입니다.
# 순차 탐색
def sequential_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# 이진 탐색
def binary_search(lst, s, e, target):
if s > e:
return -1
m = (s+e) // 2
if lst[m] == target:
return m
if target < lst[m]:
return binary_search(lst, s, m-1, target)
else:
return binary_search(lst, m+1, e, target)
다이나믹 프로그래밍
- 다이나믹 프로그래밍 기법은 메모리 공간을 조금 더 사용하여 기존 결과를 재사용하는 기법이다. 즉, 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
# DP_fibo_Top-down
dp = [0] * 101
def fibo(n):
if n < 2:
return n
if dp[n] != 0:
return dp[n]
dp[n] = fibo(n-2) + fibo(n-1)
return dp[n]
print(fibo(100))
# DP_fibo_Bottom-up
dp = [0] * 101
dp[1] = 1
for i in range(2, 101):
dp[i] = dp[i-2] + dp[i-1]
print(dp[100])
다익스트라 알고리즘
- 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라는 음수인 가중치를 가지는 간선이 없을 때 사용 가능하다.(그리드 알고리즘의 일종)
# 다익스트라 알고리즘
import heapq, sys
from tkinter import N
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())-1
graph = [[] for _ in range(n)]
dist = [INF] * n
for _ in range(m):
s, e, w = map(int, input().split())
graph[s-1].append((e-1, w))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
dist[start] = 0
while q:
w, s = heapq.heappop(q)
if dist[s] < w:
continue
for e, nw in graph[s]:
weight = w + nw
if weight < dist[e]:
dist[e] = weight
heapq.heappush(q, (weight, e))
dijkstra(start)
for i in range(n):
print("%d: " % i, end='')
if dist[i] == INF:
print("INF")
else:
print(dist[i])
플로이드 워셜 알고리즘
- 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 “모두” 구해야 하는 경우에 사용할 수 있는 알고리즘이다.(다이나믹 프로그래밍 알고리즘의 일종)
# 플로이드 워셜 알고리즘
INF = int(1e9)
n = int(input())
m = int(input())
graph = [
[INF for _ in range(n)]
for _ in range(n)
]
for i in range(n):
graph[i][i] = 0
for _ in range(m):
s, e, w = map(int, input().split())
graph[s-1][e-1] = w
for mid in range(n):
for s in range(n):
for e in range(n):
graph[s][e] = min(graph[s][e], graph[s][mid] + graph[mid][e])
for i in range(n):
for j in range(n):
if graph[i][j] == INF:
print(INF, end=' ')
else:
print(graph[i][j], end=' ')
print()
서로소 집합 알고리즘
- 두 집합이 서로소 관계인 경우 각 집합이 어떤 원소를 공통으로 가지고 있는지 확인할 수 있다. 이를 통해 어떤 노드의 부모 노드(연결된 노드 중 가장 작은 노드)가 같은지를 확인할 수 있다.
# 서로소 집합 알고리즘을 이용한 사이클 판별
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)
for i in range(v):
parent[i] = i
iscycle = False
for i in range(e):
a, b = map(int, input().split())
a-=1
b-=1
if find_parent(parent, a) == find_parent(parent, b):
iscycle = True
break
union_parent(parent, a, b)
if iscycle:
print("CYCLE")
for i in range(v):
print(parent[i], end=' ')
크루스칼 알고리즘
- 최소한의 비용으로 신장 트리를 찾을 때 사용한다.
# 크루스칼 알고리즘
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 = [i for i in range(v)]
edges = []
answer = 0
for _ in range(e):
a, b, w = map(int, input().split())
edges.append((w, a-1, b-1))
# 최소 비용부터, 사이클이 생기지 않게 하여, MST를 만들기 위함
edges.sort()
for edge in edges:
w, s, e = edge
if find_parent(parent, s) != find_parent(parent, e):
union_parent(parent, s, e)
answer += w
print(answer)
위상 정렬(Topology Sort)
- 위상 정렬은 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.
from collections import deque
# 위상 정렬
v, e = map(int, input().split())
indegree = [0] * v
graph = [[] for _ in range(v)]
for _ in range(e):
a, b = map(int, input().split())
graph[a-1].append(b-1)
indegree[b-1] += 1
def topology_sort():
result = []
q = deque()
for i in range(v):
if indegree[i] == 0:
q.append(i)
while q:
cur = q.popleft()
result.append(cur)
for i in graph[cur]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
for i in result:
print(i, end=' ')
topology_sort()