본문 바로가기

분류 전체보기

 (894)
5-2 재귀 알고리즘 분석 1. 재귀 알고리즘 분석하기 - recur 함수는 함수안에서 재귀호출 2회 수행 #include //재귀 함수 recur void recur(int n) { if(n>0) { recur(n-1); printf("%d\n",n); recur(n-2); } } int main() { int x; printf("정수를 입력하세요:"); scanf("%d",&x); recur(x); return 0; } 1.1 하향식 분석 - 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사 - 꼭대기(top)부터 분석 - recur(4) 더보기 1) recur(3) 을 실행 2) 4를 출력 3) recur(2)를 실행 1-2 상향식 분석 - 아래쪽부터 쌓아 올리며 분석 recur(1) 더보기 1) rec..
5-1 재귀의 기본 1. 재귀 알아보기 재귀적(recursive) - 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의 - 무한으로 존재하는 자연수의 재귀적 정의 1) 1은 자연수 입니다, 2) 자연수 n의 바로 다음 수도 자연수 입니다. 2. 순차곱셈 구하기 - 음이 아닌 정수의 순차곱셈(factorial)의 재귀적 정의 더보기 1. 0!=1 2. n>0이면 n!=n*(n-1)! - 순차곱셈의 결과를 재귀적으로 구하여 출력 #include //정수 n의 순차곱셈값을 반환 int factorial(int n) { if(n>0) return n*factorial(n-1); else return 1; } int main() { int x; printf("정수를 입력하세요:"); scanf("%d",&x); pr..
4-2장 큐란? 1. 큐 알아보기 큐(Queue) - 데이터를 일시적으로 쌓아 놓은 자료구조 - 선입선출(FIFO :First in First out) : 가장 먼저 넣은 데이터를 가장 먼저 꺼냄 - 인큐(en-queue) : 큐에 데이터를 넣는 작업 - 디큐(de-queue) : 데이터를 꺼내는 작업 - 프런트(front) : 데이터를 꺼내는 쪽 - 리어(rear) : 데이터를 넣는 쪽 2. 배열로 큐 만들기 ex) 배열의 프런트(front)부터 4개(19,22,37,53)의 데이터가 들어 있는 상태 -배열 이름 que -que[0]~que[3]까지의 데이터가 저장 1) 24 인큐 - 리어(rear)의 데이터가 저장된 que[3]의 다음 요소 que[4]에 24 저장 - 복잡도 O(1) 2) 19 디큐 - que[0]..
4-1 스택이란? 1. 스택 알아보기 스택(stack) - 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 - LIFO(Last In First Out) : 가장 나중에 넣은 데이터를 가장 먼저 꺼냄 - 푸시(Push) : 스택에 데이터를 넣는 작업 - 팝(Pop) : 스택에서 데이터를 꺼내는 작업 - 꼭대기(Top) : 푸시, 팝을 하는 위치 - 바닥(bottom) : 스택에 가장 밑바닥 부분 2. 스택 만들기 2-1 스택 구조체 IntStack - 스택을 관리하는 구조체 //스택을 구현하는 구조체 typedef struct { int max; //스택 용량 int ptr; //스택 포인터 int *stk; //스택 첫 요소에 대한 포인터 }IntStack; 1) 스택으로 사용할 배열을 가리키는 stk - 스택으로 ..
함수 포인터 함수 포인터 - 함수를 가리키는 포인터 - 함수 포인터의 자료형은 가리키는 함수에 따라 다름 ex) int를 받아들여 double을 반환하는 함수 double func(int); int형 인수를 받아들여 double형 값을 반환하는 함수에 대한 포인터 double(*fp)(int); - 함수에 대한 포인터를 사용하여 '덧셈표'와 '곱셈표' 출력 //덧셈, 곱셈표 #include //x1과 x2의 합 int sum(int x1, int x2) { return x1+x2; } //x1와 x2의 곱 int mul(int x1,int x2) { return x1*x2; } //표 출력 void kuku(int(*calc)(int,int)) { for(int i=1; i 포인터가 가리키는 함수의 실행으로 얻은 계..
3-3장 이진 검색 1. 이진 검색 다루기 - 이진 검색(binary search) - 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 ex) 오름차순으로 정렬된 배열 {5,7,15,28,29,31,39,58,68,72,95}에서 39 검색 - 배열의 중앙에 위치한 요소인 a[5](31)부터 검색 - 검색값 39는 중앙 요소 a[5](31)보다 큰값 ( 뒤쪽에 존재) -> 검색 대상을 뒤쪽에 5개 (a[6]~a[10])로 좁힘 - 검색값 39는 중앙 요소 a[8](68)보다 작은 값 (앞쪽에 존재) -> 검색 대상을 앞쪽에 2개 (a[6]~a[7])로 좁힘 -> 그 중 앞쪽에 위치한 요소인 a[6](39)을 선택하여 원하는 값인지 확인 -> 검색 성공 - pl : 이진 검색 범위의 맨앞 인덱스 , 0으로..
3-2장 선형 검색 1. 선형 검색 다루기 - 배열에서의 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색 -ex) 배열 {6,4,3,2,1,2,8}에서의 검색 -2를 검색 : 검색 성공 - 5를 검색 : 검색 실패 - 선형 검색에서 배열 검색의 종료 조건 1) 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색 실패) - i == n이 성립하는 경우 2) 검색할 값과 같은 요소를 발견한 경우 (검색 성공) - a[i] == key가 성립하는 경우 - 요소 개수가 n인 배열 a에서 값이 key인 요소를 검색하는 코드 nt i =0; while(1) { if(i ==n) { return -1; //검색 실패 if(a[i] =-key) return 1; //검색 성공 i++; } - 요소 개..
3-1장 검색 알고리즘이란? 1. 검색과 키 ex) 1) 국적이 한국인 사람을 찾습니다. 2) 나이가 21세 이상 27세 미만인 사람을 찾습니다. 3) 어떤 낱말과 발음이 가장 비슷한 이름의 사람을 찾습니다. - 특정 항목에 주목 - 키 : 주목하는 항목 1) 키값과 일치하도록 지정(한국) 2) 키값의 구간을 지정(21세 이상 27세 미만) 3) 키값과 비슷하도록 지정 (발음이 가장 비슷한 이름) 2. 배열에서 검색하기 - 배열 검색 1) 선형 검색 - 무작위로 늘어놓은 데이터 모임에서 검색 수행 2) 이진 검색 - 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색 수행 3) 해시법 - 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색 수행 - 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결 - 오픈 주소법 ..

티스토리툴바