전체 글

5.1 큐 추상 데이터 타입 ● 큐: 뒤(rear)에서 새로운 데이터가 추가되고 앞(front)에서 데이터가 하나씩 삭제되는 구조로 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out) 방식을 따른다. - 스택은 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다. - 따라서 스택에선 top이라는 변수 하나만 사용됐지만 큐에서는 front와 rear 두 변수가 사용된다. - enque는 rear쪽에 삽입 연산을, deque는 front쪽에 삭제 연산을 수행한다. - 은행에서 대기하는 사람들의 대기열, 공항에서 이륙하는 비행기들 등 많은 분야에서 큐를 사용한다. - 컴퓨터와 주변기기 사이에서 속도 차이를 해결하여 CPU를 효율적으로 사용하기..

01 (1) 02 (2) 03 10, 20 04 (4) 05 (1)일 때 공백상태, (3)일 때 포화상태 06 (3) 07 (1) 08 1 → 1, 2 → 1, 2, 3 → 1, 2 → 1, 2, 4 → 1, 2, 4, 5 → 1, 2, 4 09 A a, b, c B d → A a, b B d, c → A a, b, c B d → A a, b, c B 'empty' 10 #include #include #define MAX_ARR_SIZE 6 typedef int element; typedef struct{ element *data; int capacity; int top; }StackType; void init_stack(StackType *s){ s->top=-1; s->capacity = 1; s-..

4.4 스택의 응용: 괄호 검사 문제 괄호는 항상 쌍이 되게끔 사용하여야 한다. 대괄호 [ ], 중괄호 { }. 소괄호 ( ) 등이다. 조건1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 조건2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 된다. 왼쪽 괄호들을 스택에 쌓다가 오른쪽 괄호가 나오면 스택의 최상단부터 괄호가 매칭되는지 검사한다. 괄호짝이 맞는지(조건 3 위배), 스택이 비어 있지는 않는지(조건 1, 조건2 위배), 마지막 괄호까지 처리했는데 스택이 비어있지 않은 지(조건1 위배)를 체크해 준다. #include #include #include #define MAX_STACK_S..

4.1 스택이란? ● 스택 : 입출력이 최상단에서만 이루어지는 선형 나열 구조로, 가장 최근에 들어온 입력값이 가장 먼저 나가는 후입선출(LIFO: Last-In First-Out) 방식을 따른다. - 입출력이 이뤄지는 최상단을 스택 상단(stack top), 반대쪽인 바닥을 스택 하단(stack bottom)이라고 한다. - 스택에 저장되는 것을 요소(element), 스택이 요소가 하나도 없이 비어있으면 공백 스택(empty stack)이라고 한다. - 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 긴요하게 사용된다. 컴퓨터에서 함수 호출이 이루어질 때, 호출된 함수는 실행이 끝나면 자신을 호출했던 함수로 되돌아가야 한다. 이 때 시스템 스택은 함수가 호출될 때마다 활성 레코드(activ..

01 (4) 4*10*20 = 800 02 (4) 1000 + 4* 10 = 1040 03 (2) (1) 40 (2) 80 (3) 40 (4) 40 04 int main(){ int two[10]; for(int i=0; iwords); free(t); return 0; }

17. 순환적인 이항계수 / 반복적인 이항계수 (반복에서는 팩토리얼만 구현 후 이항계수 공식에 대입) int binomial(int n,int k){ if(k==0 || k==n) return 1; else return binomial(n-1,k-1)+binomial(n-1,k); } int factorial(int n){ int result=1; for(int i=1;i

3.5 포인터 ● 포인터의 개념, 포인터와 관련된 연산자, 다양한 포인터 포인터 : 다른 변수의 주소를 가지고 있는 변수. * 연산자 - 간접참조 연산자 (역참조 연산자) &연산자 - 주소 연산자 int a = 100; int *p; p = &a; //a의 주소를 p에 저장. *p = 200 // p가 가르키는 주소의 값을 200으로 변경 printf("a= %d",a); // 결과값 : a= 200 int *p 외에 float *pf, char *pc처럼 다양한 자료형에 대한 포인터를 선언할 수 있다. ● 널 포인터 널 포인터: 어떤 객체도 가리키지 않는 포인터. 포인터를 사용하는 코드를 작성할 때 포인터가 널 포인터인지 점검하는 예외처리가 필요하다. if( p == NULL ){ //C언어에서는 널 ..

3.1 배열 ● 배열의 개념 배열 : 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용하는 자료형으로 대부분의 프로그래밍 언어에서 기본적으로 제공되는 자료형이다. - 연속적인 메모리 공간이 배열에 할당되기 때문에 인덱스(index) 번호를 사용하여 쉽게 데이터에 접근이 가능하다. ● 배열 ADT - 배열은 의 쌍으로 이루어진 집합으로 정의할 수 있다. 즉, 인덱스에 대응하는 값(value)이 존재한다. - 수학적으로 배열은 인덱스→값으로의 1:1 매핑(mapping)에 해당된다. - create(size) 함수로 size개의 요소를 저장하는 배열을 생성한다. - 주어진 인덱스에 값을 저장하는 set연산 / 인덱스로부터 대응되는 값을 추출하는 get연산이 있다. * get함수는 배열과 인덱스를 받고,..

2.1 순환의 소개 순환(recursion): 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 ● 순환 호출의 내부적인 구현 - 함수가 자기 자신을 호출하는 것도 다른 함수를 호출하는 것과 동일. - 복귀 주소를 시스템 스택에 저장하고, 호출되는 함수를 위한 매개변수와 지역변수를 스택으로부터 할당받음. (함수호출마다 새로운 지역변수를 만들기 때문에 이전 호출과 구분할 수 있음) - 이 시스템 스택에서의 공간을 활성 레코드(active record)라 함. - 호출된 함수가 끝나면, 시스템 스택에서 복귀주소를 추출하여 호출한 함수로 되돌아감. - 순환호출이 중첩될 때마다 시스템 스택에 활성화 레코드가 쌓임. ● 순환 알고리즘의 구조 int factorial (int n){ i..