가장 최근의 것을 꺼낸다라...
그렇다면 stack에서는 보관할 위치와 꺼낼 위치 중 하나만 알게되어도 두 위치를 모두 파악할 수 있게 됩니다.
이말이 뭐냐하면 말입니다, 어차피 들어오는 구멍 나오는 구멍이 같기 때문에
가장 위의 위치를 가리키는 값 하나만 있어도
저장할 위치와 꺼낼 위치를 파악할 수 있다 이겁니다.
일반적으로 가장 최근에 보관한 데이터의 위치를 'top' 이라고 부릅니다.
그럼 생각해볼까요?
아무것도 없다면, stack에서 top의 위치는 -1일 것입니다. 따라서, 초기 값을 -1로 출발합니다.
전산학에서 배우는 stack에서 용어에 대해 간략하게 정리해보겠습니다.
stack에 보관하는 행위를 우리는 'Push'라고 부를 것입니다.
또한, 꺼내는 행위를 'Pop'라고 부를 것이고요.
일반적인 전산학에서 배우고 동작하는 이름은 push와 pop 입니다.
하지만, STL에서 제공하는 stack 라이브러리에서는 약간의 차이가 있어서
혼돈이 오실 수 있으니 주의하시길 바랍니다.
제가 무슨 말을 하는 것이냐면,
기존에 배운 내용을 바탕으로 우리가 코드를 구현할 때
데이터를 입력할 때는 단지, push 기능을 사용하고,
데이터를 꺼낼 때는 pop 기능을 사용하면 되지 않느냐...라고 생각할 수 있습니다.
보관하는 메서드인 push는 이론과 그대로 이지만
STL에서는 top과 pop의 동작이 따로 나누어져 있기 때문에 익숙치 못하신 사용자들의 경우
대게 혼란을 겪을 수도 있습니다.
즉, STL에서는 top의 메서드를 가장 최근에 보관한 위치를 참조할 때 사용이 가능하고,
참조할 위치를 파악 한 뒤에, pop 메서드를 통해 스택에 가장 최근에 보관한 것을 지워야 합니다.
그러니 pop 메서드만을 독립적으로 사용할 수 없다는 것이지요
이와 같이 이름의 차이가 어느정도 있을 수 있으니
실제 코드 구현시 실수 하지 말라는 차원에서 말씀을 드렸는데...
굳이 중요한 것은 아닌 거 같습니다... 아무튼...
스택이란 이런 것입니다... 간단하죠?
하지만 stack에 대해서 우리는 누구나 쉽게 알 수 있습니다.
그 말은 stack 구현은 누구나 쉽게 할 수 있다는 것입니다.
문제는 우리가 스택을 가지고 프로그래밍을 할 수 있느냐이죠...
이제 돌고 돌아 드디어 본론으로 왔습니다.
오늘 생각해보고자 하는 것은 바로 '동적 알고리즘' 즉, '동적 프로그래밍'입니다.
해당 부분에 대해서 생각해보도록 하죠...
자... 우선 stack에 대해 위에서 간략하게 배웠는데,
그렇다면 어디에서 stack을 사용하게 될까요? 어떤 때에 stack을 사용하느냐 이겁니다.
언제 사용할까요?
본론으로 알아보겠다고 한 동적 프로그래밍에 자주 사용되기에 언급하지 않았을까요? 하하하...
동적 프로그래밍이란,
"여러 단계를 거쳐 해결하는 문제가 있다고 했을 때,
n단계에서 (n+1)단계로 전이할 경우의 수가 많은 상황에서 모든 경험을 수행하며 문제를 해결하는 알고리즘..."
이라고 정의할 수 있을 거 같습니다. 어렵지요...
개발자가 무엇을 언제 stack에 보관하고 언제 꺼내와서
어떻게 사용할지 판단하는 것은 어려운 일입니다.
결론부터 말씀드리자면, stack을 사용해야 하는 상황은
반복해서 문제를 해결해야 하는데 반복문 내에서 수행해야 할 작업이 여러 개이고
그 중에 일부 작업이 다시 같은 논리로 반복해서 해결해야하는 경우입니다.
stack을 언제 사용하느냐를 판단하는 것보다,
지금 이 글을 이해하는게 더 어려우실 수 도 있겠군요.... 아하하...
쉽게 생각해보죠...
어떤 문제(A)를 해결하기 위해서 그 문제를 잘게 쪼개어서 그 문제들(a1, a2 ...) 을 해결합니다.
그 해결한 문제들을(a1, a2...) 문제(A) 해결을 위한 연장선으로 생각하고,
잘게 쪼개 구한 문제들의 해(a1, a2 ...)를 활용하는 방식의 알고리즘이라고 할 수 있습니다.
아 어렵다!!! 그러니깐... (설명하는 스스로가 답답하군요 ㅠㅠ 이해를 잘 못해서겠지요...)
한 문제가 여러 단계의 반복되는 부분 문제로 이루어질 때,
각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이라고 합니다...
예를 들어봅시다...
동그라미를 바구니라고 생각해보도록 하겠습니다.
우리는 바구니 안 5개의 문자중 3가지의 문자를 뽑는 모든 경우의 수를 구해본다고 생각해 보겠습니다.
어떻게 해결 할 것인가요?
A가 우선 뽑힌다고 가정해보도록 하겠습니다.
그렇다면 다음으로 뽑힐 문자들은 나머지 문자들인 BCDE 4가지의 경우가 생깁니다.
또 이 중에서 B가 뽑힌다고 가정해보록 하겠습니다.
그렇다면 다음으로 뽑힐 문자들은 나머지 문자들인 CDE 3가지의 경우가 생깁니다.
이와 같이 모든 경우의 수를 구하기 위해서는 중복되는 경우를 피할 수 없습니다.
이 때 동적 프로그래밍 알고리즘을 사용하는 것입니다.
모든 경우들을 한 번씩 풀고 이를 stack에 저장함으로써
각 부분 문제를 풀 때마다 중복 없이 해당 stack 위치를 참조하여 해결할 수 있다는 것이지요.
아하! 이제 좀 감이 잡히셨나요!? 하... 너무 먼길을 돌아왔습니다...
저의 글실력이 부족함이련지요... 흙흙... 아무튼...
동적 프로그래밍은 이전 시간에 배운 분할 정복과 비슷합니다.
(퀵정렬을 알아볼 때 분할 정복에 대해서 언급한 적이 있습니다.)
분할 정복의 경우 문제 하나를 잘게 쪼개며 세부적으로 들어가는 것이지요.
{ 4, 2, 3, 9, 1, 0} 이와 같은 배열이 있을때, 정렬해본다고 생각해보세요...
큰 배열 하나를 정렬이 완성 될 때까지 잘게 쪼갰었죠...
이와 반대로 동적 프로그래밍의 경우에는,
작은 부분부터 큰 부분으로 올라간다고 생각하시면 될 듯합니다.
위의 예를 들었듯이 5개의 문자들중 3개의 문자들을 뽑는 경우의 수를 구하기 위해서는
우선, 문자 하나를 뽑을 때의 경우 부터 접근을 했습니다.
즉, 작은 부분부터 시작을 하는 것이지요.
추가적으로, 동적 프로그래밍에서 각 부분들은 결국 그 다음 단계의 문제를 해결할 때 사용됩니다.
반복해서 말하지만, 효율적으로 사용하기 위해서
결론적으로, 부분 문제의 답을 stack에 보관하여 반복하는 경우를 없애는 것이지요.
Optimal Substructure 구조들을 해결 할 때에, 동적 프로그래밍이 빛을 발휘됩니다.
Optimal Substructure란, 위에서 예시를 들었듯이,
작은 문제의 답으로 부터 최종 문제의 답을 도출 할 수 있는 구조를 말하는 것입니다.
그럼 stack을 통해 동적 프로그래밍 알고리즘을 사용하는 법을 배웠으니,
이를 코드로 옮길 줄 알아야합니다.
해당 알고리즘을 구현하기 위한 절차를 소개하도록 하겠습니다.
1. 초기 상태(전산에선 경험정보(Heuristic))를 생성
2. 스택에 보관
3. 반복(스택이 비어 있지 않다면)
상태를 꺼내옴
현재 상태에서 전이할 수 있는 다음 상태를 조사
반복 (각각의 다음 상태)
결론에 도달하면
결론에 보관
그렇지 않다면
스택에 보관
이와 같은 절차를 거칠 시에, 모든 경우의 수를 거치게 되지요...
경험 정보란,
말 그대로, 결론에 도달하기 전까지 모든 케이스들을 만드는 것이라고 할 수 있겠습니다.
경험 정보를 통해서 현재 상태로 부터 다음 경험을 만들 수 있게 됩니다.
동적 프로그래밍 알고리즘 코드 구현시
가장 골머리를 앓는 것이 바로 휴리스틱 디자인...
즉,'경험정보를 어떻게 디자인 할 것이냐' 라고 합니다...
해당되는 문제에서 무엇을 보관해야 하는지 경험 정보를 어떻게 디자인 하냐의 차이만 있을 뿐,
그 이외에 동적 프로그래밍 알고리즘을 구현하는 방식은 차이가 없습니다.
경험정보에는 뭘 보관해야할까요... 우리는 위의 예시를 통해 답변을 드리자면,
바구니의 문자들과 꺼내놓은 문자들에 대한 각각의 바구니가
경험 정보라고 할 수 있겠습니다.
즉, 현재 상태가 A라는 문자를 꺼낸 상태라면,
이것이 이번에 경험하게 된 '경험 정보'가 되는 것이지요...
왜냐, 현재 꺼내 놓은 문자가 담긴 바구니와 원래 담겨져 있는 바구니를 통해
다음 단계 즉, 다음 문자를 꺼낼 수 있는 상태를 만들 수 있기 때문입니다.
현재 경험을 기반으로 다음 경험을 생성하고,
또 다음 경험 정보를 얻고 또 경험을 생성하고... 또... 또... 또...
이와 같은 반복을 하도록 알고리즘을 만드는 것입니다....
어렵지요....
중요한 것은 우리가 주어진 문제를 해결하고자 할 때 필요한 판단,
즉, 판단을 하고자할 때 우선적으로 경험 정보를 디자인하고 동적 알고리즘을 설계해야합니다...
역시나 어렵습니다... 휴...
아무튼...
문제를 해결하고자할 때 여러 단계 즉, 모든 경우를 거쳐야 하는 경우 (순열, 확률, 조합 등)
는 모두 동적 알고리즘을 사용해야한다고 생각하시면 될 듯 합니다.
동적 알고리즘은 대단히 중요한 곳에서 많이 사용된다고 하는데요...
해당 예시 코드는 나중에 소개해드리도록 하지요...
정말 어렵죠???
근데 제가 글솜씨가 없어서.... 어찌 보면 쉬운데 제가 어렵게 쓴 것일 수도....
아무튼... 읽어주셔서 감사드리며 글을 마무리 하겠습니다.
이상 삽잡이였습니다~!
'삽질의 현장 > - 자료구조와 알고리즘' 카테고리의 다른 글
| #006_자료구조와 알고리즘_너와 나의 연결고리! 연결 리스트 (더미 노드O) (0) | 2015.08.05 |
|---|---|
| #005_자료구조와 알고리즘_들어온 순서대로! 큐(Queue) (0) | 2015.08.04 |
| #003_자료구조와 알고리즘_누구보다 빠르게 Quick 정렬 (0) | 2015.08.03 |
| #003_자료구조와 알고리즘_삽입 정렬 (0) | 2015.07.30 |
| #002_자료구조와 알고리즘_find_if 알고리즘 (0) | 2015.07.30 |