본문 바로가기

C언어/자료구조

 (38)
5-4장 8퀸 문제 1. 8퀸 문제 정의하기 - 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓으세요 - 퀸은 가로,세로, 대각선 방향으로 체스판 끝까지 이동 가능 - 규칙 1) 각 열에 퀸을 1개만 배치 2) 각 행에 퀸을 1개만 배치 2. 가지 뻗기(branching) - 가지를 뻗으며 퀸을 배치하는 조합 모두 나열 - 배열 pos는 퀸의 배치를 나타냄 - i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 함 - set함수 -> pos[i]에 0부터 7까지의 값을 순서대로 대입하여 'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀함수' -> 0번째 열에 퀸을 배치 set(0); //0열에 퀸을 배치 -> for문에 의한 반복 구문에서는 i값을 0에서 7까지 증가시키면서 pos[i]에 j를 ..
5-3장 하노이의 탑 1. 하노이의 탑 살펴보기 하노이의 탑 (Towers of Hanoi) - 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제 - 모든 원반을 세번째 기둥으로 최소의 횟수로 옮김 - 원반은 1개씩만 옮길 수 있음 - 큰 원반을 작은 원반 위에 쌓을 수는 없음 - 원반이 3개일때 모든 과정 - 그룹 : 원반 1과 원반 2를 겹친 것 - 가장 큰 원반을 최소의 단계로 목표 기둥으로 옮기려면 먼저 '그룹'을 중간 기둥으로 옮겨야 함 - 원반 1과 원반 2가 겹친 '그룹'을 옮기는 단계 - 하노이의 탑 구현 프로그램 - move( 옮겨야 할 원반의 개수, 시작 기둥의 번호, 목표 기둥의 번호) //하노이의 탑 #include //원반[1] ~원반[no]를 x기둥에서 ..
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으로..

티스토리툴바