Chp5. 꼭필요한 자료구조 기초

• 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 탐색 알고리즘 : DFS, BFS
• 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

 

스택

• 선입선출 FILO(first in last out)구조, 후입선출 LIFO 구조
• 스택에서의 입출력은 맨위에서만 일어나고, 스택의 중간에서는 데이터를 삭제할 수 없다.

파이썬

stack=[]    ##리스트를 이용한다.

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) #최하단 원소부터 출력
print(stack[::-1]) #최상단 원소부터 출력

#출력결과
#[5, 2, 3, 1]
#[1, 3, 2, 5]

파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다.

+파이썬 문법이 아직 낯설다,,,,

C언어

• 배열을 통한 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 10

void push(int *stack, int *top, int value){
	if(*top>=MAX_STACK_SIZE-1) printf("overflow\n");	
	else
		*top+=1;
		stack[*top]=value;
}

void pop(int *stack, int *top){
	if(*top==-1) printf("underflow\n");
	else
		printf("pop : %d\n", stack[*top]);
		*top-=1;		//실제로 배열안의 value를 삭제하는 것이 아니라
}						//top index만 바꿔 이후에 push하는 새로운 value값으로 덮어진다. 

int main(){
	int stack[MAX_STACK_SIZE];	//스택의 요소들을 저장할 배열
	int top=-1;		//가장 최근에 입력되었던 자료의 index
					//공백스택일 경우top==-1이다. 
	int i=0, value;
	
	while(scanf("%d", &stack[i])!=EOF){		//스택에 push하는 경우  
		i++;
		top++; 
	}
	
	printf("last input : ");
	scanf("%d", &value);
	
	push(stack,&top,value);
	pop(stack,&top); 
	
	printf("스택 출력\n");
	for(i=0;i<=top;i++){
		printf("%d ", stack[i]);
	}
}

 

큐

• 선입선출 FIFO(first in first out) 구조

파이썬

from collections import deque

#큐 구현을 위해 deque 라이브러리 사용
queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력
queue.reverse() #다음 출력을 위해 역순으로 바꾸기
print(queue) #나중에 들어온 원소부터 출력

#출력결과
#deque([3, 7, 1, 4])
#deque([4, 1, 7, 3])

C언어

• 원형큐

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct{
	int front;		//큐의 전단의 index값  
	int rear;		//큐의 후단의 index값 
	element data[MAX_QUEUE_SIZE];
}queuetype;

//큐를 초기화 한다. 
void init_queue(queuetype *q){
	q->front=0;
	q->rear=0;
}

int is_full(queuetype q, char flag){
	if(q.front==q.rear && flag=='E') return 1;
	else return 0;
}

int is_empty(queuetype q, char flag){
	if(q.front==q.rear && flag=='D') return 1;
	else return 0;
}

void enqueue(queuetype *q, char *flag, element input){
	if(is_full(*q, *flag)){
		printf("큐가 포화상태");
	}
	q->rear=(q->rear)%MAX_QUEUE_SIZE;
	q->data[q->rear++]=input;
	*flag='E'
} 

int dequeue(queuetype *q, char *flag){
	if(is_empty(*q, *flag)){
		printf("큐가 비어있는 상태");
		exit(1);
	}
	*flag='D';
	q->front=q->front%MAX_QUEUE_SIZE;
	q->front++;
	return q->data[q->front];
}

void queue_print(queuetype q){
    for(int i=q.front+1;i<=q.rear;i++){
        printf("%d ", q.data[i]);
    }printf("\n");
}

int main(){
	int item = 0;
	char flag = 'D';	 
	queuetype q;
	
	init_queue(&q);
	
	enqueue(&q, &flag, 10); queue_print(q);
	enqueue(&q, &flag, 20); queue_print(q);
	
	item=dequeue(&q, &flag);  queue_print(q);
    item=dequeue(&q, &flag);  queue_print(q);
}

재귀 함수

• 자기자신을 다시 호출하는 함수
• 재귀함수가 자기자신을 무한히 추가로 불러오면 오류메시지를 출력, 오류메시지는 재귀의 최대 깊이를 초과했다는 내용으로 파이썬 인터프리터는 호출 횟수 제한이 있는데 이 한계를 벗어났기 때문에 발생

 

• 프랙털 구조와 흡사

재귀함수의 종료조건

• 재귀함수를 문제풀이에서 사용할 때는 재귀함수가 언제 끝날지, 종료조건을 꼭 명시해야 한다.
• 재귀함수는 내부적으로 스택 자료구조와 동일 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 함 == LIFO구조
• 따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀함수를 이용해서 간편하게 구현가능
• 예제) 재귀함수

def factorial_recursive(n):
    if n<=1:   #n이 1이하인 경우 1을 반환
        return 1
    return n*factorial_recursive(n-1)

#n!=n*(n-1)!

반복문 대신 재귀함수를 사용할 때 재귀함수의 코드가 더 간결한 이유는 재귀함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다.( 점화식 : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것)