주가 스팬 : 활용

https://pixabay.com/ko/photos/%EC%A3%BC%EC%8B%9D-%EB%AC%B4%EC%97%AD-%EB%AA%A8%EB%8B%88%ED%84%B0-%EC%82%AC%EC%97%85-1863880/

주가 스팬 계산하기

 위 포스트에서 주가 스팬(Stock span)이란 알고리즘을 소개한 지 세 달 정도 흘렀네요. 이 알고리즘을 여기서 쓰게 되리라고는 생각해보지 않았는데 어떻게 사용하게 되네요.

 

# tmlTitle.js 코드 분석을 함께 진행합니다. JavaScript를 모른다면 이해가 어려울 수 있습니다.

# tmlTitle.js의 v20.02.13. Release Code를 사용합니다.

---

문제 선택

tmlTitle.js에서의 문제

 제가 만든 스크립트 tmlTitle.js는 티스토리 문서의 추가 기능을 제공하는 스크립트입니다. 여러 기능을 제공하지만 indexor라 불리는 함수에서 문제가 생겼습니다. 정확히는 더 나은 기능을 만드는 과정의 고민이지요.

tmlTitle.js : 목차 생성하기

 글에서 알 수 있듯이 이 스크립트를 적용하면 알아서 목차를 생성해줍니다.

