자료구조1(리스트, 스택, 재귀함수)

자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조

 

자료구조의 필요성

데이터를 메모리에 저장하기 위해 여러 자료 구조를 사용한다.

자료구조를 활용해서 응용 프로그램의 성능 향상, 표준화, 가독성, 유지 보수 등의 관점에서 유리하게 데이터를 관리할 수 있다.

시간 복잡도는 내부에서 데이터를 어떻게 저장하여 사용하는가에 따라 달라진다. (시간 복잡도는 데이터 크기가 변경되면 연산 시간이 어떻게 변하는지 보여준다.)

 

선형자료구조 1. 연속된 자료 구조 - 정적 배열, 동적 배열

                       2. 연결된 자료 구조 - 연결 리스트

 

스택

-삽입(Push) 삭제(Pop), 순차 자료구조

변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장

공백 상태 : top = -1 (초기값) , 포화 상태 : top = n-1

 

//C언어 순차 자료구조
void push(int *top, n, int data, stack){ // 스택에 데이터를 추가
	if(*top >= n){stack_full(); return;} // 오버플로
    *top = *top + 1; stack[*top] = data;
}

 

//c언어 순차 자료구조
int pop(int *top){//스택에서 데이터를 삭제 후 반환
	if(*top = -1){return stack_empty();} // 언더플로
    return stack[*top--]; // 반환된 값은 삭제된 데이터를 알려주는 역할
}

 

- 삽입(Push) 삭제(Pop), 연결 자료구조

    -> 순차 자료구조로 스택을 구현하면 쉽게 구현할 수 있지만 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경이 어렵다. 이와 같은 단점을 보완하기 위해 연결 자료구조를 이용해서 구현한다.

변수 top : 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수, 초기 상태 : top = null

//c언어 연결 자료구조
typedef int element;

typedef struct stackNode{
	element data;
    struct stackNode* link;
}stackNode;

stackNode *top;

//스택의 top에 원소를 삽입하는 연산
void push(element item){
	stackNode *temp = (stackNode*)malloc(sizeof(stackNode));
    
    temp->data = item;
    temp->link = top;
    top = temp;
}

//스택의 top에서 원소를 삭제하는 연산
element pop(void){
	element item;
    stackNode *temp = top;
    
    if (isStackEmpty()){
    	return0;
    }else{
    	item = temp->data;
        top = temp->link;
        free(temp);
        return item;
    }
}

 

- 스택 파이썬으로 구현

스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능하다. 

stack = []

# 삽입(5) 삽입(4) 삭제() 삽입(5) 삭제()
stack.append(5)
stack.append(4)
stack.pop()
stack.append(5)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력
# 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다.
# 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 작동한다.

 

 

재귀 함수(자기 자신을 다시 호출하는 함수)

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
    
recursive_function()
# 재귀함수의 메모리 참고 블로그
# https://bentist.tistory.com/57

ex) 프랙털 구조

재귀함수는 종료 조건을 명시해야 한다.

 

출처 : 이것이 ~ 코딩테스트다 with 파이썬 p122~133, 코딩 테스트를 위한 자료 구조와 알고리즘 with C++