원당컴퓨터학원

우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 된다.

- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영체제에서의 작업 스케줄링

priority_queue<T,Container,Compare> : 원하는 자료형 및 클래스 T를 통해 생성, 여기서 Container는 Vector와 같은 컨테이너 이며 Compare 는 비교 함수 클래스(단,Compare 조건에서 참인 것이 후 순위로 밀린다.)

push(element) : 우선순위 큐에 추가
pop() : 원소 삭제
top() : top에 있는 원소를 반환
empty() : 비어있으면 true 아니면 false
size() : 우선 순위 큐에 포함되어 있는 원소들의 수를 반환

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2630&sca=9010

- 배열에서 원소 삽입 방법을 살펴 보자.

질문)  위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삽입 하기 위해서 몇번 연산을 해야 할까?

- 배열에서 원소 삭제 방법을 살펴 보자.

질문)  위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삭제 하기 위해서 몇번 연산을 해야 할까?

- 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요
- 원소들의 이동 작업으로 인한 오버헤드로 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능상의 문제 발생
- 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐 
- 순차 자료구조에서의 연산 시간에 대한 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방법 필요

- 자료의 논라적인 순서와 물리적인 순서가 불일치

- 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결된느 방식

(물리적은 순서를 맞추기 위해 오버헤드가 발생하지 않음)

- 여러개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현

(크기 변경이 유연하고 더 효율적으로 메모리를 사용)

- 연결 자료구조에서 하나의 원소를 표현하기 위한 단위구조

- <데이터, 주소> 의 구조

    : 데이터 필드 - 원소의 값을 저장, 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성됨

    : 링크필드(주소) - 다음 노드의 주소를 저장, 포인터 변수를 사용하여 주소값을 저장

typedef struct _Node{
	int data;
    struct _Node *link;
}Node;

Node *Head;  //맨먼저 접근하기 위한 포인터
Node *CurPos;  //이동하기 위한 포인터

void LinkedLastAdd(Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos->link!=NULL) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link=data;
    }
}

void LinkOutput()
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
    	CurPos = Head;
        while(CurPos!=NULL) //마지막 위치까지 찾아가자
        {
            cout << CurPos->data << endl;
        	CurPos=CurPos->link;
        }
    }
}

void LinkedSelectInsert(Node *Select,Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        data->link = CurPos->link; ///추가하는 데이터에 선택된 위치의 다음 정보를 연결한다.
        CurPos->link=data;         ///현재 선택된 위치의 다음 위치 에 추가할 데이터를 연결한다.
    }
}

void LinkedSelectDelete(Node *Select)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
        if(Select == Head)
        {
            Head = Head.link; //Head를 삭제하는 경우 Head를 다음 위치에 이동시키자.
            elete Select;       ///선택된 객체는 삭제하자.
            return;
        }
    	CurPos = Head;
        while(CurPos->link!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link = Select->link; ///선택 된 데이터의 전 링크를 선택된 링크 위치로 이동시키자.
        delete Select;       ///선택된 객체는 삭제하자.
    }
}

#include <iostream>

using namespace std;

typedef struct _Node{
    int data;
    struct _Node *link;
} Node;

Node *Head;
Node *CurPos;

void LinkedLastAdd(Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos->link!=NULL) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link=data;
    }
}

void LinkedSelectInsert(Node *Select,Node *data)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	Head = data;
    }
    else{
    	CurPos = Head;
        while(CurPos!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        data->link = CurPos->link; ///추가하는 데이터에 선택된 위치의 다음 정보를 연결한다.
        CurPos->link=data;         ///현재 선택된 위치의 다음 위치 에 추가할 데이터를 연결한다.
    }
}

void LinkedSelectDelete(Node *Select)
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
        if(Select == Head)
        {
            Head = Head.link; //Head를 삭제하는 경우 Head를 다음 위치에 이동시키자.
            elete Select;       ///선택된 객체는 삭제하자.
            return;
        }
    	CurPos = Head;
        while(CurPos->link!=Select) //마지막 위치까지 찾아가자
        {
        	CurPos=CurPos->link;
        }
        CurPos->link = Select->link; ///선택 된 데이터의 전 링크를 선택된 링크 위치로 이동시키자.
        delete Select;       ///선택된 객체는 삭제하자.
    }
}

void LinkOutput()
{
    if(Head==NULL) //Head가 Null 이면 현재 아무것도 추가 되지 않은 경우이다.
    {
    	return;
    }
    else{
    	CurPos = Head;
        while(CurPos!=NULL) //마지막 위치까지 찾아가자
        {
            cout << CurPos->data << endl;
        	CurPos=CurPos->link;
        }
    }

    cout <<"\n\n";
}

