알고리즘4 알고리즘 - 2016 출석수업 자료 및 예상문제 1. 알고리즘이 무엇인지 •요건에 대해 서술하시오주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것 입출력 0개 이상의 외부 입력 1개 이상의 출력 모호하지 않고 단순 명확한 명령 한정된 수의 작업 후에는 반드시 종료 모든 명령은 수행 가능해야 함 (실용적 관점) 효율적이어야 함 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것이 알고리즘이다 2. 전이진, 포화이진, 완전이진 트리 개념, 샘플예제를 그리시오☞전 이진 트리(full binary tree)는 단말 노드가 아닌 모든 노드가 2개의 자식을 가진 트리이다. ☞포화이진 트리(perfect binary tree)는 모든 단말 노드의 깊이가 같은 전 이.. 2016. 3. 25. Algorythms Big-O (or Big-oh) notation Big-O (or Big-oh) notation 계산 복잡도 이론에서 사용되는 점근 표기법. 입력 데이터의 크기와 알고리즘의 소요 시간 또는 메모리의 상관관계를 나타낸다. 1.1. 정의 모든 n(n은 어떤 n0보다 크거나 같다)에 대해 |f(n)|= 2015. 5. 12. Algorithms 알고리즘의 정의 알고리즘의 정의문제를 해결하기 위한 명령어들의 유한집합어떤 문제에 대해 입력 받아서 출력을 내기위해서 컴퓨터에 의해 샐행, 유한 번 수행후에 종료되는 명확 명령어들의 나열 알고리즘의 조건입력 (input)출력 (output)명확성 (definiteness)유한성 (finiteness)유효성 (effectiveness) 2015. 5. 3. Algorithm Dijkstra(데이크스트라) 최단경로 알고리즘 algorythm_05_dijkstra Dijkstra(데이크스트라) 최단경로 알고리즘 Home Contact 알고리즘의 개요 방향이 주어진 가중 그래프(weighted graph) G와 출발점 s(tart)를 입력으로 받는다. V(ertex) : 그래프의 모든 점들의 집합 (u(ndefined), v(ertex)) : 그래프의 간선. 간선의 출발점 u, 간선의 도착점 v E(ddge) : G의 모든 간선들의 집합 w: E -> [0, infinity] : 간선들의 가중치 w(u, v): 점 u에서 점 v로 이동하는데 드는 비용. 경로의 비용 : 경로 사이의 모든 간선들의 가중치의 합. 데이크스트라 알고리즘은 V의 임의의 점의 쌍 s 와 t가 있을 때 s 에서 t 로 가는 가장 적은 비용이 드는 경로(최.. 2015. 4. 29. 이전 1 다음
