자료구조 정리 #알고리즘

▶큐

🔎검색
순차 검색 =선형 검색
이진 검색 = 이분 검색 = 보간 검색
▶트리
트리 용어
이진트리
일반트리 → 이진트리
이진트리 종류
완전 이진 트리
포화 이진 트리
편향 이진트리
힙
MAX HEAP = 최대 히프
MIN HEAP = 최소 히프
힙 삽입 연산
힙 삭제 연산
이진트리 구현
배열
리스트 (포인터)
🔎이진 트리 순회 (D L R)
전위 순회 preorder
중위 순회 inorder
후위 순회 postorder
중위 표기식 (중위 순회)
후위 표기식 (후위 순회)
응용 프로그램 :: 파일 (후위 순회)
🔎 이진 탐색 트리
탐색 연산
삽입 연산
삭제 연산

🔎정렬 알고리즘
버블정렬
삽입정렬
선택정렬
병합정렬
퀵정렬
힙정렬
최대히프 : 원소의 개수 만큼 삭제 연산을 수행하여 내림차순으로 정렬
최소히프 : 원소의 개수 만큼 삭제 연산을 수행하여 오름차순으로 정렬
▶하노이탑 (FOR문 변경)
▶그래프
그래프 정의
무방향 그래프
방향 그래프
1-1. 인접행렬
1-2.희소행렬
2. 인접리스트
3.인접배열
🔎그래프 순회
1. DFS 깊이우선탐색 (스택) /위 → 아래
2. BFS 너비우선탐색 (큐) /좌 → 우
🔎신장트리
신장트리
최소 신장 트리
1. 쿠르스칼 알고리즘(1,내림차순)
1-2) 쿠르스칼 알고리즘 (2 오름차순0
2. 프림 알고리즘

 

 

▶큐

 

🔎검색

 

순차 검색 =선형 검색

 

일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법

배열, 연결리스트로 구현된 순차 자료구조에서 사용하는 검색

비효율적이지만 알고리즘이 구현이 쉬움

 

첫번째 원소부터 마지막 원소까지 순서대로 키가 일치하는 원소가 있는지 비교하며 찾음

 

• 정렬되지 않은 자료

하나하나 순서대로 같은 값이 있는지 비교해나가면 됨

 

 

• 정렬된 자료

키 값보다 크면 더이상 없는 것이므로 검색 실패를 빠르게 알 수 있음

Copy

#include <stdio.h>
typedef int element;

 //정렬되지 않은 자료 

void sequentialSearch1(element a[], int n, int key) {
	int i = 0;
	printf("\n %d를 검색하라! ->> ", key);
	while (i<n && a[i] != key) i++;
	if (i<n) printf("%d 번째에 검색 성공! \n\n", i + 1);
	else   printf("%d번째에 검색 실패! \n\n", i + 1);
}

void main() {
	element a[] = { 8, 30, 1, 9, 11, 19, 2 };
	int n = 7;

	sequentialSearch1(a, n, 9);  // 배열 a의 n개 원소 중에서 탐색키가 9인 원소 검색
	sequentialSearch1(a, n, 6);  // 배열 a의 n개 원소 중에서 탐색키가 6인 원소 검색

	getchar();
}

Copy

#include <stdio.h>
typedef int element; 

// 정렬된 자료 = 평균 비교 횟수가 반으로 줄어듬 ( 이미 정렬이 되어있음)

void sequentialSearch2(element a[], int n, element key) {
	int i = 0;
	printf("\n %d를 검색하라! ->> ", key);
	while (a[i] < key) 
		 i++; 
	if (a[i] == key)  printf("%d번째에 검색 성공!\n\n", i + 1); //찾은경우
	else  printf("%d번째에 검색 실패! \n\n", i + 1); // 큰 경우 = 같은 경우가 없음
}

void main() {
	element a[] = { 1, 2, 8, 9, 11, 19, 29 };
	int n = 7;

	sequentialSearch2(a, n, 9); // 배열 a의 n개 원소 중에서 탐색키가 9인 원소 검색
	sequentialSearch2(a, n, 6); // 배열 a의 n개 원소 중에서 탐색키가 6인 원소 검색

	getchar();
}

 

Copy

//공통으로 입력한 값 있는지 찾는 알고리즘

#include <stdio.h>
#define MAX 10


int main() {
	
	int a, b;
	int u, d;
	int UP[MAX], DN[MAX];

	printf("첫번째 줄 입력 데이터 수 : ");
	scanf_s("%d", &u);
	printf("첫번째 줄 데이터 %d 개 입력: ", u);
	for (a = 0; a < u; a++) {
		scanf_s("%d", &UP[a]);
	}

	printf("두번째 줄 입력 데이터 수 : ");
	scanf_s("%d", &d);
	printf("첫번째 줄 데이터 %d 개 입력: ", d);
	for (b = 0; b < d; b++) {
		scanf_s("%d", &DN[b]);
	}

	for (b = 0; b < d; b++) {
		for (a = 0; a < u; a++) {
			if (UP[a] == DN[b])
				printf(" %d 공통으로 있음 \n", UP[a]); //값 넣을것
		}
	}
	return 0;
}

Copy

//과제[]

#include <stdio.h>
#define MAX 10

Search(int u, int d);

int main() {

	int u, d;

	printf("첫번째 줄 입력 데이터 수 : ");
	scanf_s("%d", &u);

	printf("두번째 줄 입력 데이터 수 : ");
	scanf_s("%d", &d);

	Search(u, d);

	return 0;
}

Search(int u, int d) // (1) 함수 호출 식으로 바꾸기 
{
	int a;
	int b;
	int UP[MAX], DN[MAX];
	
	printf("첫번째 줄 데이터 %d 개 입력: ", u);
	for (a = 0; a < u; a++) {
		scanf_s("%d", &UP[a]);
	}

	printf("두번째 줄 데이터 %d 개 입력: ", d);
	for (b = 0; b < d; b++) {
		scanf_s("%d", &DN[b]);
	}

	for (b = 0; b < d; b++) {
		for (a = 0; a < u; a++) {
			if (UP[a] == DN[b])
				printf("UP[%d]와 DN[%d]에 %d이 공통으로 있음 \n",a,b,UP[a]);
//(2) UP은 첫번째 줄, DN 두번째 줄 인덱스 출력하기
		}
	}


}

 

이진 검색 = 이분 검색 = 보간 검색

 

정렬된 자료에 대해서 수행하는 검색 방법

중간에 있는 값을 기준으로 잡고

찾을 값 / 기준값 비교 ( 크면 오른쪽, 작으면 왼쪽 ) → 계속해서 기준값 변경해감.

기준값 :: 배열의 중간에 있는 값 == // middle ← (begin + end / 2)

 

 

** 재귀함수, 순한문 두가지 형태 코드 있음

 

▶트리

• 사이클이 있음

트리 용어

 

이진트리

일반트리 → 이진트리

 

이진트리 종류

완전 이진 트리

• 노드 위치가 포화 이진트리에서 노드 1~n까지의 위치와 완전히 일치하는 이진트리

포화 이진 트리

• 모든 레벨에 노드가 포화 상태로 차 있음

편향 이진트리

• 모든 노드가 왼쪽 or 오른쪽 중 한 방향으로만 서브트리를 가지고 있는 트리

 

힙

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰, 가장 작은 노드를 찾기 위해서 만든 자료구조

MAX HEAP = 최대 히프

• 루트 노드(키값)가 가장 큼

MIN HEAP = 최소 히프

• 루트 노드(키값)가 가장 작음

힙 삽입 연산

• 노드를 확장시킴
• 현재 위치에서 부모노드와의 값 크기를 비교함
• 교환하거나 해서 자리 확정시킴

힙 삭제 연산

• 루트 노드의 원소만 삭제 가능함
• 완전 이진 트리를 유지해야되기 때문에 마지막노드 n번 노드를 삭제
• 루트 노드에 임시 저장 한 후 제자리를 찾아가면 됨

 

이진트리 구현

배열

리스트 (포인터)

 

🔎이진 트리 순회 (D L R)

• 모든 원소를 빠트리거나 붕복하지 않고 처리하는 연산
• 루트 방문 시기에 따라 구분됨

전위 순회 preorder

• 루트 노드를 먼저 방문

중위 순회 inorder

• 루트 노드를 중간에 방문

후위 순회 postorder

• 루트 노드를 마지막에 방문

 

중위 표기식 (중위 순회)

후위 표기식 (후위 순회)

응용 프로그램 :: 파일 (후위 순회)

• 후위 순회 하면서 폴더 용량을 계산함

Copy

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

typedef struct treeNode {	// 트리의 노드 구조 정의
	int size;				// 데이터 필드
	struct treeNode* left;	// 왼쪽 서브 트리에 대한 링크 필드
	struct treeNode* right;	// 오른쪽 서브 트리에 대한 링크 필드
} treeNode;

int AmountSize = 0;

// size를 루트 노드의 데이터 필드로 하여 왼쪽과 오른쪽 서브 트리를 연결하는 연산
treeNode* makeRootNode(int size, treeNode* leftNode, treeNode* rightNode) {
	treeNode* root = (treeNode*)malloc(sizeof(treeNode));
	root->size = size;
	root->left = leftNode;
	root->right = rightNode;
	return root;
}

// 각 폴더 크기를 계산하기 위한 후위 순회 연산
int postorder_AmountSize(treeNode* root) {
	if (root) {
		postorder_AmountSize(root->left);
		postorder_AmountSize(root->right);
		AmountSize += root->size;
	}
	return AmountSize;
}

void main() {
	treeNode* F11 = makeRootNode(50, NULL, NULL);
	treeNode* F10 = makeRootNode(40, NULL, NULL);
	treeNode* F9 = makeRootNode(45, NULL, NULL);
	treeNode* F8 = makeRootNode(30, NULL, NULL);
	treeNode* F7 = makeRootNode(0, NULL, NULL);
	treeNode* F6 = makeRootNode(65, F10, F11);
	treeNode* F5 = makeRootNode(100, NULL, NULL);
	treeNode* F4 = makeRootNode(0, F8, F9);
	treeNode* F3 = makeRootNode(0, F6, F7);
	treeNode* F2 = makeRootNode(0, F4, F5);
	treeNode* F1 = makeRootNode(0, F2, F3);

	printf("\n\n 공학계열 모금액 : %d M \n", postorder_AmountSize(F2));

	AmountSize = 0;
	printf("\n 자연계열 모금액 : %d M \n", postorder_AmountSize(F3));

	AmountSize = 0;
	printf("\n 학과 전체 모금액 : %d M \n", postorder_AmountSize(F1));

	getchar();
}

🔎 이진 탐색 트리

• 원소의 크기에 따라 노드 위치를 정의 한 것

서로 다른 유일한 키를 가짐

R 는 루트 키보다 작음

L은 루트 키 보다 커야됨

• 왼쪽 < 루트 < 오른쪽

탐색 연산

• 루트에서 시작
• 탐색할 키 값 ↔ 루트노드 키값 비교
• 키값 = 루트노드키값 : 탐색연산성공
• 키값 < 루트노드키값 왼쪽 서브트리로 탐색연산수행
• 키값 > 루트노드키값 오른쪽 서브트리로 탐색연산수행

삽입 연산

• 탐색 연산 수행해야됨
• 삽입 할 원소랑 같은 원소가 있으면 삽입 불가능함
• 탐색수행이 실패되는 그 자리에 원소를 삽입함

삭제 연산

• 탐색연산을 수행 (삭제 노드 위치를 알아야함)
• 탐색하여 찾은 노드를 삭제함
• 이제 후속처리를 해줘야됨 (이진 탐색 트리 유지해줘야됨)

1. 단말노드 (차수=0)
2. 자식 노드 한개

• 부모노드 자리를 자식노드에게 물려준다

1. 자식 노드 두개

• 부모노드 자리를 자식노드에게 물려준다
• 후계자 선택방법 :

삭제 노드에 위치해야할 값은 왼쪽 서브 트리에 있는 노드들의 값보다 커야하고, 오른쪽 서브 트리에 있는 노드들의 키값보다는 작아야한다.

출처:

https://songeunjung92.tistory.com/31

[은져미]

1. 왼쪽 서브트리 : 가장 큰 자손노드 선택
2. 오른쪽 서브트리 : 가작 작은 자손노드 선택

 

 

🔎정렬 알고리즘

• 데이터를 일정한 규칙에 따라 다시 나열하는 것

버블정렬

• 인접한 두개씩 비교한다.

삽입정렬

• 미정렬 첫번째를 정렬된 곳과 비교

선택정렬

• 미정렬 된 곳에서 선택 후 미정렬 된 첫번째 와 교환

병합정렬

• 배열을 두 개로 쪼개서 (최소 단위 1개로 분할) 정렬한 뒤 다시 병합하는 작업
• *분할정복방법
• 분할 → 정복 → 결합

• 병합정렬 알고리즘 분석함

퀵정렬

기준 값 (피벗)을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할 하여 정렬

• 분할 → 정복
• 가운데 원소를 피봇으로 정한다.
• L : → / 피봇보다 크거나 같은 원소 찾기
• R : ← / 피봇보다 작은 원소 찾기 ( 피벗을 넘어 갈 수 있음)
• LR이 만나기 전에 조건이 충족되면 각각 원소끼리 교환함 (피벗이 설정된 건 아님)
• LR이 만나 진행되지 않으면 그 원소와 피봇을 교환함
• 모든 부분 집합의 크기가 1 이하가 되면 전체 퀵 정렬을 종료함
• ㅅ

힙정렬

• 히프에서는 가장 큰 원소가 루트 노드가 된다. 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환 (삭제연산 )

최대히프 : 원소의 개수 만큼 삭제 연산을 수행하여 내림차순으로 정렬

1. 삽입 연산을 이용해서 최대히프 구성
2. 삭제 연산을 통해서 메모리에 다시 정렬 ㄹ

최소히프 : 원소의 개수 만큼 삭제 연산을 수행하여 오름차순으로 정렬

▶하노이탑 (FOR문 변경)

Copy

#include <stdio.h>


int n, start, work, target;

void hanoi_01(int n, int start, int work, int target);
void hanoi_02(int n, int start, int target, int work);
void hanoi_03(int n, int work, int start, int target);

int main()
{
	start = 'A';
	work = 'B';
	target = 'C';

	for (int n = 3; n > 0; n--) {
		if (n == 1) hanoi_01( n,  start,  work,  target);
		else if (n == 3 ) hanoi_02(n - 1, start, target, work);
		else hanoi_03(n - 1, work, start, target);
	}
}


void hanoi_01(int n, int start, int work, int target) {
	printf("%c에서 원반 %d를 %c로 옮김 \n", start, n, target);
}

void hanoi_02(int n, int start, int target, int work) {
	//printf("%c에서 원반 %d를 %c로 옮김 \n", start, n, target);
}

void hanoi_03(int n, int work, int start, int target) {
	//printf("%c에서 원반 %d를 %c로 옮김 \n", start, n, target);
}

 

 

 

▶그래프

• 사이클이 없음

그래프 정의

• 현상이나 사물을 정점 + 간선으로 표현한 것
• Graph G = (V, E)
• 인접힌다 : 두 정점이 간선으로 연결되어 있는 상태

무방향 그래프

• 방향이 없는 그래프

방향 그래프

• 방향이 있는 그래프
• 진입차수, 진출차수

1-1. 인접행렬

• 2차원 배열로 표현함

1-2.희소행렬

대부분의 값이 0인 경우

 

2. 인접리스트

• 연결리스트를 이용해 표현함

3.인접배열

 

🔎그래프 순회

• 모든 정점에 방문하는 것

1. DFS 깊이우선탐색 (스택) /위 → 아래

• 최대한 깊이 탐색하다가 갈 곳 이 없으면 갈림길 간선으로 되돌아와서 다른 방향으로 탐색을 계속 반복한다.
• 가장 마지막에 만난 갈림길 간선으로 돌아가야되기때문에 후입 선출의 스택 사용

2. BFS 너비우선탐색 (큐) /좌 → 우

• 정점과 인접한 정점 중에 방문하지 않은 정점을 차례대로 방문함 이 과정을 계속 반복

 

🔎신장트리

신장트리

• 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리
• 정점이 n개면 간선은 n-1개 존재

최소 신장 트리

• 신장 트리 중에서 간선의 가중치 합이 가장 작은 트리
• 조건 : 무방향 연결 그래프
• 트리 : 사이클이 없는 연결 그래프

1. 쿠르스칼 알고리즘(1,내림차순)

• 내림차순 or 오름차순 정렬부터 시작
• 가중치가 가장 높은 간선을 제거한다.
• 사이클을 만들지 않으면서 추가

1-2) 쿠르스칼 알고리즘 (2 오름차순0

• 내림차순 or 오름차순 정렬부터 시작
• 가중치가 가장 작은 간선부터 선택
• 사이클을 만들지 않으면서 추가

2. 프림 알고리즘

• 간선 정렬하지 않고 시작
• 정점에서 시작하여 (본인이 선택)
• 선택한 정점에 부속된 모든 간선 중 가중치가 가장 낮은 간선을 연결해서 트리를 확장