[자료구조] 자료구조와 알고리즘

1. 자료구조

 자료구조란?

- 자료마다 효율적인 정리 규칙이 있음 -> 컴퓨터에서 자료들을 정리하고 조직화 하는 여러 가지 구조

- 자료 : data --- 컴퓨터 ---> 구조( 저장공간(memory) + 읽기,쓰기,삽입,삭제,탐색등의 연산 )

- 자료구조는 지원되는 연산에 따라 다양한 자료구조가 존재함

- ex ) 변수 : a = 5; // 쓰기연산 , print(a); // 읽기 연산 -> 변수 이름을 통해서 접근함

-> 유한한 횟수의 연산 후 정답을 출력함

 

자료구조의 분류

1. 단순 자료구조 : 정수, 실수, 문자와 같이 대부분의 프로그래밍 언어에서 기본적으로 제공함

 

2. 복합 자료구조 : 여러 개의 자료들을 모은 창고와 같음

- 자료에 접근 하는 방법 : 직접 접근(배열) / 순서 접근(연결 리스트)

-> 복합 자료구조는 창고의 형태에 따라 나뉨

 

선형 자료구조

- 항목들을 순서적으로 나열하여 저장함

- 항목 접근 방법에 따라 다시 세분화

( 리스트 : 가장 자유로운 선형 자료구조 / 스택, 큐, 덱 : 항목 접근 맨 앞이나 맨 뒤로 제한됨)

 

비선형 자료구조

- 자료들이 보다 복잡한 연결 관계를 갖고있음

- 트리 : 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조를 표현하기에 적합한 구조

- 그래프 : 지하철 노선도나 소셜 네트워크서비스의 인맥 지도, 인터넷 망 등을 표현할 수 있는 복잡한 형태의 자료구조

 

자료구조의 활용

- 가장 대표적인 응용은 정렬과 탐색

- 정렬 : 주어진 자료들을 어떤 기준을 바탕으로 순서대로 나열함. 정렬은 알고리즘이 중요하지만 효율적인 정렬을 위해선 다양한 자료구조의 활용이 필수적임.

- 탐색 : 컴퓨터에서 가장 핵심이 되는 작업 중 하나임. 효율적인 탐색을 위해서는 반드시 적잘한 자료구조와 그에 따른 알고리즘을 사용해야 함.

 

2. 알고리즘

- 알고리즘 : 어떤 문제를 해결하는 절차

프로그램 = 자료구조 + 알고리즘

- 대부분의 프로그램은 데이터를 처리하고있고 이들 자료는 자료구조를 사용하여 표현하고 저장됨. 주어진 문제를 처리하는 절차, 알고리즘이 필요함

-> 따라서 프로그램은 자료구조와 알고리즘으로 구성됨.

 

ex) 성적 처리 프로그램 ( 최고 성적 찾는 프로그램 )

- 자료구조 : 많은 학생들의 성적을 처리하기 위해 배열 사용

- 알고리즘 : 변수에 배열 첫 번째 값 대입 -> 배열의 각 요소와 비교함 -> 만약 배열의 요소가 크다면 변수에 저장

 

알고리즘의 조건

- 입력 : 0개 이상의 입력이 존재해야 함. (필수 아님)

- 출력 : 1개 이상의 출력이 존재해야 함.

- 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 함.

- 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 함. ( ex : 무한 반복하는 명령어는 알고리즘이 아님)

- 유효성 : 각 명령어들은 실행 가능한 연산이어야 함. ( ex : 0으로 나누는 연산은 알고리즘이 아님)

 

알고리즘 기술 방법

1. 영어나 한국어와 같은 자연어

- 자연어를 사용하므로 편리하지만 의미가 애매할 수 있음

- 명령어로 쓰이는 단어들을 명백하게 해야함.

ex) 최대값을 찾는 알고리즘을 자연어로 표현
array_max(A,n)
1. 배열 A의 첫 번째 요소를 변수 tmp에 복사함
2. 배열 A의 다음 요소들을 tmp 변수의 값과 하나씩 비교하며, 더 클 경우 tmp 변수에 값을 복사함
3. 배열 A의 모든 요소를 비교했으면 tmp를 반환함

2. 흐름도

- 절차를 매우 명확하게 표현할 수 있음. (특허 명세서 등에서 많이 사용됨)

- 알고리즘이 조금만 복잡해져도 매우 복잡하게 표시되는 단점이 있음.

3. 유사 코드

- 자연어보다 더 체계적 / 프로그래밍 언어보다 덜 엄격한 언어

- 알고리즘의 표현에 흔히 사용되는 방법

- 특정 프로그래밍 언어로 구현할 때의 여러 문제들을 감출 수 있음

- 알고리즘의 핵심적인 내용에 대한 표현에만 집중할 수 있음

