01. 자료구조와 알고리즘

Posted on: 2019년 03월 06일 2019년 03월 06일
Categories: 강의자료, 자료구조

자료구조 : 데이터의 표현 및 저장 방법
1. 선형구조
  1. 리스트
  2. 스택
  3. 큐
2. 비선형구조
  1. 트리
  2. 그래프
3. 파일구조
  1. 순차파일
  2. 색인파일
4. 단순구조
  1. 정수
  2. 실수
  3. 문자
  4. 문자열
알고리즘 : 표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법
알고리즘의 성능분석 방법
1. 시간복잡도(Time Complexity) : 속도
2. 공간 복잡도(Space Complexity) : 메모리 사용량
시간복잡도 예1 : 순차 탐색(Linear Search)의 경우
1. 최악의 경우(Worst Case) : T(n) = n
2. 평균적인 경우(Average Case)
  1. 탐색 대상이 존재하지 않는 경우 연산 횟수 : n
  2. 탐색 대상이 존재하는 경우 연산 횟수 : n / 2
  3. T(n) = (n + n / 2) / 2 = 3 / 4 * n
시간복잡도 예2 : 이진 탐색(Binary Search)의 경우
1. 최악의 경우(Worst Case) : T(n) = log(n)
2. 평균적인 경우(Average Case) : …
빅-오 표기법(Big-Oh Notation) :
1. 시간 복잡도 함수를 단순화 시켜 근사치(approximation)로 표현
2. 다항식에서 최고차항의 차수가 빅-오
3. 최고차항의 계수와 최고차항 외의 나머지 식은 제거
대표적인 빅-오
1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n^2)
6. O(n^3)
순차 탐색과 이진 탐색의 비교
1. 순차 탐색 : O(n)
2. 이진 탐색 : O(log n)

순차 탐색 소스 코드(S001_LinearSearch.c)

#include <stdio.h>

int LSearch(int ar[], int len, int target){
	int i;
	for (i = 0; i < len; i++){
		if (ar[i] == target){
			return i;
		}
	}
	return -1;
}

int main(void){
	int arr[] = { 3, 5, 2, 4, 9 };
	int idx;

	idx = LSearch(arr, sizeof(arr) / sizeof(int), 4); //4 대신 7로 수정한 후 재실행

	if (idx == -1){
		printf("탐색 실패\n");
	}
	else{
		printf("타겟 저장 인덱스 : %d \n", idx);
	}

	return 0;
}

#include <stdio.h>

int LSearch(int ar[], int len, int target){

int i;

for (i = 0; i < len; i++){

if (ar[i] == target){

return i;

}

return -1;

}

int main(void){

int arr[] = { 3, 5, 2, 4, 9 };

int idx;

idx = LSearch(arr, sizeof(arr) / sizeof(int), 4); //4 대신 7로 수정한 후 재실행

if (idx == -1){

printf("탐색 실패\n");

}

else{

printf("타겟 저장 인덱스 : %d \n", idx);

}

return 0;

}

이진 탐색 소스 코드(S001_BinarySearch.c)

#include <stdio.h>

int BSearch(int ar[], int len, int target){
	int first = 0;
	int last = len - 1;
	int mid;

	while (first <= last){
		mid = (first + last) / 2;

		if (target == ar[mid]){
			return mid;
		}
		else{
			if (target < ar[mid]){
				last = mid - 1;
			}
			else{
				first = mid + 1;
			}
		}
	}

	return -1;
}

int main(void){
	int arr[] = { 1, 3, 5, 7, 9 };
	int idx;

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 7); //7 대신 4로 수정한 후 재실행

	if (idx == -1){
		printf("탐색 실패\n");
	}
	else{
		printf("타겟 저장 인덱스 : %d \n", idx);
	}
}

#include <stdio.h>

int BSearch(int ar[], int len, int target){

int first = 0;

int last = len - 1;

int mid;

while (first <= last){

mid = (first + last) / 2;

if (target == ar[mid]){

return mid;

}

else{

if (target < ar[mid]){

last = mid - 1;

}

else{

first = mid + 1;

}

return -1;

}

int main(void){

int arr[] = { 1, 3, 5, 7, 9 };

int idx;

idx = BSearch(arr, sizeof(arr) / sizeof(int), 7); //7 대신 4로 수정한 후 재실행

if (idx == -1){

printf("탐색 실패\n");

}

else{

printf("타겟 저장 인덱스 : %d \n", idx);

}

최악의 이진 탐색 소스 코드(S001_BSWorstOpCount.c)

#include <stdio.h>

int BSearch(int ar[], int len, int target){
	int first = 0;
	int last = len - 1;
	int mid;
	int opCount = 0;

	while (first <= last){
		mid = (first + last) / 2;

		if (target == ar[mid]){
			return mid;
		}
		else{
			if (target < ar[mid]){
				last = mid - 1;
			}
			else{
				first = mid + 1;
			}
		}
		opCount += 1;
	}

	printf("비교 연산 횟수 : %d\n", opCount);
	return -1;
}

int main(void){
	int arr1[500] = { 0, };
	int arr2[5000] = { 0, };
	int arr3[50000] = { 0, };
	int idx;

	idx = BSearch(arr1, sizeof(arr1) / sizeof(int), 7); //arr1 대신 arr2 또는 arr3 으로 수정한 후 재실행

	if (idx == -1){
		printf("탐색 실패\n");
	}
	else{
		printf("타겟 저장 인덱스 : %d \n", idx);
	}
}

#include <stdio.h>

int BSearch(int ar[], int len, int target){

int first = 0;

int last = len - 1;

int mid;

int opCount = 0;

while (first <= last){

mid = (first + last) / 2;

if (target == ar[mid]){

return mid;

}

else{

if (target < ar[mid]){

last = mid - 1;

}

else{

first = mid + 1;

}

opCount += 1;

}

printf("비교 연산 횟수 : %d\n", opCount);

return -1;

}

int main(void){

int arr1[500] = { 0, };

int arr2[5000] = { 0, };

int arr3[50000] = { 0, };

int idx;

idx = BSearch(arr1, sizeof(arr1) / sizeof(int), 7); //arr1 대신 arr2 또는 arr3 으로 수정한 후 재실행

if (idx == -1){

printf("탐색 실패\n");

}

else{

printf("타겟 저장 인덱스 : %d \n", idx);

}

문제
1. 문제 01-1 빅-오 구하기(p036)
2. 문제 01-2 빅-오의 증명(p044)

whan0623

517