Programming

위상 정렬 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 정렬 알고리즘의 일종 ex) 선수과목을 고려한 학습 순서 설정 * 진입차수(Indegree) : 특정한 노드로 '들어노는' 간선의 개수 위상 정렬 알고리즘 진입차수가 0인 노드를 큐에 넣기 큐가 빌 때까지 다음의 과정 반복 1) 큐에서 원소를 떠내 해당 노드에서 출발하는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 넣기 알고리즘 동작 원리 큐가 빌 때까지 큐에서 원소를 꺼내서 처리하는 과정을 반복 모든 원소 방문하기 전 큐가 빈다 = 큐에서 원소가 V번 추출되기 전 큐가 빈다 → 사이클 O 0. 진입차수 0인 노..

신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건 크루스칼 알고리즘 가장 적은 비용으로 모든 노드 연결 그리디 알고리즘 최소 신장 트리 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리 찾는 알고리즘 - 대표적으로 크루스칼 알고리즘 - ex) N개의 도시에서 전체 도시가 연결될 수 있게 도로 설치하는 경우 알고리즘 동작 원리 일종의 트리 자료구조 → 신장 트리에 포함되는 간선의 개수 '노드의 개수 - 1' 가장 거리가 짧은 간선부터 차례대로 집합에 추가 사이클 발생 간선은 제외하고 연결 → 항상 최적해 보장 간선 데이터를 비용에 따라 오름차순으로 ..

이미 배운 내용을 훑어보자 그래프 알고리즘은 코테에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘 그래프 알고리즘의 한 유형 : DFS/BFS, 최단 경로 그래프 자료구조 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 알고리즘 문제에서 '서로 다른 개체(객체)가 연결되어 있다'를 보면 그래프 알고리즘 가장 먼저 떠올리기 ex) 여러 개의 도시가 연결되어 있다 트리 자료구조 그래프 자료구조의 일종 부모에서 자식으로 내려오는 계층적인 모델 최소힙 : 트리 자료구조, 항상 부모 노드가 자식 노드보다 크기가 작음 그래프 트리 방향성 방향 그래프 or 무방향 그래프 방향 그래프 순환성 순환 or 비순환 비순환 루트 노드 존재 여부 루트 노드 X 루트 노드 O 노드간 관계성 부모와 자..

다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 문제 해설 한 도시에서 다른 도시가지의 최단 거리 문제로 치환 → 다익스트라 알고리즘 N과 M의 범위가 충분기 크므로, 우선순위 큐 다익스트라 알고리즘을 조금 변경하여 문제 해결 가능 풀이 import queue import sys input = sys.stdin.readline # 입력을 빠르게 받기 위함 INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수, 시작 노드를 입력받기 n, m, start = map(int, input().split()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for ..

플로이드 워셜 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 문제 해설 N의 범위가 100 이하로 매우 한정적 → 플로이드 워셜 O(N^3) 알고리즘으로 풀 수 있음 (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리) 문제 먼저 그림을 그려보는 것도 좋은 방법 풀이 INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n, m = map(int, input().split()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a ..

가장 빠르게 도달하는 방법 최단 경로 알고리즘 = 가장 짧은 경로 찾기 = 길 찾기 ex) 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등 대표적인 예시 : 다익스트라 최단 경로, 플로이드 워셜 알고리즘 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 특징 '음의 간선'이 없을 때 정상적으로 동작 GPS 소프트웨어의 기본 알고리즘으로 채택 그리디 알고리즘으로 분류 : '가장 비용이 적은 노드' 선택 '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트에 저장 & 갱신 알고리즘의 원리 출발 노드를 설정 최단 거리 테이블 초기화 방문x 노드 중 최..