int main()
{
    Node *tmp[10];
    for(int i=0;i<10;i++)
    {
        tmp[i] = new Node;
        tmp[i]->data = i+1;
        tmp[i]->link = NULL;
        LinkedLastAdd(tmp[i]);
    }

    LinkOutput();

    Node *add;
    add = new Node;
    add->data = 100;
    add->link = NULL;
    LinkedSelectAdd(tmp[6],add);
    LinkOutput();
    LinkedSelectDelete(add);
    LinkOutput();

    return 0;
}

인천 서구 검단신도시 원당컴퓨터학원

- 입력 : 외부에서 제공되는 자료가 0개 이상 제공된다.

- 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.( 즉 모든 입력에서 하나의 출력이 나오면 안됨)

- 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성

- 유한성 : 유한번의 명령을 수행 후 종료된다.

- 효율성 : 모든 과정은 명백하게 실행가능(검증가능) 한것이어야 한다.

- 정확성 : 적당한 입력에 대해서 유한 시간내에 답을 산출하는가? 를 판단.

- 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정

- 기억장소 사용량 : 수행 과정에서 필요한 저장공간

- 최적성 : 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가?

(단, 최적이란 가장  '잘 알려진' 이 아닌 '가장 좋은' 의 의미이다.)

- 시간 복잡도 : 최적의 시간으로 연산을 수행하는 알고리즘인가?

(단, 빠른 시간안에 해결이 된다고 해도 정확성이 떨어진다면? 혹은 정확성은 약간의 오차가 발생하는데 시간 차이가 많이 발생한다면?)

- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

- 가장 많이 사용하는 빅오표기법(O) : 알고리즘의 효율성을 상한선 기준으로 표기한다.(1부터 5000까지의 수가 있는 경우 어떤 수의 위치를 찾을때 최대 5000 번을 수행한다고 하면 빅오표기법에서 수행시간은 5000 이라고 생각하는 것이다.)

- O(1) : 입력 자료에 관계 없이 동일한 실행 시간을 갖는 알고리즘 

예)

int main()
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           scanf(“%d”,&b);
           printf(“%d”,a[b]);
}

- O(logN) : 입력자료가 N일경우 log2N의 시간

예)

int f(int n)
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           int s =0;
           int e = 9;
           while(1){
		if(s>=e) return -1; //찾지 못했다.
		int m = (s+e) /2;
 		if(a[m]==n) return  m;
		if(a[m]>n) s=m+1;
                      else e = m-1;
	} 

}

- O(N) : 입력 자료가 N일경우 N시간

예)

int f(int n)
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           for(int i=0;i<10;i++) if(a[i]==n) return I;
	return -1;
}

- O(NlogN) : 입력자료가 N일경우 Nlog2N의 시간

예)

int quick_Sort(int start, int end)
{
    int tempValue;
    if(start < end)
    {
        int left = start-1, right = end+1, pivot = a[start];
        while(left<right)
        {
            while(a[++left]<= pivot);
            while(a[--right] > pivot);
            if(left >= right) break;
	swap(a[left],a[right]);
        }
        swap(a[start],a[right]);
        quick_Sort(start, right-1);
        quick_Sort(right + 1, end);
    }
}

- O(N²) : 입력 자료가 N일경우 N * N 시간

예)

int f(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) printf( “%d “,i*j);
		printf(“\n”);
	}
}

- O(N³) : 입력 자료가 N일경우 N * N * N 시간

예)

int f(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) 
		{
			for(int k=1;k<=n;k++) printf( “%d “,i+j+k);
			printf(“\n”);
		}
	}
}

- O(2ⁿ) : 입력 자료가 2^n 의 시간

예)

int dfs(int y,int x,int state)
{
	if(y>=n) return 1;
	if(x>=n) y++,x=0;
	int res = dfs(y,x+1,0) + 1;
    	res +=dfs(y,x+1,1) +1;
	return res;
}

- #include <time.h> 또는 #include <ctime> 선언
- clock() 함수를 이용해 프로그램 수행시간 측정

예)

int startTime,endTime;
startTime = clock();
//프로세스 수행
endTime= clock();
printf(“%.3lf”,(double)(endTime-startTime)/CLOCKS_PER_SEC);
 
//여기서 CLOCKS_PER_SEC 는 1000의 값으로 define 되어 있다.

오늘도 최선을 다하는 우리 학생들을 응원합니다.

인천 서구 검단신도시 원당컴퓨터학원