본문 바로가기
반응형

자료구조및알고리즘35

위상정렬 (topological sorting) 위상정렬 위상정렬이란 위키나무 에서 다음과 같이 정의한다. 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 .. 2023. 9. 30.
프림 알고리즘 프림 알고리즘은 그래프에서 최소 스패닝 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘 중 하나이다. MST란 원래 그래프의 모든 정점을 포함하면서 사이클이 없는 트리다. 최소 스패닝 트리는 그래프의 모든 정점을 가장 적은 비용으로 연결하는 트리를 말한다. 프림 알고리즘의 동작 방식은 1. 임의의 정점을 선택하여 시작 2. 이 정점은 초기에 최소 스패닝 트리에 포함 3. 선택한 정점과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택 4. 이 간선으로 연결된 정점을 MST에 추가 5. MST에 포함된 정점들과 연결된 간선들 중에서 가장 가중치가 작은 간선을 선택 모든 정점을 MST에 포함시킵니다. 프림 알고리즘은 우선순위 큐 를 사용하여 간선들을 관리하면 효율적으로 구현할 수.. 2023. 7. 26.
플로이드-워셜 알고리즘 플로이드 워셜 알고리즘이란 모든 최단경로를 구하는 알고리즘이다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다 한붓그리기인 오일러서킷 과는 다르다 오일러 서킷은 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 반드시 시작점으로 돌아와야하며, 한 번 지나간 선으로는 지나가지 않고 모든 선을 이어 그림을 완성하는 것이다. 나중에 오일러 서킷을 알아보도록 하겠다. 플로이드 - 워셜 알고리즘은 O(N^3) 이기 때문에 N이 20 만 넘어가도 엄청나게 된다. 모든 노드 간의 최단거리를 구해.. 2023. 7. 17.
Union-Find (Disjoint Sets) 알고리즘 Union - Find랑 크루스칼 알고리즘을 사용하려면 필수적으로 알아야하는 알고리즘이다. 여러개의 노드가 존재할때 두 개의 노드를 선택하여 같은 트리에 포함되어있는지 확인하는 것이다. Union - Find 를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다. 트리로 부분집합을 표현하고 find를 통해 루트 노드를 찾고 union으로 트리를 합친다. 처음 시작할때 숫자들은 자기 자신이 부모이며, 노드가 연결되어있어 합치게 되면 더 작은값이 부모가 된다. 만약 1,2 가 연결되어있으면 부모는 1,1 이다. def find(parent, x): if parent[x] != x: # 자기 자신이 아닌경우 다른 노드에 연결된 경우 parent[x] = find(parent, parent[x]) retur.. 2023. 6. 13.
LIS 최장증가수열 최장증가수열이란 : 가장 긴 증가하는 수열을 말한다. [1,4,3,6,4,8] 이런식으로 주어졌을때 가장 긴 증가하는 수열은 [1,3,4,8] 4이다. 이러한 문제를 풀때는 dp를 사용하여야 하는데, 각 idx까지의 최장증가 수열을 dp에 저장하는 것이다. 주어진 idx 보다는 작지만 가장 긴 수열에 + 1을 해주면된다. idx 가 0 일때 는 dp[0] = 1 1일때는 dp[1] = 2 dp[2] = 2 dp[3] = 3 dp[4] = 3 dp[5] = 4 이렇게 하려면 이중 포문을 사용해야한다. for i in range(N): for j in range(i): if lst[i] > lst[j]: dp[i] = max(dp[i], dp[j] + 1) 그것을 식으로 나타나면 이렇게 된다. 기본문제: h.. 2023. 6. 13.
크루스칼 알고리즘 프로그래머스 LV3 레벨을 풀던중 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 푸는데 당연히 난 다익스트라를 사용하여 푸려고 했다. def solution(n, costs): costs = sorted(costs, key=lambda x:(x[2])) print(len(costs)) dist =[1] + [0] * (n-1) graph = [ [] for _ in range(n)] for ( x, y, z ) in costs: g.. 2023. 5. 23.
반응형

티스토리툴바