네발로 코딩하는 포메라니안

1. 그래프 그래프는 정점과 간선으로 구성되어 있다. 그래프는 방향성이 없는 '무방향 그래프'와 방향성이 있는 '방향그래프'로 나눠볼 수 있다. '각각 정점에서 다른 모든 정점을 연결한 그래프'를 '완전 그래프'라고 하며 아래 두 그래프가 이에 해당한다. 2. 그래프 구현방법 1) 인접 행렬(adjacent matrix) 기반 그래프 2차원 배열을 이용한다. 2) 인접 리스트(adjacent list) 기반 그래프 연결 리스트를 활용하여 그래프를 표현한다. 3. 그래프의 탐색 1. 깊이 우선 탐색 (DFS : Depth First Search) 자신과 연결된 노드들 중 내용이 전달 안 된 하나를 먼저 선택해서 그 사람과 연결된 노드들에게 내용을 다 전달하면, 다음 하나를 또 선택한다. 백트래킹이라고도 하..

1. 테이블 저장되는 데이터가 key & value가 한 쌍을 이룬다. 키는 서로 다른 데이터를 구별하기 위해 사용되므로 중복되어서는 안 된다. #include typedef struct data{ int number; //사람의 고유번호 = key값 int name; //데이터 }Data; int main(void){ Data arr[100]; Data person; int n; //데이터 넣기 scanf("%d %d", &(person.number), &(person.name)); arr[person.number] = person; //데이터 찾기 printf("확인하고 싶은 사람의 고유번호 입력: "); scanf("%d", &n); person = arr[n]; printf("나이 %d, 이름 %..

1. 탐색이란? 탐색은 '데이터를 찾는 방법'을 말한다. 여기서는 '어떻게 찾을까'와 '효율적인 탐색을 위해 어떤 방식으로 데이터를 저장할까'를 고민해야 한다. 정렬과 탐색은 정수를 기준으로 한다. 탐색할 데이터의 종류가 무엇이든 탐색 자체의 알고리즘에 대해서만 집중하기 위함이다. 따라서 데이터는 아래와 같이 구성한다. typedef struct item{ int searchKey; Data searchData;//Data : 원하는 데이터 type 적으면 됨 }Item; 2. 순차 탐색 - 단순하게 배열 처음부터 내가 찾는 값이 있는지 살펴본다. - 정렬되지 않은 배열을 대상으로 함 - O(n) 3. 이진 탐색 - 배열의 중앙에 위치한 데이터와 비교해서 그 데이터보다 작으면 왼쪽 구역에서의 중앙값과 또..

1. 버블 정렬(Bubble Sort) 배열 처음부터 시작해서, 바로 옆에 있는 값과 비교하고 우선 순위에 맞게 위치를 바꾸거나 그대로 둔다. 정리하자면, "우선 순위가 낮은 걸 뒤로 보내는 방법"이라고 할 수 있다. step1) 값이 제일 큰 걸 우선 순위가 낮다고 할 때, '4'가 제일 뒤에 위치하게 된다. step2) 그 다음 큰 값인 '3'이 '4'앞에 위치한다. step3) 그 다음 큰 값인 '2'가 '3'앞에 위치하여 결과적으로 오름차순 정렬이 끝난다. - 성능 = O($n^{2}$) 2. 선택 정렬(Selection Sort) 아직 정렬되지 않은 배열 부분을 모두 차례대로 읽어가면서, 최솟값(우선순위가 높은 것)을 찾아 앞으로 위치시킨다. - 성능 = O($n^{2}$) 3. 삽입 정렬(In..

1. 우선 순위 큐 - 큐에 넣을 데이터들이 우선 순위가 있다. - 우선 순위가 높은 것부터 꺼낼 수 있도록 한다. 2. 구현 방법 1. 배열 배열로 구현할 때, 우선순위가 높을수록 배열의 앞에 위치시키며 아래와 같은 단점이 있다. 1) 데이터를 삽입 및 삭제할 때, 데이터를 한 칸씩 밀고 당겨야 한다. => 연산 증가 2) 삽입 위치를 찾기 위해 처음부터 하나씩 비교를 해야 한다. 2. 연결 리스트 연결 리스트로 구현할 때, 배열과 마찬가지로 우선순위가 높을수록 리스트 앞쪽에 위치시킨다. 배열의 첫 번째 단점은 없지만, 두 번째 단점은 여전히 존재한다. 따라서 우선순위 큐는 힙을 사용하는 경우가 많다. 3. 힙 힙은 우선순위를 고려한 '완전 이진 트리'이다. *완전 이진 트리 : 자식 subtree가 ..

1. 트리 1. 트리 = 계층적 관계를 표현하는 자료구조 ex) 조직도 2. 이진트리 = 자식 가지가 최대 2개로 나누어진다. 2. 구현 방법 1) 배열 기반 이진트리 2) 연결 리스트 기반 이진트리 3. 이진트리의 순회 1. 전위 순회(Preorder Traversal) - 루트 노드 먼저 방문 = node -> Left subtree -> Right subtree 2. 중위 순회(Inorder Traversal) - 루트 노드를 중간에 방문 = Left subtree -> node -> Right subtree void inorder(TreeNode* bt){ inorder(bt->left); printf("%d \n", bt->data); inorder(bt->right); } 3. 후위 순회(Po..

1. 스택(Stack) - LIFO(Last-In, First-Out) 구조 : 먼저 들어간 것이 나중에 나온다. - 스택 관련 연산 1) push : 데이터 추가 2) pop : 데이터 꺼내기 - 소스코드 1) 배열로 Stack 구현 #include #include typedef struct ArrStack { int arr[100]; int top; }Stack; void init(Stack* node); int is_Empty(Stack* node); void push(Stack* node, int data); int pop(Stack* node); int main() { Stack my_stack; int n; init(&my_stack); for (int i = 0; i < 3; i++) { s..

1. 배열을 이용한 리스트 #include int main() { int arr[10]; int n, index = 0; //입력 while (indexdata = n; newNode->next = NULL; if (head == NULL) head = newNode; else tail->next = newNode; tail = newNode; } printf("\n"); //출력 if (head == NULL) printf("list에 데이터가 없습니다."); else { current = head; printf("%d ", current->data); while (current->next != NULL) { current = current->next; printf("%d ", current->data..

1. 재귀함수란? - 함수 내에서 자기 자신을 다시 호출하는 함수 void Recursive(void){ printf("Recursive call\n"); Recursive(); } 2. 관련 문제 1. 피보나치 수열 #include int fibo(int n) { if (n == 1) return 0; if (n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { int n; scanf("%d", &n); printf("%d\n", fibo(n)); return 0; } 2. 이진탐색 #include int BinarySearch(int* arr, int left, int right, int n) { if (left > right) ret..