Major/Data Structure

Chapter 1 자료구조 소개 01 자료구조의 이해 1. 자료구조의 개념 - 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것 2. 자료구조의 분류 1) 단순구조 : 정수, 실수, 문자, 문자열 2) 선형구조 : 순차 리스트, 연결 리스트(단순, 이중, 원형), 스택, 큐, 데트 3) 비선형 구조 : 트리, 그래프 4) 파일 구조 : 순차 파일, 색인 파일, 직접 파일 02 자료의 표현 1. 컴퓨터에서의 자료 표현 - 2진수 코드 형태로 처리하고 저장한다. * 2진수 한자리를 표현하는 단위를 bit 라고 함(4bit = 1nibble, 8bit= 1byte) 2. 수치 자료의 표현 1) 10진수 표현 - 존 형식 표현 - 1 바이트를 한 단위로 사용한다. - 존 영역은 항상 1111을 ..

3Chapter 배열, 구조체, 포인터 - 연습문제 1. ④ 해설 : 4 * 10 * 20 = 800 2. ④ 해설 : 1000 + 4(float)*10 = 1040 3. ② 1) 40 2) 80 3) 40 4) 40 4. int main() { int two[10]; for (int i = 0; i < 10; i++) { two[i] = pow(2, i); printf("%d ", two[i]); } } 5. struct person { char name[10]; int age; float wage; } 6. typedef complex { float real; float imaginary; } complex; complex c1, c2; 7. typedef struct Complex { int rea..

1. 최단 경로 - 최단 경로 문제는 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. - 최단 경로를 찾는 대표적인 알고리즘으로 다익스트라, 플로이드 워셜, 벨만포드가 있다. 2. 최단 경로 알고리즘 1) 다익스트라(Dijkstra) ① 개념 : 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. ※ 조건 : 음수 가중치와 음수 사이클은 없다고 가정한다. ② 동작 과정 - 시작점으로부터 가장 가까운 정점을 방문 - 방문한 정점에서 인접한 정점들에 대해 거리를 갱신 위와 같은 그래프가 있을 때, v0을 시작노드라고 하면 아래와 같이 거리가 갱신된다. v0 v1 v2 v3 v4 v5 0 50 10 INF 45 INF 그다음 노드를 v2..

1. 최소 신장 트리 - 연결된 그래프 G(V.E)의 신장 트리란, 그래프 내의 모든 정점을 포함하는 트리다. - 이 트리는 모든 정점들이 연결되어 있어야 하고, 사이클이 없어야 한다. - 에지에 가중치가 주어진 그래프 G에서 G의 신장 트리 중에 에지 가중치 합이 최소가 되는 신장 트리를 최소 신장트리라고 한다. 2. 최소 신장 트리 알고리즘 1) 크루스칼(Kruskal)의 알고리즘 - 크루스칼의 알고리즘은 탐욕적인(greedy method) 방법을 이용한다. - 탐욕적인 방법이란 선택할 때마다 그 순간 가장 좋다고 생각 되는 것을 선택함으로써 최종적인 해답에 도달하는 방법 👉 알고리즘 - 가중치가 최소인 간선을 추가해가며 트리를 만들어 간다. - 만약에 간선을 추가해서 사이클이 만들어 진다면 그 간선..

1. 그래프 순회 - 그래프 순회란 정점과 에지를 체계적으로 방문하는 것을 말한다. ⓐ 깊이 우선 탐색(depth first search_DFS) : 전순위 순회 일반화 ⓑ 너비 우선 탐색(Breadth first search_BFS) : 레벨순위 순회 일반화 2. 깊이 우선 탐색(DFS) 1) 알고리즘 ① 먼저 정점 v를 방문 한 다음 ② v에 인접한 정점 중에서 방문하지 않는 정점 w를 찾아서 w에 대한 DFS를 재귀적으로 수행한다. 2) 구현 #include #include using namespace std; #define MAX_NODE 100 bool visited[MAX_NODE]; vector v[MAX_NODE]; void DFS(int x){ visited[x] = true; print..

1. 그래프의 개념 그래프(Graph)란, 노드(N)과 노드를 연결하는 간선(E)을 하나로 모아 놓은 자료 구조이다. 2. 대표적인 용어 정점(Vertex) : 노드의 위치 엣지(Edge) : 간선, 즉 노드들을 연결하는 선 분지, 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 사이클(Cycle) : 시작 정점과 종료 정점이 동일한 경우 연결 성분(Connected component) : 서로 연결되어 있는 각각의 그래프의 개수(부분 그래프의 개수) 3. 그래프 종류 방향 그래프 : 간선에 방향이 있는 그래프(간선에 화살표가 있으면 방향그래프) 무방향 그래프 : 간선에 방향이 없는 그래프 연결 그래프 : 두 정점 사이에 경로가 존재하는 그래프 완전 그래프 : 한 정점에서 모든 ..

01 5개 02 ④ 스택 03 ④ 순환 호출의 순차번호 04 ③ 05 n이 줄어들지 않아 무한적으로 반복된다 06 기저조건이 없다 07 5 4 3 2 1 0 반환 값 : 16 * 이유 sum(5) = 5+ sum4 = 16 sum(4) = 4 + sum3 = 11 sum(3) = 3 + sum 2 = 7 sum(2) = 2 + sum 1 = 4 sum(1) = 1 + sum 0 = 2 sum(0) = 1 08 출력 : 5 4 3 2 1 0 반환 값 : 95 09 출력 : 10 7 4 1 -2 반환 값: 3 10 1 2 3 4 5 11 ******* 7개 함수가 몇번 실행되는지 알면된다. 12 evisrucer * getchar : 사용자가 키보드로 입력한 문자 혹은 문자열에서 한 글자를 읽어서 반환하는 ..

1. 순환 - 순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그램이다. 1. 순환의 예 ex) 팩토리얼 계산 🟡 코드 int factorial(int n) { if(n

1. 배열 표현법 - 이진트리를 완전 이진 트리라고 가정하고 연속적으로 값을 할당한다. - 인덱스 0은 사용하지 않는다. - 완전 이진 트리가 아닐 시 기억공간의 낭비가 심하다. 1) 특징 - 노드 i의 부모 노드 인덱스 = i/2 - 노드 i의 왼쪽 자식 노드 인덱스 = 2i - 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1 2. 링크 표현법 - 트리에서의 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법이다. - 하나의 노드는 3개의 필드를 가지는데, 왼쪽자식 노드의 포인터, 데이터, 오른쪽 자식의 포인터를 가진다. > 코드 구현 #include using namespace std; typedef struct TreeNode { int d..