[자료구조] 2020.08.03

1. [문제] 숫자 맞추기 게임(저번주 문제 복습)

   1) 1 ~ 100까지 랜덤으로 숫자 10개 생성
   2) 배열에 넣고 출력
   3) 오름차순정렬하고 출력 => 알고리즘 사용
   4) 0 ~ 9 중에 랜덤으로 선택, 해당 숫자를 맞춰보자!

   예시)
          [ 1 3 17 18 19 ]

          [2]->17
          3<= X <=18
          15
          16<= X <=18
          N번 소요됨!

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void swap(int* arr, int a, int b) {
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}
void quick_sort(int* arr, int start, int end) {
	int pivot = arr[start];
	int l = start + 1;
	int r = end;

	while (l <= r) {
		while (arr[l] < pivot) {
			l++;
		}
		while (arr[r] > pivot) {
			r--;
		}
		if (l <= r) {
			swap(arr, l, r);
		}
	}

	if (start < end) {	// 요소가 1개가 될 때까지 반복
		swap(arr, start, r);
		quick_sort(arr, start, r - 1);
		quick_sort(arr, r + 1, end);
	}
}

int main() {
	srand(time(NULL));
	int arr[10];
	for (int i = 0; i < 10; i++) {
		arr[i] = rand() % 100 + 1;
	}
	for (int i = 0; i < 10; i++) {
		printf("%d, ", arr[i]);
	}

	printf("\n"); 
	quick_sort(arr, 0, 9);
	for (int i = 0; i < 10; i++) {
		printf("%d", arr[i]);
	}

	printf("\n");
	int index = rand() % 10;
	printf("[%d] -> %d를 맞추자!\n", index, arr[index]);

	int start = index == 0 ? 1 : arr[index - 1];
	int end = index == 9 ? 100 : arr[index + 1];
	int cnt = 0;

	while (1) {
		printf("%d ~ %d : ", start, end);
		int n;
		scanf("%d", &n);
		if (start > n || n > end) {
			printf("[올바르게 입력하세요!]\n");
			continue;
		}
		cnt++;
		if (n == arr[index]) {
			break;
		}
		else if (arr[index] > n) {
			start = n + 1;
		}
		else {
			end = n - 1;
		}
	}
	printf("%d번 소요됨!\n", cnt);

	return 0;
}

 

 

2. 이진탐색(==이분탐색, 이진검색) 알고리즘(Binary Search Algorithm)

 : 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘,

   처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 선택 정렬 함수
void select_sort(int* arr, int n) {
	for (int i = 0; i < n; i++) {
		int min = arr[i];
		int min_index = i;
		for (int j = i; j < n; j++) {
			if (min > arr[j]) {
				min = arr[j];
				min_index = j;
			}
		}
		int tmp = arr[i];
		arr[i] = arr[min_index];
		arr[min_index] = tmp;
	}
}
// 이진탐색 == 이분탐색
int binarySearch(int* arr, int data, int start, int end) {
	int m = (start + end) / 2;

	while (start <= end) {
		if (arr[m] == data) {
			return m;
		}
		else if (arr[m] < data) {
			start = m + 1;
		}
		else {
			end = m - 1;
		}
		m = (start + end) / 2;
	}
	return -1;
}

int main() {
	// 1. 1~100까지 랜덤의 수 10개를 배열에 담기
	srand(time(NULL));
	int arr[10];
	for (int i = 0; i < 10; i++) {
		arr[i] = rand() % 100 + 1;
	}
	for (int i = 0; i < 10; i++) {
		printf("%d, ", arr[i]);
	}

	// 2. 선택 정렬을 이용하여 오름차순으로 정렬
	printf("\n");
	select_sort(arr, 10);
	for(int i = 0; i < 10; i++) {
		printf("%d, ", arr[i]);
	}

	// 3. 몇 번방에 있는지 찾고자 하는 정수 입력 받기
	printf("\n");
	printf("찾을 정수 입력 : ");
	int f;
	scanf("%d", &f);


	// 4. 이진 탐색 미사용, 입력한 정수가 몇 번 방인지 확인
	printf("\n이진탐색 미사용\n");
	int sw = 0;	// 스위치OFF
	int i;
	for (i = 0; i < 10; i++) {
		if (arr[i] == f) {
			printf("[%d]\n", i);
			sw = 1;
			break;
		}
	}
	if (i == 10) {		// break 사용 시 구현 가능
		printf("[-1]");
	}
	if (sw == 0) {
		printf("[-1]");
	}
	printf("\n\n");
	

	// 5. 이진탐색 사용, 입력한 정수가 몇 번 방인지 확인
	// 이진탐색==이분탐색
	printf("이진탐색 사용\n");
	printf("[%d]\n\n", binarySearch(arr, f, 0, 9));

	return 0;
}

 

 

