코딩테스트 알고리즘

이진 탐색

정렬된 배열 내에서 중간점 위치 데이터와 비교하며 반복적으로 절반씩 좁혀가며 찾는다
O(log n)

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        if array[mid] == target:
            return mid
        elif target < array[mid]:
            end = mid - 1
        else:
            start = mid + 1
    
    return -1

주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘
최적화 문제(최댓값 x = ?) -> 결정문제(x일 경우 최댓값?)로 바꾸어 풀 수 있다.

  • 범위의 중간값과 조건을 비교하며 범위를 수정해나간다
  • 이진 탐색과 차이점은 값 비교 -> 조건 비교, 반환값 (mid, -1 -> result (현재까지의 최적값))이 다르다는 점.
# 최적화문제: 24시간을 7시간마다 배고파지는 사람이 최소 몇끼니를 먹어야 배부르게 지낼수있는가?
# 결정문제: 7시간마다 배고파지는 사람이 x끼니를 먹으면 24시간을 배부르게 지낼 수 있다.
def parametricSearch(start, end) {
    mid = (start + end) / 2
    currentValue = mid
    while (start <= end):
        if (24 / mid) > 7:   
            start = mid + 0.1
        elif (24 / mid) < 7:
            end = mid - 0.1
        else
            return currentValue
    return mid
}

파라메트릭 서치 블로그

다이나믹 프로그래밍

큰 문제를 작은 문제로 나눌 수 있는 경우 동일문제를 중복되지 않게 계산하는 방법
Bottom up(반복문), Top down(재귀) 방식
메모이제이션: 계산된 결과들을 메모하는 기법 (캐싱)
O(n)

d = [0] * 100
def pibo(x):
    d[1] = 1
    d[2] = 1
    
    for i in range(3, x+1):
        d[i] = d[i-1] + d[i-2]

다익스트라

시작 노드로부터 각 노드까지의 최단거리 알고리즘 (음의 간선이 없는 경우)
반복적으로 최소 최단거리의 노드를 선택하며 테이블을 갱신 (heapq 사용)
O(E log V)

  • V: 노드수, E: 간선수
  • visited: [False] * (n+1)
  • distance: [INF] * (n+1)
def dijkstra(graph, startNode):
    distance = [INF]*(len(graph)+1)
    distance[startNode] = 0
    q = []
    # q: (distance, node), distance 가 적은 node 순으로 정렬된다
    heapq.heappush(q, (0, startNode))
    
    while q:
        currentDistance, currentNode = heapq.heappop(q)
        # currentNode 의 distance 가 갱신된적이 있는 경우 무시
        if distance[currentNode] < currentDistance:
            continue
        
        # currentNode 의 인접노드들 확인
        for node in graph[currentNode]:
            nodeNum = node[0]
            nodeCost = node[1]
            newDistance = currentDistance + nodeCost

            if newDistance < distance[nodeNum]:
                distance[nodeNum] = newDistance
                heapq.heappush(q, (newDistance, nodeNum))
                    
    return distance
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
startNode = int(input())

graph = [[] for i in range(n+1)]
for _ in range(m):
    from, to, cost = map(int, input().split())
    graph[from].append((to, cost))

distance = dijkstra(graph, startNode)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

플로이드 워셜

여러개의 from, to 노드간 최단거리 구하기 알고리즘
점화식: AtoB = min(AtoB, AtoK + KtoB)
k, a, b 순차적으로 3중 for 구조
O(n^3)

def floydWarshall(graph):
    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])
                graph[b][a] = graph[a][b]
import sys
input = sys.stdin.readline()
INF = int(1e9)

n, m = map(int, input().split())
graph = [[]]*(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
            graph[b][a] = 0

for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a][b] = cost
    graph[b][a] = cost

floydWarshall(graph)

for a in range(1, n+1):
    for b in range(1, n+1):
        val = graph[a][b] if graph[a][b] != INF else "INF"
        print(val, end=" ")
    print()

서로소 집합

공통 원소가 없는 집합이 필요한 경우
하나의 집합으로 합치는 union 과 원소가 속한 집합을 알려주는 find 연산이 필요
union 의 경우 작은 노드값이 집합의 값이 된다.

# 노드값과 집합값이 같을때까지 재귀적으로 호출
def findParent(parents, x):
    if parents[x] != x:
        parents[x] = findParent(parents, parants[x])
    return parents[x]

def unionParent(parents, a, b):
    setA = findParent(parents, a)
    setB = findParent(parents, b)
    
    if setA < setB:
        parents[b] = setA
    else:
        parents[a] = setB
v, e = map(int, input().split())
parents = [i for i in range(v+1)]

for _ in range(e):
    a, b = map(int, input().split())
    unionParent(parents, a, b)
    
for i in range(1, v+1):
    print(findParent(parents, i), end=" ")
print()

사이클 판별

유향 그래프: DFS 알고리즘
무향 그래프: 서로소 집합 알고리즘

# 무향그래프에서 사이클 판별
v, e = map(int, input().split())
parents = [i for i in range(v+1)]

cycle = False

for i in range(e):
    a, b = map(int, input().split())
    
    if findParent(parents, a) == findParent(parents, b):
        cycle = True
        break
    else:
        unionParent(parents, a, b)
        
if cycle:
    print("사이클 발생")
else:
    print("사이클 비발생")

크루스칼 알고리즘

경로를 최소한의 비용으로 연결하는 알고리즘
모든 간선에 대해 비용값 기준 정렬, 사이클이 발생하지 않는 간선부터 집합에 포함
무향 그래프이므로 find, union 을 통해 사이클 여부 판별 후 간선비용 총합
O(E log E)

v, e = map(int, input().split())
parents = [i for i in range(v+1)]
edges = [(a, b, cost) for _ in range(e) a, b, cost = map(int, iniput().split())]
result = 0

edges.sort()

for edge in edges:
    cost, a, b = edge
    
    if findParent(parents, a) != findParent(parents, b):
        unionParent(parents, a, b)
        result += cost

print(result)

위상정렬

우선순위(선후관계)에 따라 방향성에 거스르지 않도록 순서대로 나열
진입차수 테이블과 deque가 필요
deque가 빌때까지 각 노드부터 출발하는 간선을 제거하며 진입차수가 0인 노드를 삽입
O(V+E)

def topologySort(graph, indegree):
    result = []
    q = deque()
    
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)
            
    while q:
        node = q.popleft()
        result.append(node)
        
        for i in graph[node]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
                
    return result
from collections import deque

v, e = map(int, input().split())
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)
    indegree[b] += 1
    
sorted = topologySort(graph, indegree)

for n in result:
    print(n, end=" ")
profile
 iOS Developer

0개의 댓글