이 버전은 저장된 사람의 수가 배열의 용량을 초과하는 경우, 배열의 크기를 확장한다. 또 잘못된 명령이 있다면 적절하게 반응하도록 한다. 예시 $ read File name required. $ read directory.txt $ status David 0517778888 Henry 0243737788 John 01034523747 Sean 01012345678 $ add Anderson Number required. $ add Anderson 01032452587 Anderson was added successfully. $ save directory.txt $ exit #include #include #include #define INIT_CAPACITY 3 #define BUFFER_SIZE 50..
CS/자료구조
앞선 v1.0과는 동일하지만 전화번호부 v2.0은 파일로부터 데이터를 읽어오며 데이터를 알파벳 순으로 정렬한다. 데이터를 정렬된 상태로 유지하기 위해서는, 1) Sorting 알고리즘을 사용하거나 2) 새 데이터가 추가될 때마다 자릴 찾아 삽입 하는 방법이 있다. 이 버전은 알파벳 순서대로 정렬해야 하므로 2번으로 프로그래밍한다. #include #include #define MAX 100 #define BUFFER_SIZE 100 char* names[MAX]; char* numbers[MAX]; int n = 0; void add(); void find(); void status(); void remove(); void save(); void load(); int main() { char com[BU..
프로그램을 실행하면 화면에 프롬포트($)를 출력하고 사용자의 명령을 기다린다. 1. 새로운 사람을 추가한다. $ add John 01079799898 John was added successfully. 2. 이름으로 전화번호를 검사한다. $ find Henry No person named 'Henry' exists. $ find David 0517778888 3. 전화번호부에 등록된 모든 사람을 출력한다. $ status John 01076769898 David 0517778888 Total 2 persons. 4. 전화번호부에서 삭제한다. $ delete Jim No person named 'Jim' exists. $ delete John John was deleted successfully. 5. 프..
1. 리턴을 제외한 입력문장을 그대로 출력한 후 문장의 길이를 출력한다. (단, 공백문자도 포함해 카운트하며 문장의 앞뒤에 붙은 공백까지 그대로 출력한다.) #include #include #define BUFFER_SIZE 20 int readline(char str[], int lim) { int ch, i = 0; while ((ch = getchar()) != '\n') // 한 문자씩 입력 받음 if (i < lim - 1) str[i++] = ch; str[i] = '\0'; return i; } int main() { char buffer[BUFFER_SIZE]; while (1) { printf("$ "); //fgets(buffer, BUFFER_SIZE, stdin); // 라인 단위의..
1. 벨만 포드 : 그래프 상의 한 정점으로부터 다른 모든 정점들까지의 최단 경로를 구하는 알고리즘 - single-source 최단경로 알고리즘 - 가중치가 음수인 경우도 적용 가능 - 가중치가 사이클을 이루는 경우 불가능 - 시간 복잡도 O(nm) (최악의 경우 최대 n개의 정점, n-1개의 간선) - 동작과정 - 가장 가까운 노드를 탐색해 한 단계 거칠 때마다 최단 거리를 확정해 나감. - (n-1)번 반복해 모든 노드 간의 최단 거리를 완화해 나감. s에서 u까지의 최단 경로가 다음과 같다고 가정하자. 처음에는 모두 upper[] 상태 시작노드인 s는 upper[s] = dist [s] = 0 이다. 모든 간선을 탐색해 relaxation 과정을 반복한다. upper[a]
1. DAG : Directed Acyclic Graph DAG란? 사이클이 존재하지 않는 방향 그래프 예를 들면, 라면을 끓이는 순서 어느 작업이 하나의 작업의 선행작업이 되는 경우, 자신으로 돌아올 수 없다. 👉 작업의 우선순위를 표현할 때 2. 위상정렬 우선순위를 표현하기 위해 사용 -> 노드들을 순서화하는 것 작업의 순서를 표현, 순서 유일 X 왼쪽에서 오른쪽으로 향하도록 한다. 1) 위상정렬을 통한 해결 방법 indegree(들어오는 차수)가 0인 노드를 선택한다. -> 차수가 같다면, 어느 노드를 선택해도 무방 -> indegree가 0인 노드를 모두 큐에 삽입 2. indegree가 0인 노드 중 선택된 노드와 그 노드와 연결된 에지를 제거 -> 큐에서도 선택된 노드 삭제 3. 1~2번 과정..
1. 깊이우선순회 DFS 출발 노드 s에서 시작 현재 노드를 visited로 표시하고, 인접한 노드 중 unvisited 노드가 존재하면 노드로 향한다. (즉, leaf 노드에 도달하는 것과 같음) 2번을 반복 unvisited인 이웃 노드가 존재하지 않는 동안 직전 노드로 돌아간다. 2번을 반복 출발 노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. 자세하게 설명하면, 1에서 시작해 unvisited인 노드 중 3을 방문한다. 다음, 3과 인접한 노드 중 unvisited 노드 7을 방문한다. 7과 인접한 노드 중 unvisited 노드 8을 방문한다. 8과 인접한 unvisited인 이웃노드가 존재하지 않기 때문에 이전 노드인 7로 돌아간다. 노드 7 또한 unvisited인 이웃노드가 없으므로..
1. 그래프 순회(Graph Traversal) 순회란 ? 그래프의 모든 노드를 방문하는 일 BFS(너비우선순회) DFS(깊이우선순회) 1) BFS L0 = {s} (s : 출발노드) L1 = L0의 모든 이웃 노드 L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 . . Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 의 순서로 노드를 방문한다. 👉 level-order travasal 방식 - 큐를 이용한 너비우선순회 ① s가 1인 노드부터 순회를 시작, 방문한 노드임을 체크 후 큐에 넣음 ② 1을 큐에서 제거한 후 인접노드인 2, 3을 큐에 삽입 ③ 2를 큐에서 제거한 후 2의 인접노드인 4, 5를 큐에 삽입 ④ 3을 큐에서 제거한 후 3의 인접노드인 7, 8을 큐에 삽입 ⑤ 4를 ..
1. 그래프의 개념 그래프 G는 두 개의 집합 V와 E로 구성 V : node 혹은 vertex E : node 쌍을 연결하는 edge -> V(G)와 E(G)는 그래프 G의 정점들의 집합과 간선들의 집합을 나타냄. -> 개체들 간의 이진관계 표현 V = {1,2,3,4,5,6,7,8} E = {(1,2), (1,3), (2,3), .. , (7,8)} n = |V| = 8 m = |E| = 11 그래프의 종류에는 2가지가 있다. 방향그래프(Directed Graph) G = (V,E) : edge (u,v)는 u->v 가중치 그래프(Weighted Graph) : edge 마다 가중치 지정 2. 그래프의 표현 * 무방향 그래프 1) 인접행렬 (adjacency matrix) : n x n 행렬 A = ..
1. 해쉬테이블 - dynamic set을 구현하는 효과적 방법 중 하나 - 평균 탐색, 삽입, 삭제 시간은 O(1) - 최악의 경우 Θ(n) - 해쉬함수 h를 이용해 키 k를 T[h(k)]에 저장 - h : U -> {0, 1, ..., m-1} (m : 테이블 크기, U : 모든 가능한 키들의 집합) - 하나의 slot 혹은 bucket으로 사상됨 - 즉, 각 키는 0 ~ m-1의 정수로 mapping 2. 해쉬 함수의 예 - 모든 키를 자연수로 가정 예1) 문자열 ASCII 코드 : C = 67, L = 76, R = 82, S = 83 CLRS = (67 * 128^3) + (76 * 128^2) + (82 * 128^1) + 83 * (128^0) 예2) h(k) = k % m : key를 m으..