array_max(A,n)

tmp<-A[0];
for i<-1 to n-1 do
	if tmp < A[i]
    then tmp <- A[i];
return tmp;

4. 특정한 프로그래밍 언어

-  알고리즘의 가장 정확한 기술 가능

- 실제 구현시 많은 구체적인 사항들이 내용 이해를 방해할 수 있음

//최대값 찾는 알고리즘

int array_max(int score[],int n)
{
    int tmp = score[0];
    for(int i = 1; i<n;i++)
    {
    	if( score[i] > tmp)
        	tmp = score[i];
    }
    return tmp;
}

 

3. 추상 자료형

추상화란?

- 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념이나 기능을 간추려 내는 것

- 어떤 시스템의 간략화 된 기술 또는 명세

- 시스템의 핵심적인 구조나 동작에만 집중하는 것

-> 좋은 추상화를 위해 정보은닉기법이 개발되었고 추상 자료형의 개념으로 발전됨.

 

추상 자료형

- 추상화된 자료형, 즉 추상적으로 정의한 자료형을 의미함

- 구체적으로는 데이터의 집합과 자료에 가해지는 연산들의 집합에 대한 수학적인 명세

 

ex) 가방(Bag)의 추상 자료형

데이터 : 중복된 항목을 허용하는 자료들의 저장소. 항목들은 특별한 순서가 없이 개별적으로 저장됨.
연산 :
1. Bag() : 비어있는 가방을 새로 만듦.
2. insert(e) : 가방에 항목 e를 넣음.
3. remove(e) : 가방에 e가 있는지 검사하여 있으면 이 항목을 꺼냄.
4. contains(e) : e가 들어있으면 True를 없으면 False를 반환함.
5. count() : 가방에 들어 있는 항목들의 수를 반환함.

 

추상 자료형

- 추상화된 자료형, 즉 추상적으로 정의한 자료형을 의미함

- 구체적으로는 데이터의 집합과 자료에 가해지는 연산들의 집합에 대한 수학적인 명세

 

4. 알고리즘의 성능 분석

실행시간을 측정하는 방법

- 두 개의 알고리즘의 실제 실행 시간을 측정하는 것

- 실제로 구현하는 것이 필요

- 동일한 하드웨어를 사용해야 함.

 

clock 함수 사용 : clock_t clock(void);

- 호출되었을 때의 시스템 시각 반환

- CLOCKS_PER_SEC 단위

ex) 실행 시간 측정 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void main()
{
	clock_t start, finish;
    double duration;
    start = clock();
    // 실행 시간을 측정하고자 하는 코드 . . . .
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("%f 초입니다.\n",duration);
}

 

알고리즘의 복잡도 분석방법

- 복잡도 분석 : 알고리즘을 직접 구현하지 않고 대략적인 효율성을 살펴보는 것

-> 구현하지 않고도 알고리즘의 효율성을 평가할 수 있음

1. 시간 복잡도 : 알고리즘의 실행시간 분석

- 산술, 대입, 비교, 이동의 기본적인 연산 고려

- 알고리즘 수행에 필요한 연산의 개수를 계산

-입력의 개수 n에 대한 함수 -> 시간 복잡도 함수, T(n)

2. 공간 복잡도 : 알고리즘이 사용하는 기억 공간 분석

 

시간 복잡도 함수

n의 제곱을 구하는 문제

알고리즘	A	B	C
유사코드	sum <- n * n	for i <- 1 to n do    sum <- sum + n	for i <- 1 to n do    for j <- 1 to n do       sum <- sum + 1
연산 횟수	대입연산 : 1 곱셈연산 : 1	대입연산 : n+1 곱셈연산 : n	대입연산 : n^2+n+1 곱셈연산 : n^2
복잡도 함수	T(n) = 2	T(n) = 2n+1	T(n) = 2n^2 + n + 1

 

빅오 표기법

- 차수가 가장 큰 항이 절대적인 영향

- 다른 항들은 상대적으로 무시

 

빅오 표기법의 정의

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

 

빅오 표기법의 종류

- O(1) : 상수형

- O(log n) : 로그형

- O(n) : 선형

- O(nlog n) : 선형로그형

- O(n²) : 2차형

- O(n³) : 3차형

- O(2ⁿ) : 지수형

- O(n!) : 팩토리얼형

 

빅오 표기법에 따른 실행시간 차이

 

 

최선, 평균, 최악의 경우

순차 탐색의 최선, 평균, 최악의 경우

int search(int list[], int n, int key) {
	for(int i = 0 ; i < n ; i ++ )
    	if ( list[i] == key ) return i;
    return -1;
}

- 최선의 경우 : O(1)

- 최악의 경우 : O(n)

- 평균적인 경우 : (1+2+...n)/n=(n+1)/2 ∴ O(n)