Stack
2019. 02. 12 (Tue)
자료를 쌓아올려 저장하는 자료구조
1 : 1 관계
Last In First Out: 마지막에 들어온 것이 먼저 나간다
데이터 연산을 역순으로
자료구조
자주 접근되는 논리구조를 통해 자료를 저장하고 관리
Abstract Data Type
논리적인 구조로 이루어진 자료형
논리적인 구조 : 깨져서는 안되는 자료의 구조
하나의 객체에 대해
구현은 선택의 문제: class나 struct든 어떤 방식을 사용해서 구현할 수 있다.
I. 기본 구조 & 연산
top : 마지막으로 삽입된 자료의 위치
- 보통 top은 -1에서 시작
push : 삽입 연산. top += 1
pop : top의 자료를 꺼내는 연산. top -= 1
peek : top의 자료를 가져오는 연산
II. 구현 방법
1. 배열
구현이 용이하다는 장점이 있지만, 스택의 크기를 변경하기 어렵다.
스택의 크기를 변경하는데 O(n)
2. 리스트
구현은 어렵지만 메모리를 효율적으로 관리할 수 있다.
III. 적용 예시
1. 올바른 괄호
스택을 사용하여 올바른 괄호인지 판단할 수 있다.
2. 재귀적 함수 호출
실행 파일의 메모리 구조
code: binary 형태의 코드 파일을 저장하는 영역
data: 정적, 전역 데이터를 저장하는 영역
heap: 프로그램 실행에 따라 동적으로 자료를 저장하는 영역
stack: 일반적인 자료, 함수 데이터를 저장하는 영역
stack과 heap은 같은 메모리장소를 공유함
함수 호출
함수가 호출될 때 마다 stack에 함수의 현재 진행상태, 주소등을 push
함수가 종료되면 해당 자료를 pop
메모리 할당, 해제를 계속 해주어야 되므로 재귀는 느리다
heap을 침범하는 함수 호출을 하면 segmentation fault(stack overflow) 발생
재귀함수 요소
base case : 재귀 호출을 종료하는 경우
- 반드시 작성해주어야 하며, 작성하지 않을 경우 프로그램이 무한으로 실행
3. 피보나치 수열
O(2^n)
non-polymolial problem(NP) : 인간이 견딜 수 없는 시간이 걸리는 문제
k^n, n!
근사치로 구한다
결정론적 알고리즘 : 같은 input에 대해 항상 같은 output
- 같은 일(중복)을 반복시키지 말자
Memoization: 이미 계산된 결과를 기록하고 재사용 한다
Dynamic Programming
최적화 방법론
입력 크기가 작은 부분을 모두 해결하고, 그 해를 이용하여 더 큰 크기의 문제를 해결한다
- 이미 해결한 문제는 다시 계산하지 않는다
IV. 기타 내용
상태 공간 트리
알고리즘의 실행 단계 하나 하나를 트리형태로 표현한 구조
알고리즘을 구현하기 전에 알고리즘의 상태 공간 트리를 그려보고 합당한 로직인지 판단한 뒤 구현한다.
alogorithm testing?
Adv: 탐색공간(상태공간트리) 완전검색
Pro: 논리적 중복, 회피, 줄이기
비결정론 알고리즘?