04. S/W 문제해결 기본 - Stack 1 (6)

1. Stack 자료구조의 개념

① Stack의 특성

• 마지막에 삽입한 자료를 가장 먼저 꺼내 지는 후입선출로 동작한다.

② Stack의 구현

• push 연산 - Stack에 값을 삽입, top의 위치가 증가한다.
• pop 연산 - Stack의 값을 삭제, top의 위치가 감소한다.

 

2. Stack의 응용

① 괄호 검사

• Stack을 이용하여 괄호의 사용이 올바른지 검사할 수 있다.

② 함수 호출

• 프로그램에서 함수 호출과 복귀에 따른 수행 순서를 관리하기 위하여 Stack을 이용한다.
• 함수 호출의 특수한 경우인 재귀 호출은 함수 호출을 자기 자신을 호출하여 순환 수행되는 함수 호출이다.

 

3. Memoization

① 피보나치 수철

• 피보나치 수열을 구하는 함수를 재귀 함수로 구현할 수 있다.

② Memoization이란?

• 재귀 함수로 구현 할 경우 심한 중복 호출이 발생할 수 있다. 
• 이를 보완하기 위한 프로그램 기법으로 기존의 계산된 해를 저장하여 다시 사용하는 기법을 Memoization이라 한다.

 

4. DP(동적 계획법)

① DP(동적 계획)이란?

• 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 기법이다.

 

5. DFS(깊이우선탐색)

① DFS(깊이우선탐색) 이란?

• 비선형구조의 모든 자료를 검색하는 방법 중 하나이다.
• 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다.
• 그리고, 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법이다.
• 되돌아가서 다시 탐색을 반복해야하므로 Stack 자료구조를 사용하여 구현할 수 있다.