주식 가격 문제 - 거꾸로 생각하기는 정말 중요하다.

1. 주식 가격 문제

프로그래머스

 

문제를 간략하게 요약하면 아래와 같다.

초 단위로 기록된 주식 가격이 담긴 배열이 매개변수로 주어진다. 각 초를 기준으로 가격이 떨어지지 않은 기간은 몇 초 인지 return하라.

prices = [1, 2, 3, 2, 3] 이면 return = [4, 3, 1, 1, 0]

해석하자면, 첫 번째 기간의 가격은 1이다. 1 입장에서는 4기간 동안은 가격이 떨어진 적이 없다. 따라서 4다. 두 번째 기간의 가격은 2다. 역시나 떨어진 적이 없으므로 3기간이다. 세 번째 기간의 가격은 3인데, 바로 다음 기간에서 가격이 2로 떨어졌다. 1기간 동안만 살아남았다. 이런 식이다.

풀이 자체는 스택을 사용한다. 방법은 아래와 같다.

prices를 순회 접근한다. 순서대로 각 원소의 인덱스를 스택에 넣는다. 이때 가격이 직전 기간과 비교해 떨어졌다면 스택에서 원소들을 peak한다. 만약 현재 가격보다 해당 인덱스의 가격이 높다면 pop한다. 현재 가격의 인덱스 i와 스택에 있던 원소의 인덱스 j를 빼면 기간이 나온다.

 

2. 문제 풀이의 원리와 스택을 사용하는 원리

역시나 언뜻 보면 이 문제의 풀이는 해당 문제에만 적용되는 특수한 경우 같아 보인다. 그러나 컴퓨팅의 원리가 숨어 있다. 

먼저, 이 문제를 풀기 위해 다음과 같이 직관적인 풀이를 해볼 수도 있다.

prices의 원소에 순회 접근한다. 해당 price에 대해 i+1 부터 끝까지 원소들을 순회하며 비교 연산을 수행한다. 만약 가격이 price보다 떨어졌다면, 해당 인덱스 j와 i를 빼서 기간을 구한다. 이 과정을 모든 prices의 원소에 반복해 배열을 구한다.

 

이 방식은 시간복잡도가 O(N^2)임을 어렵지 않게 계산할 수 있다. 당연히 문제에서 쉽게 사용할 수 없다. 이 문제의 제한 조건 중 하나가 prices 배열의 크기가 100,000개가 최대인데, 위 시간복잡도 하에서는 오래 걸린다.

처음에 이 문제를 풀려고 했을 때 좀 애를 먹었다. 그 이유는 컴퓨팅 사고력의 본질 중 하나인 "거꾸로 생각하기"를 하지 않았기 때문이다.

 

2-1. 거꾸로 생각하는 역방향 사고 방식의 중요성.

가격이 떨어지기까지 걸린 시간을 구하기 위해서 어떻게 해야 할까? 이때 사람들은 보통 a라는 기간의 가격을 기준으로 삼고, 뒤를 향해 prices 배열에 접근해가며 언제 떨어지는지 알아내야 한다고 믿는다. 이것이 거꾸로 생각하는데 실패한 사고방식이다.

특정 기간에서 출발해서 하나의 기간만을 고려할 이유는 없다. 거꾸로 생각해보자. 특정 기간의 가격이 떨어지기까지 걸린 시간을 구하지 말자. 반대로 하자. 거꾸로 해당 시간을 끝에 놓고 왼쪽으로 진행해보자는 것이다.

왼쪽으로 진행해나가면 무엇을 알 수 있을까? 

기간30 의 가격이 $10이다. 왼쪽으로 향해 가는데 기간29의 가격이 $15다. 그렇다면 기간29는 기간30이 되어 가격이 $5 만큼 떨어진 것이다. 기간28로 가보자. 만약 기간28의 가격이 $12라면? 기간28은 기간30이 되어 $8만큼 떨어진 것이다.

그렇다. 거꾸로 생각해나가면 해당 정보를 이용해 한 번에 떨어진 기간을 구할 수 있다. 역방향으로 사고하니 문제가 쉽게 풀린다. 

 

2-2. 스택

이 문제가 스택을 사용하는 이유는 바로 거꾸로 생각하기의 핵심 알고리즘 때문이다. 거꾸로 생각해나가기 때문에 역추적이 필요하다. 들어온 순서가 아니라 최근에 쌓인 순서대로 거꾸로 기간을 되짚어 올라가야 한다.

그렇게 계산이 끝난 기간은 더 이상 계산할 필요가 없다. 이 구조는 정확히 스택 그 자체다.

스택은 보통 큰 문제에서 작은 문제들로 분할되어 해결하는 구조에서 사용된다. 이 문제에서 스택은 역산하기 위해 역추적하는데 사용된다. 약간 사용 방향은 다르지만 역추적 또한 스택이 사용될 수 있는 구조다.