[자료구조] 2장 자료구조 소개

2-1 자료구조

1. 자료구조

: 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조

2. 추상화?

: 어떤 시스템의 간략화 된 기술 또는 명세. 시스템의 핵심적인 구조나 동작에만 집중.

3. 자료형?

: 데이터의 집합과 연산의 집합.

4. 추상 자료형(ADT: abstract data type)

: 데이터 타입을 추상적으로 정의한 것.

  - 데이터나 연산이 무엇(what)인가를 정의.

  - 데이터나 연산을 어떻게(how) 구현할 것인지는 정의하지 않음

예. 자연수 추상 자료형

  ▶ 추상 자료형을 프로그래밍 언어로 구현한 것이 자료구조!!

       - 추상 자료형의 데이터: 구조체 사용

       - 추상 자료형의 연산: 함수 사용

2-2 알고리즘

1. 알고리즘

: 컴퓨터로 문제를 풀기위한 단계적인 절차.

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

2. 알고리즘의 조건(5)

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

3. 알고리즘 표현 방법(4)

  - 자연어: 가독성 굳. 단어들이 정확히 정의되어 있지 않으면 전달이 모호해짐.

  - 흐름도(flow chart): 직관적임. 복잡한 알고리즘의경우 복잡해짐.

  - 유사 코드(pseudo-code): 알고리즘의 고수준 기술 방법. 자연어와 프로그래밍 언어 사이의 표현.

                                       가장 많이 사용. 알고리즘의 핵심적인 내용에만 집중하기좋음.

  - 특정한 프로그래밍 언어(c언어, java): 가장  정확한 알고리즘.

                                                   많은구체적인 사항들이 알고리즘 핵심 내용을 방해할 수도 있음.

2-3 성능 평가

1. 실행 시간 측정 방법

• 두 개의 알고리즘 실제 실행 시간을 측정하는 것
• 실제 구현 필요
• 동일한 하드웨어 사용

  - clock 함수 사용: 호출되을 때의 시각 반환. CLOCK_PER_SEC 단위.

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

2. 알고리즘 복잡도 분석 방법

• 직접 구현하지 않고 수행 시간을 분석하는 것
• 알고리즘이 수행하는 연산 회수 비교
• 일반적으로 연사의 횟수는 n 함수.

  - 종류(2): 시간 복잡도 분석(수행 시간 분석)/공간 복잡도 분석(수행 시 필요로 하는 메모리 공간 분석)

3. 시간 복잡도

: 입력 개수 n에 대한 함수. T(n).

 - 고려하는 연산: 산술, 대입, 비교, 이동, 반환

ArrayMax(A, n)
	tmp <- A[0];				// 1번의 대입 연산
    for i<-1 to n-1 do			// 루프 제어 연산은 제외
    	if tmp < A[i] then		// n-1번의 비교 연산
        	tmp <- A[i];		// n-1번의 대입 연산(최대)
    return rmp;					// 1번의 반환 연산
    
    // 1 + n-1 + n-1 + 1 = 2n
    // 최대 총 연산 수는 2n번 이다.

● 빅오 표기법

  : 차수가 가장 큰 항이 가장 영향을 크게 미치고, 다른 항들은 상대적으로 무시됨.

이러한 경우 O(n^2)로 나타냄.

   - 빅오 표기법의 정의:

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

  - 빅오 표기법 예시

    - f(n) = 5 → O(1)

    - f(n) = 2n + 1  → O(n)

    - f(n) = 3n^2 +100  →  O(n^2)

    - f(n) = 2^n  → O(2^n)

4. 최선, 평균, 최악의 경우

: 실행 시간은 입력에 따라 다를 수 있음.

  - 최선의 경우: 수행 시간이 가장 빠름. 의미 없는 경우가 많음.

  - 평균의 경우: 수행 시간이 평균적임. 계산하기 상당히 어려움

  - 최악의 경우: 수행 시간이 가장 늦음. 가장 널리 사용됨. 계산도 쉽고, 응용에 따라 중요한 의미를 가짐.

int sequentialSearch(int list[], int n, int key){
	for(int i=0; i<n ; i++)
    	// 탐색에 성공하면 키 값의 인덱스 반환
        if(list[i]==key) return i;
    retrun-1;	// 탐색에 실패하면 -1반환
}

  + 최선의 경우: O(1)

  + 평균의 경우: (1+2+...+n)/n = (n+1)/2 = O(n)

  + 최악의 경우: O(n)

 

 

💡이번 장에서 기억할 점
  1. 자료구조는 추상화 자료형(ADT)를 구현한 것이다.
  2. 연산의 횟수를 셀 때 가장 중요시해야하는 것은 입력의 개수이다. 이는 함수의 형태로, 최고차항이 빅오 표현법으로 표현된다.