Algorithms/Concepts (2) 썸네일형 리스트형 [알고리즘] 위상정렬(Topological Sort) Concept 1) 개념 "순서가 정해져 있는 작업들의 순서를 정해주기 위해 사용하는 알고리즘." 방향 그래프(유향 그래프, Directed Graph)의 꼭짓점(Vertex)들을 방향에 거스르지 않도록 나열하는 것을 의미한다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. (시작점을 찾을 수 없기 때문) ex) 선수과목(prerequisite) 구조, 업무 일정 배치(PERT - 일정관리 평가 분석) 2) 수행 과정 ① 자기 자신을 가리키는 변이 없는 버텍스(노드)를 찾는다. ② 찾은 버텍스를 출력하고, 출력한 버텍스와 그 버텍스에서 출발하는 간선(edge)을 삭제 ③ 아직 그래프에 버텍스가 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다. 3) 시간복잡도 O(.. [알고리즘 공부] 동적계획법(Dynamic Programming) [ 컨셉 ] 1. 문제에 대한 접근 방식을 일컫는다 2. 큰 문제를 작은 문제로 나누어 해결해 나가는 것 Q. 분할정복 기법 또한 부분 문제로 나눠 해결하는 과정인데 무엇이 다르지? 부분 문제의 중복이 핵심. 부분 문제의 중복이 많이 일어나는 문제의 경우, 분할 정복은 해결에 어려움이 있을 수 있다. [ 동적계획법의 종류 ] 1. 하향식 방법 (Top-down) 재귀함수를 통해 하위 문제들을 해결해 나가는 방식 많은 중복이 발생하는 경우, 재귀적인 풀이는 효율성에 문제가 발생할 수 있다. "Memoization"을 통해 해결 된 하위 문제들을 캐싱(Caching)하여 중복을 해결하여 오버헤드를 줄일 수 있음. 2. 상향식 방법 (Bottom-up) 가장 하위의 문제부터 시작하여 순차적으로 해결해 나가는 .. 이전 1 다음
