![]()
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..
![]()
1.1 자료구조와 알고리즘 프로그램 = 자료구조 + 알고리즘 자료구조 : 프로그램에서 자료들을 정리하여 보관하는 여러 구조 알고리즘 : 컴퓨터로 문제를 풀기 위한 단계적인 절차 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 기술한 것 특정한 일을 수행하는 명령어들 중 알고리즘이 되기 위한 조건들을 만족하는 집합 ● 알고리즘 정의 입력(0개 이상), 출력(1개 이상), 명백성(의미는 모호하지 않고 명확), 유한성(한정된 수의 단계 후에는 반드시 종료), 유효성(종이, 연필 또는 컴퓨터로 실행 가능한 연산) ● 알고리즘 기술법 한글이나 영어 같은 자연어 - 모호성 제거 필요 흐름도(flowchart) - 알고리즘이 복잡할수록 기술하기 어려움 의사 코드(pseudo-co..
