pridiot

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

큐(Queue)

• 선입선출(FIFO: First-In First-Out) 입출력 형태를 갖는다.
• 삽입과 삭제가 일어나는 위치가 다르다.
  = 삽입과 삭제가 큐의 양 끝에서 일어난다.
   rear(후단)  : 큐에서 삽입이 일어나는 곳
   front(선단)  : 큐에서 삭제가 일어나는 곳

큐의 연산

객체 : 0개 이상의 요소들로 구성된 선형 리스트
연산 :
    create(max_size) ::= 최대 크기가 max_size인 공백 큐를 생성
    init(q) ::= 큐 초기화
    is_empty(q) ::=
    	if(size == 0) return TRUE;
        else return FALSE:
    is_full(q) ::=
    	if(size == max_size) return TRUE;
        else return FALSE;
    enqueue(q, e) ::=
    	if(is_full(q)) ERROR_QUEUE_FULL;
        else q의 끝에 e를 추가
    dequeue(q) ::=
    	if(is_empty(q)) ERROR_QUEUE_EMPTY;
        else q의 맨 앞에 있는 e를 제거하여 반환
    peek(q) ::=
    	if(is_empty(q)) ERROR_QUEUE_EMPTY;
        else q의 맨 앞에 있는 e를 읽어서 반환

enqueue(Q, x) ::=
    rear<-(rear + 1) % MAX_QUEUE_SIZE;    // 배열 크기를 넘어가지 않게 하기 위해 큐 사이즈로 나눠줌
    Q[rear]<-x;
dequeue(Q) ::=
    front<-(front + 1) % MAX_QUEUE_SIZE;
    return Q[front];

원형 큐일 경우 삽입과 삭제 알고리즘이 달라진다.

• enqueue : 삽입 연산. 큐의 맨 뒤에 새로운 요소를 추가
• dequeue : 삭제 연산. 큐의 맨 앞에 있는 요소가 삭제되면서 반환
• peek : 맨 앞에 있는 요소를 읽어서 반환 (삭제가 일어나지 X)
• is_empty : 큐가 공백 상태인지 검사
• is_full : 큐가 포화 상태인지 검사
• create : 큐 생성
• init : 큐 초기화

큐의 종류

• 선형 큐(linear queue)
  - front와 rear이 증가만 하기 때문에 경우에 따라 배열의 앞부분을 사용할 수 없음
  - 주기적으로 모든 요소를 앞쪽으로 이동시켜야 하기 때문에 비효율적
• 원형 큐(circular queue)
  선형 큐의 단점을 보완하기 위해 처음과 끝을 연결한 개념.
  공백 상태 : ``front == rear``
  포화 상태 : front가 rear보다 한 칸 앞에 있는 경우
  
  - 공백상태와 포화상태를 구분하기 위한 방법
      1. 항상 큐의 한자리 이상을 비우기
      2. 원소의 개수를 저장하는 변수를 지정

큐의 응용

• 버퍼
• 인쇄 작업 큐
• 운영체제의 작업 스케줄링

대기 행렬 이론, 큐잉 이론(queueing theory)

 : 대기 행렬을 수학적으로 다루는 이론. 경영관리, 산업공학, 통신 네트워크의 성능 분석 및 설계(패킷 스케줄링 정책, 자원관리)등 여러 분야에서 사용한다.

덱(Deque, double-ended queue)

  큐의 전단(front) 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다.

덱의 연산

객체 : n개의 element형의 요소들의 순서 있는 모임
연산 :
    create() ::= 덱 생성
    init(dq) ::= 덱 초기화
    is_empty(dq) ::= 덱이 공백상태인지 검사
    is_full(dq) ::= 덱이 포화상태인지 검사
    add_front(dq, e) ::= 덱의 앞에 요소 추가
    add_rear(dq, e) ::= 덱의 뒤에 요소 추가
    delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭제
    delete_rear(dq) ::= 덱의 뒤에 있는 요소를 반환한 다음 삭제
    get_front(dq) ::= 덱의 앞에 있는 요소를 삭제하지 않고 반환
    get_rear(dq) ::= 덱의 뒤에 있는 요소를 삭제하지 않고 반환

