보관/자료구조-개념

자료구조와 알고리즘

unhyepnhj 2024. 7. 3. 19:43

자료구조와 알고리즘

 

자료구조(data structure): 프로그램에서 자료들을 정리하여 보관하는 여러 가지 구조

- 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정됨

 

알고리즘(algorithm): 컴퓨터로 문제를 풀기 위한 단계적인 절차

- 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것

- 특정한 일을 수행하는 명령어들의 집합

 

<알고리즘의 조건>

  • 입력: 0개 이상의 입력이 존재해야 함
  • 출력: 1개 이상의 출력이 존재해야 함
  • 명백성: 각 명령어의 의미가 명확해야 함
  • 유한성: 한정된 수의 단계 후에 반드시 종료되어야 함
  • 유효성: 각 명령어들은 실행 가능해야 함

<알고리즘의 기술 방법>

  • 자연어
  • 흐름도(플로우차트)
  • 의사 코드(pseudo code): 알고리즘 기술에만 사용되는 언
  • 프로그래밍 언어

추상 자료형

 

자료형(data type): 데이터의 종류

- 정수, 실수, 문자열, 스택, 큐, 트리 등

- 데이터뿐 아니라 데이터 간 가능한 연산도 고려해야 함

- 복잡한 자료형을 구현할 때 연산은 연산자가 아닌 함수로 작성

 

추상 자료형(ADT, abstract data type): 자료형을 추상적(수학적)으로 정의한 것

- 실제적인 구현으로부터 분리되어 정의된 자료형

- 데이터나 연산이 무엇인지는 정의되지만 이들을 어떻게 구현할지는 정의되지 않음

- ADT가 구현될 때 보통 구현 세부 사항은 공개하지 않고 외부 인터페이스만을 공개

 

ex) 자연수를 나타내는 추상 자료형

//객체: 0부터 INT_MAX까지 순서화된 정수의 부분범위
//함수:
Nat_Number zero()	::=0
Nat_Number successor(x)	::= if(x==INT_MAX) return x
				else return x+1
Boolean is_zero(x)	::= if(x) return FALSE
				else return TRUE
Boolean equal(x, y)	::= if(x==y) return TRUE
				else return FALSE
Nat_Number add(x, y)	::= if((x+y) <= INT_MAX) return x+y
				else return INT_MAX
Nat_Number sub(x, y)	::= if(x<y) return 0
				else return x-y;

- ADT의 이름부터 시작

- ADT 안에는 객체(주로 집합 개념을 사용)와 함수들이 정의

알고리즘 성능 분석

 

1. 수행시간 측정 방법

- 알고리즘을 프로그래밍 언어로 작성하여 실행한 다음 그 수행시간을 측정

- 알고리즘을 직접 구현 및 테스트해야 함

- 반드시 똑같은 하드웨어를 사용하여 측정

- 실험되지 않은 입력에 대해서 수행시간을 주장할 수 없음

→ 문제점 많음

 

ex) 수행시간 측정 방법 예시

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

int main(void) {
	clock_t start, stop;
	double duration;
	start = clock();	//측정 시작
	for (int i = 0; i < 1000000; i++)
		;	//의미 없는 반복 루프
	stop = clock();
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	printf("수행시간은 %f초입니다.\n", duration);
	return 0;
}

- clock()이 반환한 시작 시스템 시간을 start, 종료 시스템 시간을 stop에 저장하고 이들의 차를 CLOCKS_PER_SEC으로 나누어 초 단위의 시간 측정하는 코드

 

2. 복잡도 분석 방법(complexity analysis)

- 알고리즘을 구현하지 않고 효율성 분석

- 실행 하드웨어나 소프트웨어 환경과 무관하게 알고리즘 효율성 평가 가능

→ good

 

시간 복잡도 함수

- 시간 복잡도(time complexity): 알고리즘의 수행시간 분석

- 공간 복잡도(space complexity): 알고리즘이 사용하는 기억 공간 분석

 

- 알고리즘 복잡도란 대체로 시간 복잡도를 의미

- 시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내지 않음

- 알고리즘을 구성하는 연산들의 수행 횟수를 표시

- 연산들의 수행 횟수는 입력의 개수에 따라 달라짐

- 시간복잡도 함수: T(n), 연산의 수를 입력 개수 n에 대한 함수로 나타낸 것

 

※빅오 표기법(Big-O)

- 입력 개수에 따른 기본 연산의 수행 횟수를 개략적으로 나타낸 것

- 알고리즘이 n에 비례하는 수행 시간을 가진다고 말하는 대신에 해당 알고리즘의 시간복잡도가 O(n)이라 함

두 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n)) 

 

- n과 T(n)의 관계에서 자료의 개수가 많은 경우 차수가 가장 큰 항이 가장 많은 영향을 미침(극한을 생각해보면 당연히..ㅎ)

- 기본 연산의 횟수가 다항식으로 표현되었을 때 최고차항의 차수만을 사용하여 표기

 

<많이 쓰이는 빅오 표기법>

  • O(1): 상수형
  • O(logn): 로그형
  • O(n): 선형
  • O(nlogn): 선형로그형
  • O(n^2): 2차형
  • O(n^3): 3차형
  • O(2^n): 지수형
  • O(n!): 팩토리얼형

- 빅오 표기법에 의한 알고리즘 수행 시간은 아래와 같음

 

- n이 작을 때는 상수항이나 계수도 수행시간에 영향을 미치므로 주의

빅오 표기법 이외의 표기법

- 빅오 표기법은 함수의 상한을 표시한 것이지만 상한은 여러 개 존재할 수 있음

- 빅오 표기법이 최소 차수 함수로 표기되었을 경우에만 유의미

- 이와 같은 문제점을 보완하기 위해 빅오메가와 빅세타 표기법이 있음

 

- 빅오메가(big omega) 표기법

- 함수의 하한을 표시 

두 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 |f(n)|>=c|g(n)|을 만족하는 2개의 상수 c와 n0이 존재하면 f(n)= Ω(g(n))

 

- 빅세타(big theta) 표기법

- 동일한 함수로 상한과 하한을 만들 수 있는 경우

- 3가지 표기법 중 가장 정밀(그러나 통상적으로 빅오 표기법을 많이 사용)

두 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 c1|g(n)|<=|f(n)|<=c2|g(n)|을 만족하는 3개의 상수 c1, c2, n0이 존재하면 f(n)= Θ(g(n))


최선, 평균, 최악의 경우

- 알고리즘 효율성은 주어지는 자료집합에 따라 다음 3가지 경우로 나누어 평가할 수 있음

  • 최악의 경우(worst case): 수행 시간이 가장 긴 경우
  • 최선의 경우(best case): 수행 시간이 가장 짧은 경우
  • 평균적인 경우(average case): 평균적인 수행 시간

- 최악의 경우가 시간 복잡도 척도로 많이 쓰임