목차가 자동으로 생성됩니다.

 기존의 코드는 대/중/소분류를 구분 짓지 않고 무조건적으로 목록을 생성했습니다. 그러다 보니 어느 문단이 어디에 속해 있는지를 알 수가 없었죠.

 트리를 이용할까도 생각했습니다. 그러나 트리는 부적절한 구조라 생각했습니다. 트리 자체를 구현하는 코드도 길 뿐만 아니라 트리가 생각보다 느리다는 판단[# 왜 이런 판단이 들었을까.. 하면, 트리에 현재 값을 넣을 곳을 탐색하는 데 시간이 들고 그 구조를 다시 뽑아서 html element 구조를 작성해야 한다고 생각했습니다.][# 사실 트리 구조를 쓰지 않은 게 구현 코드 쓰는 게 귀찮아서..ㅎ]이 섰기 때문이죠. 그러다 생각한 것이 이 주가 스팬(Stock span) 알고리즘입니다. 

문제 확인하기

 구현코자 했던 목차의 모습은 아래 이미지와 유사합니다.

한글(왼쪽), 위키백과(가운데), 나무위키(오른쪽)

 위 이미지를 보면 각 항목이 depth를 가지고 있다고 볼 수 있겠네요. 그래서 코드에도 depth를 적용하는 것으로 생각했습니다.

---

문제 해결

 태그의 항목에 어떤 방법으로 depth를 줄까 했는데, 태그를 저장한 배열[# 달리 이야기 하면 여기에 원하는 태그를 입력하면 인덱서에서 알아서 목차에 적용한다는 의미가 되죠.]을 만들고 그 배열의 인덱스를 depth로 정했습니다.

Line 260

 아래 코드 중에 키 값이 class인 코드가 있습니다. 이 class는 각 depth에 다른 값을 넣어주고 싶을 때 구분용으로 만든 코드입니다.

Line 264

 이러한 목적으로 만들다보니 가장 큰 값은 바뀌어선 안됩니다. 아무리 자식이 많은 항목이더라도 root의 클래스 값은 변동이 생겨선 안됩니다. 그래서 인덱스 0에 가까울수록 root에 가깝게 코드를 작성했습니다.

 

 Line 353을 보겠습니다. 일반적으로 문단을 나누는 구분선을 기준으로 새로운 글이 나오게 됩니다. 그러면 목차의 부모도 변경할 필요가 있습니다. 그래서 구분선 태그인 hr을 기준으로 배열을 만들도록 코드를 작성했습니다.

 실제 항목을 찾아서 배열화하는 작업은 findObjInParagraph[# Line 311] 함수에서 진행합니다.

 목차로 구성할 항목들을 다 찾으면 이제 html element node로 구성해야죠. 이 작업은 Line 372부터 시작합니다.

 

선행 작업

 이번 설명에서 사용할 알고리즘[# 영어 발음대로 하면 알고리듬(thm..)이지만..]은 Stock Span입니다. 이 알고리즘은 이전 포스트에서 다루어 봤으니 알고리즘 설명은 깊이 하지 않습니다.

 글은 위에서 아래로 쓰고 읽습니다. 따라서 A의 자식인 B가 A보다 먼저 작성되지는 않는 셈이죠. 그렇게 생각하면 목차로 만들 데이터는 선형으로 들어온다고 볼 수 있겠네요. 

 

 선형으로 들어올 데이터는 한 가지 문제가 있습니다. A의 자식인 B의 depth가 A의 depth보다 깊은 것[# 자식일수록 더 깊이 들어가므로 depth는 깊어집니다.]은 자명하지만, A의 자식인 아닌 C는 A의 depth보다 높지 않다는 것은 모르는 일입니다. 이미지처럼 이후에 나올 요소가 기준 단락인 A보다 얕을 수 있다는 말이죠.

depth기준 정렬

 C의 depth가 A의 depth와 같은 경우 형제 노드로 만들면 되지만 부모급[# depth의 차이가 1], 혹은 조상급[# depth의 차이가 2 이상] depth라면 중간 계층을 만들어야[# 달리 이야기 해 예외처리를 더 많이 해야 한다는 말이죠. ]할 수 있습니다. 따라서 목차를 만들때 기준이 되는 대상의 depth보다 얕은 대상은 기준 대상의 depth와 같은 것으로 취급합니다.

Line 378. 주석 내용은 무시하세요 :)

 이렇게 작성하면 목차가 위에서 보인 구조가 아닌 아래처럼 처리가 될 겁니다. depth가 기준 요소보다 클 수가 없으니까요.

일반 목차처럼 구조를 가지게 되었습니다

Stock Span(주가 스팬) Algorithm

 Line 378 이후에 바로 나오는 for 반복 구문이 여기서 설명하는 Stock Span의 알고리즘입니다. 기존 포스트에서 설명한 알고리즘과 다른 점을 들라면 현재 요소에서 가장 가까우면서 현재 요소보다 큰 값을 찾는 것이 아니라 더 작은 값을 찾도록 구성[# 그 이유는 상위 노드의 값이 더 낮은 depth를 가지기 때문입니다.]합니다.

Line 384

 변수 curParent는 언제나 리스트 태그[# li]의 부모가 되는 목록 태그[# ol, ul 등]를 가리킬 수 있도록 두 번 빠져나갑니다.

# curParent는 parentElement를 두 번 사용하나요?

 이 코드로 구현되는 노드는 아래와 같이 wrapper라 칭할 수 있는 ol, ul 태그가 실제 값을 가지고 있는 li 태그를 감싸고 있습니다. 그리고 최상위 ol, ul 태그를 제외한 다른 모든 목록 태그는 모두 부모 요소를 li로 두고 있습니다. 따라서 목적에 맞게 curParent의 대상을 목록 태그로 제한하려면 본인을 담고 있는 li, 그 li를 담고 있는 목록 태그를 반환토록 parentElement를 두번 작성해주어야합니다.

Line 388

 위 과정을 거친 후 스택에 값이 하나 이상 남아있다면 우리는 curParent가 가리키는 요소가 최상위 요소가 아니라는 것을 알게 됩니다. 따라서 요소에 목록 태그가 존재하는지를 판별하고 나서 목록 태그가 있으면[# Line 401] curParent가 해당 요소를, 없다면 새로 만들어 가리키도록[# Line 396] 합니다.

Line 409-412

 최종으로 새로이 만들어진 리스트 요소를 상위 요소에 추가하고 현재 작성된 녀석의 depth를 알 수 있도록 스택에 추가해줍니다.

 

 이 코드를 적용하면 기존에 선형 구조를 가지던 목차가 깊이를 가진 목차로 탈피하게 됩니다.

# index