• add_front : 덱의 앞에 요소를 추가
• add_rear : 덱의 뒤에 요소를 추가
• delete_front : 덱의 앞에 있는 요소가 삭제되면서 반환
• delete_rear : 덱의 뒤에 있는 요소를 삭제되면서 반환
• get_front : 덱의 앞에 있는 요소를 반환 (삭제되지 X)
• get_rear : 덱의 뒤에 있는 요소를 반환 (삭제되지 X)
• is_empty : 덱이 공백 상태인지 검사
• is_full : 덱이 포화 상태인지 검사
• create : 덱 생성
• init : 덱 초기화

덱의 연산 비교

  덱은 스택과 큐의 연산들을 모두 가지고 있다.

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

스택(stack)

• 후입 선출(LIFO : Last-In First-Out)의 입출력 형태를 갖는다.
  자료의 출력 순서가 입력 순서의 역순이어야 할 때 많이 사용된다.
• 입출력이 맨 위에서만 일어나고 스택의 중간에서는 데이터 삭제가 불가능하다.

    요소(element)  : 스택에 저장되는 것

     공백 스택(empty stack)  : 요소가 하나도 없는 스택

스택의 연산

객체 : 0개 이상의 원소를 가지는 유한 선형 리스트
연산:
    create(size) ::= 최대 크기가 size인 공백 스택을 생성
    is_full(s) ::=
    	if(스택의 원소수 == size) return TRUE;
        else return FALSE;
    is_empty(s) ::=
    	if(스택의 원소수 == 0) return TRUE;
        else return FALSE;
    push(s, item) ::=
    	if(is_full(s)) return ERROR_STACKFULL;
        else 스택의 맨 위에 item을 추가
    pop(s) ::=
    	if(is_empty(s)) return ERROR_STACKEMPTY;
        else 스택의 맨 위에 원소를 제거해서 반환
    peek(s) ::=
    	if(is_empty(s)) return ERROR_STACKEMPTY;
        else 스택의 맨 위의 원소를 제거하지 않고 반환

• push : 삽입 연산. 요소가 스택의 가장 위에 쌓인다. (스택이 가득 차면 오류)
• pop : 삭제 연산. 가장 위에 쌓여있는 요소가 삭제되면서 반환된다. (스택이 비어있으면 오류)
• peek : 가장 위에 있는 요소를 읽어오는 연산 (삭제가 일어나지 X)
• is_empty : 스택이 공백 상태인지 검사
• is_full : 스택이 포화 상태인지 검사
• create : 스택 생성
• init : 스택 초기화

스택 구현 방식

스택응용

• 괄호 검사
• 후위 표기 수식의 계산
• 미로 찾기

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

팩토리얼(거듭제곱 값) 계산

  반복적인 방법이 순환적인 방법에 비하여 속도가 더 빠르다.

1. 반복문을 사용하는 방법

double power_1(double x, int n)
{
	int i;
	double result = 1.0;
	
	for (i = 0; i < n ; i++)
		result *= x;
	return (result);
}

한 번의 루프마다 한 번의 곱셈이 일어나므로 시간 복잡도는 $O(n)$이 된다.

2. 순환을 사용하는 방법

double power_2(double x, int n)
{
	if (n == 0)
		return 1;
	else if ((n % 2) == 0)	// n이 짝수인 경우
		return power_2((x * x), (n / 2));
	else	// (n % 2) != 0 -> n이 홀수인 경우 
		return x * power_2((x * x), ((n - 1) / 2));
}

$x^n = (x^2)^{\frac{n}{2}}$ 의 공식을 이용하는 방법이다.

n이 짝수인 경우에는 $x^2$을 먼저 계산한 후에 이 값을 $\frac {n}{2}$제곱하고,

n이 홀수인 경우에는 $x^2$을 $\frac{n-1}{2}$제곱한 뒤 $x$를 한번 더 곱해야 한다.

함수를 한번 호출할 때마다 n승, $\frac{n}{2}$, $\frac{n}{4}$승으로 점점 문제의 크기가 약 절반으로 줄어든다.

  시간 복잡도

약 k번의 순환 호출이 일어난다. $n = 2^k$이므로 양변에 log를 취하면 $log_2n = k$가 된다.