3. 트리(Tree)
 : 노드들의 집합, 사이클이 없음

** 관련 용어
    노드(node): 트리를 구성하는 기본 원소
    루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
    부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
    자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
    형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
    리프 노드(leaf node/leaf/terminal node): 자식이 없는 노드
    경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
    길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 갯수
    깊이(depth): 루트 경로의 길이
    레벨(level): 루트 노드(1) 로 부터 노드까지 연결된 엣지의 수의 합
    높이(height): 가장 긴 루트 경로의 길이
    차수(degree): 각 노드의 자식의 갯수
    트리의 차수(degree of tree): 트리의 최대 차수
    크기(size): 노드의 개수
    너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

 

 

4. 이진 트리(Binary Tree)

 : 자식이 2개(== 주소부가 2개)

#include<stdio.h>
#include<stdlib.h>

typedef struct NODE {
	int data;
	struct NODE* left;
	struct NODE* right;
}N;

int main() {
	// 최상위 노트(root) 생성, 
	// 값 10 대입
	N* root = (N*)malloc(sizeof(N));
	root->data = 10;
	root->left = NULL;
	root->right = NULL;

	// 최상위 노드(root)의 left 노드 생성, 
	// 값은 scanf를 통해 직접 입력 받음
	N* node = (N*)malloc(sizeof(N));
	int data;
	scanf("%d", &data);
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	if (root->data > node->data) {
		root->left = node;
	}
	else {
		root->right = node;
	}

	return 0;
}

 

 

5. 이진트리 구현 예제
 : 못다한 부분은 다음시간에 배울 예정

 

** 이진 트리 순회 방법
    전위 순회(Pre-order traversal): root, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법

    중위 순회(In-order traversal): 왼쪽 자손, root, 오른쪽 자손 순서로 방문하는 순회 방법

    후위 순회(Post-order traversal): 왼쪽 자손, 오른쪽 자손, root 순서로 방문하는 순회 방법

#include<stdio.h>
#include<stdlib.h>

// 노드 생성을 위한 구조체 선언
typedef struct NODE {
	int data;
	struct NODE* left;
	struct NODE* right;
}N;

// 노드 생성
N* create(N* node, int data) {
	if (node == NULL) {
		node = (N*)malloc(sizeof(N));
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else {
		if (node->data > data) {
			node->left = create(node->left, data);
		}
		else {
			node->right = create(node->right, data);
		}
	}
	return node;
}

// 전위순회
void preorder(N* node) {
	if (node != NULL) {
		printf("%d ", node->data);
		preorder(node->left);
		preorder(node->right);
	}
}
// 중위순회
void inorder(N* node) {
	if (node != NULL) {
		inorder(node->left);
		printf("%d ", node->data);
		inorder(node->right);
	}
}
// 후위순회
void postorder(N* node) {
	if (node != NULL) {
		postorder(node->left);
		postorder(node->right);
		printf("%d ", node->data);
	}
}

// 노드 삭제
void del(N* node, int data) {

	// TODO

}

int main() {
	N* root = NULL;

	int act;
	while (1) {
		printf("1.노드생성 2.전위순회 3.중위순회 4.후위순회 5.노드삭제 6.종료\n");
		scanf("%d", &act);
		if (act == 1) {
			int data;
			printf("데이터입력: ");
			scanf("%d", &data);
			root = create(root, data);
		}
		else if (act == 2) {
			preorder(root); // 전위순회
			printf("\n");
		}
		else if (act == 3) {
			inorder(root); // 중위순회
			printf("\n");
		}
		else if (act == 4) {
			postorder(root); // 후위순회
			printf("\n");
		}
		else if (act == 5) {
			int data;
			printf("삭제할데이터입력: ");
			scanf("%d", &data);
			del(root, data);
		}
		else {
			printf("프로그램종료\n");
			break;
		}
	}

	return 0;
}

 

** 출력결과

① 노드생성

② 전위순회(Pre-order traversal) : 10 20 30

③ 중위순회(In-order traversal) : 10 20 30

④ 후위순회(Post-order traversal) : 30 20 10