Algorithm Design - Intro/Data structure

---

Intro

이전에도 타과의 알고리즘 강의를 청강해서 들었으나 실습이 포함된 실습과목을 통해 직접 코드 설계하는 실력도키우고 설계학점도 채울겸 알고리즘 설계 수업을 수강하게 되었고 해당 수업 내용을 정리하는 시리즈가 될 것이다.

우선 알고리즘이란 특정문제를 해결하기 위해 기술한 일련의 명령문이다. 본격적으로 구체적인 알고리즘들을 학습하기전에 복습겸 간단한 기초와 데이터 구조에 대해서 살펴보자.

알고리즘의 요건으로는 크게 세가지 정도로 볼 수 있다.

- 완전성과 명확성: 수행결과와 순서가 완전하고 명확하게 명세되어야하고 순수하게 알고리즘이 지시하는대로 실행하기만하면 의도한 결과가 얻어져야하는 것이다.
- 입력과 출력: 입력은 알고리즘이 처리해야할 대상으로 제공되는 데이터이고 출력은 입력데이타를 처리하여 얻은 결과이다.

- 유한성: 유한한 단계 뒤에는 반드시 종료해야한다. 물론 그렇지 않은 알고리즘도 존재하지만 유의미하다고 보기 힘들 것이다.

---

성능분석

1) 공간 복잡도 (space complexity)
- 알고리즘을 실행시켜 완료하는데 필요한 총 저장 공간: Sa = Sc + Se
• Sc:고정공간
명령어 공간, 단순 변수, 복합 데이타 구조와 변수, 상수
• Se : 가변 공간
크기가 변하는 데이타 구조와 변수들이 필요로 하는 저장 공간, 런타임 스택(runtime stack)을 위한 저장 공간

 

2)시간 복잡도 (time complexity)
- 알고리즘을 실행시켜 완료하는데 걸리는 시간: Ta = Tc + Te
• Tc:컴파일시간 

• Te:실행시간
단위 명령문 하나를 실행하는데 걸리는 시간, 실행 빈도수 (frequency count)

 

factorial을 구현하는 두가지 방식의 complexity를 분석해보면 아래와 같다.

 

대표적인 복잡도 카테고리를 정리하면 아래와 같다.

---

주소의 이해

Fixed – static 데이터는 code area, Global/static area를 포함하는 데이터영역에 저장된다.
예를들어 프로그램 코드나 Const 선언, Literal Values (“Hello” 또는 12345), Global 선언등이 포함된다.
Nonfixed – dynamic 데이터는 스택에서 지속적으로 grow와 shrink를 반복하며 사용된다.
stack과 heap 구조를 이용한 형태이다.

 

32비트 컴퓨터라는 것은 주소공간이 4Gbytes라는 것이다.

-주소 값을 표현할 때 4바이트가 필요하다. (2^32)
- Fetch-Execute cycle
• 레지스터의 크기 -> 4바이트
• 메모리에서 CPU로 fetch할때 4바이트씩 fetch
- 프로그램 실행시 스택의 요소 크기도 4바이트

char a,b,c;
char str1[4];
char str2[5];
short s1,s2;
double d;
int i,j,k;

위 변수들을 스택에 표현하면 아래와 같다.

 

이번에는 함수를 호출할때 데이터들이 어떻게 저장되고 반환되는지 살펴보자.

int main(void)
{
    int num = 3, val;
    val = fact(num);
    printf("fact = %d\n", val);
    return 0;
}

int fact(int n)
{
    if (n==0)
        return 1;
    else
        return fact(n-1)*n;
}

---

스택과 큐

스택은 기본적으로 Last In First Out, 즉 LIFO 구조를 갖고 있다.

 

큐는 First in First Out, 즉 FIFO 구조를 갖고 있다.

---