🥕 문제 이름 : 커리큘럼 참고한 책 ; 나동빈 (2020). . 서울시: 한빛미디어. 303p 🍒 문제 분석 N개의 교양 강의를 듣고자 한다. 각 과목에는 선수과목이 있는 과목이 있고 없는 과목이 있다. 강의는 동시에 들을 수 있기 때문에, 가령 과목 3의 선수과목이 1과 2 일 때, 1이 30시간, 2가 20시간 걸린다고 한다면, 과목 3을 듣기 위해 선수과목을 듣는 시간은 30시간이 되는 셈이다. 따라서 강의 3의 강의 시간이 40시간이라면, 과목 3을 수강하기 까지 걸리는 시간은 70 시간이다. N 개의 강의를 모두 듣는데 걸리는 최소 시간을 구해야 한다. 🥑 코드 # 입력 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 from collections import deque ..
알고리즘
[정의] 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 기본적으로 사이클이 발생하는 경우는 고려하지 않는다. 진입 차수라는 개념에 대해서 알아야할 필요성이 있다. 진입 차수란 특정한 노드로 들어오는 간선의 갯수를 의미한다. 경제학원론은 선수 과목이 없다. ( 진입 차수가 0 ) 경제수학은 1 개의 선수 과목을 가지고 있다. ( 진입 차수가 1 ) 중급 미시 경제학은 두 개의 선수 과목을 가지고 있다. ( 진입 차수가 2 ) 다음을 위상 정렬 하게 되면 ' 경제 학원론 -> 경제 수학 -> 중급 미시 경제학 ' 이 될 것이다. [위상 정렬] 마치 BFS 같이 하면 된다. 노드 1 2 3 4 5 6 7 진입 차수 0 1 1 2 1 2 1 다음의 그래프에서 먼저 진입차수가 0인..
[신장 트리] 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 신장 트리라고 한다. 아래는 원래의 그래프(위)에 대한 부분 그래프(아래), 신장 트리의 예 이다. [크루스칼 알고리즘] 그래프의 간선에 비용이 적혀있다고 하자. 신장 트리의 모든 간선에 대하여, 비용이 합이 가장 적겠끔 하는 신장 트리를 구하는 알고리즘을 최소 신장 트리 알고리즘이라고 한다. 대표적인 최소 신장 트리 알고리즘으로 크루스칼 알고리즘이 있다. 그리디 알고리즘으로 분류된다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선 3, 4 4, 7 4, 6 6, 7 1, 2 2, 6 2, 3 5, 6 1, 5 비용 7 13 23 25 29 34 35 53 75 간선을 하나 하나 체크해가며 그래..
[정의] union 과 find 연산으로 이루어진다. ( union-find 자료구조 라고도 불린다. ) 코드를 보면 알겠지만, 집합은 같은 부모 노드를 가지고 있다는것으로 묶을 수 있고, 따라서 union 함수는 부모 노드를 합치는 함수라고 할 수 있다. find 함수는 부모 노드를 찾는 함수이다. find를 하여서 부모노드를 찾았는데 서로 다르면 다른 집합이고, 서로 같으면 같은 집합이다. find를 통해 부모 노드를 찾을 때는, 재귀적으로 부모를 거슬러 올라가 자기 자신을 부모 노드로 갖는 노드를 찾는다. 왜냐면 자기 자신을 부모 노드로 갖는 노드가 루트 노드가 되기 위한 정의이기 때문이다. 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 한다. 무방향 그래프에서 적용 가..
