Coding Story

그래프를 인접 행렬과 인접 리스트로 표현했을 때 진입/진출 차수 계산, 엣지수를 계산할 때 각각의 시간 복잡도를 C언어 코드로 구현하였다. int matrixCalculateOutDegree(GraphType* g, int v) { int i, degree = 0; for (i = 0; in; i++) { if (g->adj_mat[v][i] != 0) degree++; } return degree; // 시간 복잡도는 O(n) } int matrixCalculateInDegree(GraphType* g, int v) { int i, degree = 0; for (i = 0; i n; i++) { if (g->adj_mat[i][v] != 0) degree++; } return degree; /..

자료구조와 알고리즘 자료구조의 필요성 컴퓨터에서 처리할 자료들을 효율적으로 관리하기 위해 구조화 자료의 특성에 따라 자료의 형태를 구성하고 처리하고 저장 자료구조란? 자료를 효율적으로 처리할 수 있도록 자료를 조직화하고 체계적으로 구조화하여 표현한 것이다. 프로그램 = 자료구조 + 알고리즘 알고리즘이란? 해야 할 일을 컴퓨터가 수행하여야 할 단계적인 절차를 자세히 기술하는 것 컴퓨터로 문제를 풀기 위한 단계적인 절차 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것 특정한 일을 수행하는 명령어들의 집합(명령어란 컴퓨터에서 수행되는 문장들) 알고리즘의 조건 입력 : 0개 이상의 입력이 존재하여야 한다. 출력 : 1개 이상의 출력이 존재하여야 한다. 명..

그래프 그래프의 개념 객체 사이의 연결 관계를 표현할 수 있는 자료구조 정점(vertex)과 간선(edge)으로 이루어진 자료구조 그래프와 관련된 용어 정점(vertex): 노드(node)라고도 불리며, 여러가지 특성을 가질 수 있는 객체 간선(edge): 링크(link)라고도 불리며, 정점을 연결하는 선 인접 정점(adjecent vertex): 간선에 의해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수 단순 경로(simple path..

머신 스케줄링 어떤 작업을 처리하는 동일한 기계가 m개 존재하고 처리해야 할 작업이 n개 있다고 하자. 이 기계를 풀가동하여 가장 최소의 시간에 작업들을 끝내고자 한다. 이것을 머신 스케줄링이라한다. 이 문제의 최적의 해를 찾는것은 어렵지만 LPT(longest processing time first) 방법을 통해 근사의 해를 찾을 수 있다. LPT(Longest Processing Time first) LPT는 가장 긴 작업을 우선적으로 가장 먼저 사용가능하게 되는 기계에 할당하는 것이다. 맨 위의 표는 각 작업의 기계 사용 시간이다. 미리 정렬되어 있다고 가정한다. 최소 힙은 모든 기계의 종료시간을 저장하고 있다. 초기의 모든 기계의 종료시간은 0이고, 힙에서 최소 종료시간을 가지는 기계를 삭제하여 ..

우선순위 큐(Priority Queue) 1. 우선순위 큐란? 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐는 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐는 2가지로 구분할 수 있다. 최소 우선순위 큐는 가장 우선 순위가 낮은 요소를 먼저 삭제하고, 최대 우선순위 큐는 반대로 가장 우선 순위가 높은 요소가 먼저 삭제된다. 우선순위 큐는 대표적으로 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제에서의 작업 스케쥬링, 수치 해석적인 계산 등 컴퓨터의 여러 분야에서 이용된다. 우선순위 큐는 배열, 연결 리스트, 힙으로 구현이 가능한데, 가장 효율적인 구조는 힙이다. 2. 우선순위 큐의 구현 방..