한 번의 순환 호출이 일어날 때마다 약 1번의 곱셈과 1번의 나눗셈이 일어나므로 전체 연산의 개수는 $k = log_2n$에 비례하게 되어 시간 복잡도는 $O(log_2n)$이 된다.

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

반복과 순환

  기본적으로 반복과 순환은 문제 해결 능력이 같으며 대부분의 경우 순환 알고리즘과 반복 알고리즘은 서로 대체될 수 있다. 특히 순환 호출이 끝에서 이뤄지는 것을 꼬리 순환(tail recursion)이라 하는데, 이를 반복 알고리즘으로 쉽게 대체할 수 있다. 대부분의 언어가 순환을 지원하지만 FORTRAN, COBOL과 같은 고전적인 언어에서는 지역변수가 없거나 있더라도 정적으로 할당되므로 순환이 불가능하다. (함수 호출마다 새로운 지역변수를 만들지 못하면 이전 호출과 구분할 수 없어 순환 호출이 불가능하다.)

• 반복(iteration) : 반복 구조로 되풀이하는 방법
• 순환(recursion) : 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법
  - 특정 문제에서 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있다.
  - 함수호출을 하게 되므로 대부분 반복에 비해 수행 속도가 떨어진다.
  - 알고리즘의 정의가 순환적으로 되어있는 경우 유용함
    ex) 팩토리얼, 피보나치 수열, 이항 계수 계산, 이진트리 알고리즘, 이진 탐색, 하노이 탑 등

   순환의 원리 : 문제의 일부를 해결한 다음 나머지 문제에 대하여 순환 호출을 한다.

    분할정복(divide and conquer)  : 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법 

순환의 종류

1. 머리 순환(head recursion) : 순환 호출이 순환 함수 처음에서 이뤄지는 경우
2. 꼬리 순환(tail recursion) : 순환 호출이 순환 함수 맨 끝에서 이뤄지는 경우 → 반복문으로 쉽게 변환 가능
3. multi recursion : 여러 군데에서 자기 자신을 호출하는 경우

순환 호출 과정

1. 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 
    활성 레코드(activation record)  : 함수를 위한 시스템 스택에서의 공간
2. 준비가 끝나면 호출된 함수의 시작 위치로 점프하여 수행 시작
3. 호출된 함수가 끝나면 시스템 스택에서 복귀 주소를 추출하여 호출한 함수로 되돌아감

순환 알고리즘의 구조

[반환형] [함수이름] (매개변수)
{
    if (종료조건)
    {
    	// 순환을 멈추는 부분
    }
    else
    {
    	// 순환호출 하는 부분
    }
}

종료 조건이 없으면 무한히 반복하게 되므로 주의한다.

순환 알고리즘 문제

• 팩토리얼(거듭제곱) : https://pridiot.tistory.com/260
• 피보나치
• 하노이의 탑

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

•  자료구조(data structure)  : 자료들을 정리하여 보관하는 여러 가지 구조
•  알고리즘(algorithm)  : 컴퓨터로 문제를 풀기 위한 단계적인 절차, 특정한 일을 수행하는 명령어들의 집합

알고리즘이 되기 위한 조건

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

알고리즘을 기술하는 방법

1. 자연어
   ex) 한글, 영어
2. 흐름도(flowchart)
3. 의사코드(pseudo-code)
   대입 연산자를 ←로 사용한다는 점이 다름
4. 프로그래밍 언어

알고리즘의 성능 분석

•  수행 시간 측정 방법  : ``time.h``헤더의 ``clock( )``함수를 이용해서 호출 프로세스에 의하여 사용된 CPU 시간을 계산
  - 알고리즘이 복잡한 경우 테스트하기가 어려움
  - 여러 가지 알고리즘을 비교하는 경우 반드시 똑같은 하드웨어를 사용하여 수행 시간을 측정해야 함
  - 소프트웨어 환경에 따라 결과가 달라질 수 있음
    ex) 일반적으로 컴파일 언어가 인터프리터 언어보다 빠름
  - 테스트하지 않은 입력에 대해서는 수행 시간을 보장할 수 없음
