[ SWEA ] SW 문제해결 기본 - Stack 1

하루입니다.

 

1차시 : Stack 자료구조의 개념Stack의 특성, Stack의 구현

2차시 : Stack의 응용괄호검사, Function call

3차시 : Memoization피보나치 수열, 피보나치 수를 구하는 재귀 함수, Memoization이란?

4차시 : DP(동적 계획법)DP 개념, DP를 적용한 피보나치 수

5차시 : DFS(깊이우선탐색)DFS 개념, DFS 알고리즘, DFS의 예

 

 

---

[ SWEA ] SW 문제해결 기본 - Stack 1 (1)

1차시. Stack 자료구조의 개념

1. stack의 특성

• 프로그램에서 중요성과 활용도가 매우 높은 자료구조이다.
• 자료를 쌓아 올린 형태의 자료구조이다.
• 선형구조이다.
• 선형구조란 ? 자료간의 관계가 1대1인 것이다. 배열, 연결리스트, 스택, 큐 ...
• 비선형구조란 ? 자료간의 관계가 1대1 혹은 1:n인 것이다. 트리, 그래프

• stack에 자료를 삽입하거나 꺼낼 수 있다.
• 마지막에 삽입된 자료가 가장 먼저 꺼내진다. 
• 후입선출(LIFO)이다. 
• 1 2 3 순으로 자료를 삽입한다면, 3 2 1 순으로 자료가 꺼내진다.

 

 

2. stack의 구현

자료구조

• 자료를 선형으로 저장할 저장소가 필요하다. 
• C언어에서는 배열 사용. 자바도 그럴 듯?
• 저장소 자체를 stack이라고도 함. 
• stack에서 마지막에 삽입된 원소의 위치를 top이라고 함.

 

연산

• 삽입 : push, 저장소에 자료 저장
• 삭제 : pop, 저장소에서 자료 꺼냄

 

 

3. stack의 연산

• 빈 stack에 원소 a b c를 차례로 삽입 후 한 번 삭제하는 연산과정

 

 

 

 

stack 구현시 고려사항

 

 

---

 

 

2차시. Stack의 응용

1. 괄호 검사 (알고리즘 개요)

포함 관계란? { () } 이런 거. { { ( ) ] } 이런 건 불가하다는 뜻이다.

 

 

2. function call (함수 호출)

함수 호출 관리

 

 

프로그램 메모리 공간

• 프로그램이 실행되어 메모리 공간에 적재되면, 논리적으로 4가지의 영역으로 나뉜다.
• 이 중, 함수 호출이 발생하면 스택 영역에 stack frame이 위치하게 된다.

 

 

스택 프레임이란?

출처 : http://www.tcpschool.com/c/c_memory_stackframe

• 스택 영역에 차례대로 저장되는 함수의 호출 정보이다.
• 메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역이다.
• 스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.
• 함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장된다.
• 스택 오버플로우 주의! (재귀함수의 재귀함수의 재귀함수의 ... )

http://www.tcpschool.com/c/c_memory_stackframe

 

 

 

함수 호출 수행 순서

 

 

재귀 호출

• 함수가 자기 자신을 호출하여 순환 수행되는 것
• 함수에서 실행해야 하는 작업의 특성에 따라 재귀 호출 방식을 사용한다면 프로그램의 크기를 줄이고 간단하게 작성할 수 있다.
• 디버깅이 어렵고 잘못 작성하게 되면 수행 시간이 많이 소요된다.

 

 

---

 

3차시. Memoization

 

 

 

---

 

4차시. DP(동적 계획법)

 

 

 

---

 

5차시. DFS(깊이 우선 탐색)