그래프 개요 그래프는 버텍스와 아크로 이루어져 있다. 그래프는 버텍스 간에 여러 개의 아크가 존재할 수 있는데, 다른 버텍스에서부터 오는 아크의 개수를 In-degree, 다른 버텍스로 가는 아크의 개수를 Out-degree라고 부른다. 이때 방향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로도 나뉜다. 뱡향 그래프는 무방향 그래프와 다르게 방향을 나타내는 화살표가 있다. 위 방향 그래프 그림에서 (C) 버택스는 (B)로 부터 오는 한 개의 In-degree와, (E), (D)로 가는 두 개의 Out-degree를 가지고 있다. 위 무방향 그래프 그림에서 (E) 버텍스는 (B), (D) 2개의 Degree가 있다. 그래프를 코드로 나타내기 그래프를 코드로 표현하는 방법엔 크게 두 가지가 있다. 하..

#include #include #include #include #include #include #define MAX_FNAME 100 #define MAX_WORDS 10000 #define MAX_WORD_SIZE 100 #define TRUE 1 #define FALSE 0 // 데이터 형식 typedef struct { char word[MAX_WORD_SIZE]; // 단어 int count; } element; // 노드의 구조 typedef struct TreeNode { element key; struct TreeNode *left, *right; } TreeNode; // 문자열 비교 strcmp 함수 // 만약 e1 음수 반환 (시스템에 따라: -1) // 만약 e1 ==..

#include #include #include #include // // Calculator // // 프로그램 5.3 // 스택 동작 관련 함수들 typedef char element; #define MAX_STACK_SIZE 100 #define MAX_STR_SIZE 4096 typedef struct { element data[MAX_STACK_SIZE]; int top; } StackType; // 스택 초기화 함수 void init_stack(StackType* s) { s->top = -1; //s->capacity = 1; //s->data = (element *) malloc(s->capacity * sizeof(element)); } // 공백 상태 검출 함수 int is_empty(..

C언어에서 배열의 요소는 연속적인 메모리 공간에 할당된다. 1차원 배열 int A[6]; 다음의 배열의 각 요소의 주소는 어떻게 계산할 수 있을까? 배열 A는 크기가 6인 int형 배열로 각 요소가 int만큼의 메모리를 가진다. 또한 C언어에서 int형의 크기는 기기에 따라 가변적이기 때문에 int형 자료형의 데이터 길이를 가져오는 sizeof(int) 함수를 사용한다. C언어에서 배열은 연속적인 주소에 저장되기 때문에 A[0]의 주소를 base address라고 하면 A[i]의 주소는 base + i*sizeof(int)가 된다. 2차원 배열 2차원의 배열은 index가 두개가 있다 행 index와 열 index이다. int A[2][2] 다음의 배열을 머릿속으로 그려보자 A[0][0] A[0][1] ..

알고리즘의 성능을 분석하는 방법은 뭘까? 알고리즘의 runtime이 짧으면 좋은 성능인 것일까? 이 running time을 측정하는 방법은 프로그램을 수행하는 기기에 의존적일 수 밖에 없다. 간단하게 연산이 빠른 슈퍼컴퓨터와 일반 컴퓨터로 동일한 프로그램을 실행하면 일반적으로 슈퍼컴퓨터가 빠를수밖에 없기 때문이다. 우리는 컴퓨터의 성능을 측정하는 것이 아닌 알고리즘의 성능을 분석하는 것이기 때문에 알고리즘에서는 특별한 성능 측정 방법을 사용한다. 복잡도 Complexity 1. 공간 복잡도 (Space Complexity) 이 문제를 해결하는데 얼마만큼의 메모리가 필요한가? 고정된 필요 메모리와 가변 메모리 요소의 합으로 나타낸다. 2. 시간 복잡도 (Time Complexity) 이 문제를 해결하는데..