•  알고리즘의 복잡도 분석 방법(complexity analysis) 
  : 대부분의 경우 알고리즘의 복잡도는 시간 복잡도를 의미한다.
  • 시간 복잡도(time complexcity)
    - 알고리즘의 수행 시간 분석.
    - 절대적인 수행 시간이 아닌 알고리즘을 이루고 있는 연산들이 몇 번 수행되는지 숫자로 표시한다.
    - (보통 입력 값에 따라 수행 횟수가 변하게 되므로)연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 $T(n)$이라고 표기한다.
  • 공간 복잡도(space complexity) : 알고리즘이 사용하는 기억공간 분석

빅오(big O) 표기법

•  n의 값에 따른 함수의 상한 값을 나타내는 방법이다.
• 시간 복잡도 함수에서 불필요한 정보(함수의 증가에 별로 기여하지 못하는 항을 생략)를 제거한 것으로, 알고리즘 분석을 쉽게 할 목적으로 사용한다.
• 다항식으로 표현되었을 경우 다항식의 최고 차항만을 남기고 다른 항들과 상수항을 버리는 방법으로 간단하게 구할 수 있다. (logn은 생략하면 X)
• 최소 차수 함수로 표기되었을 경우만 의미가 있다.
• 상한을 표기한 것이므로 상한이 여러 개가 존재하는 경우에 문제

빅 오메가(big omega) 표기법

n의 값에 따른 함수의 하한 값을 나타내는 방법이다.

빅 세타(big theta) 표기법

• 동일한 함수로 상한과 하한을 만들 수 있는 경우에 사용할 수 있는 방법이다.
• 3가지 표기법 중 가장 정밀하다.

시간 복잡도 함수의 수행 시간(빅오 표기법)

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

최선, 평균, 최악의 경우

  똑같은 알고리즘도 주어지는 입력에 따라 수행시간이수행 시간이 달라질 수 있다. 평균적인 경우는 산출하기 어렵기 때문에 대부분 최악의 경우의 수행 시간이 알고리즘의 시간 복잡도 척도로 많이 사용된다.

• 최선의 경우(best case) : 수행시간이 가장 적은 경우
• 평균적인 경우(average case) : 알고리즘의 모든 입력과 각 입력이 발생하는 확률을 고려한 평균적인 수행시간
• 최악의 경우(worst case) : 자료 집합 중에서 알고리즘의 수행 시간이 가장 오래 걸리는 경우

추상화(abstraction)

• 어떤 시스템의 간략화된 기술, 또는 명세로서 시스템의 핵심적인 구조나 동작에만 집중하는 것.
• 좋은 추상화는 사용자에게 중요한 정보는 강조되고 중요하지 않은 구현 세부 사항은 제거되는 것이다. 이를 위하여 정보 은닉 기법(information hiding)이 개발되었고 추상 자료형의 개념으로 발전되었다.

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

• 자료형을 추상적으로 정의한 것
• 데이터나 연산이 무엇인지는 정의되지만 어떻게 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.
  - ADT안에는 객체(objects)와 함수(functions)들이 정의된다.
  - 함수에는 매개변수, 반환형, 함수가 수행하는 기능의 기술 등이 포함된다.
  - ``::=``는 "~으로 정의된다"는 의미이다.
• 정보은닉의 한 방법으로도 사용된다.
  : ADT가 구현될 때 보통 구현 세부사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개하게 된다. ADT의 사용자는 구현 세부사항이 아닌 인터페이스만 사용하기 때문에 추상 자료형의 구현 방법은 언제든지 안전하게 변경될 수 있다. 또한 인터페이스만 정확하게 지켜진다면 ADT가 여러 가지 방법으로 구현될 수 있다.
• 객체 지향 언어에서는 클래스 개념을 사용하여 ADT를 구현한다.
  - ADT의 객체는 클래스의 속성, 연산은 클래스의 멤버 함수로 구현된다.
  - private나 protected 키워드를 이용하여 내부 자료의 접근을 제한할 수 있다.
  - 클래스는 계층구조(상속 개념 사용)로 구성될 수 있다.

기본 자료형

• 기초 자료형 : char, int, float, double ...
• 파생 자료형 : 배열, 포인터
• 사용자 정의 자료형 : 구조체, 공용체, 열거형