알고리즘 핵심 강의 (이론) 1일차

빅오표기법과 stack 자료구조에 대해서 배웠다
수업 종료 10분전 문제 하나를 과제로 내주셨는데 내용은 이러하다
이런식으로 그래프가 주어지면 막대 그래프 맨 위쪽에 빨간 선을 그 그래프 기준 왼쪽으로 긋는데
이때 빨간 선이 닿는 그래프가 몇번인지 출력하는 문제이다.

그럼 한번 이 문제를 풀어보자

첫번째로 1번 배열에 있는 정보를 스택에 넣는다.

탐색을 2번 배열부터 시작하며 탐색하려는 값과 스택을 비교한다.
비교하는 도중 스택의 top에 자신보다 작은 값이 있으면 그 값은 결국 지금 탐색하는 값에 가려져 더이상 닿을 레이저가 없기 때문에 pop한다.

위와 같은 행동을 자신보다 큰 값이 나올 때 까지 반복한다.

i) 자신보다 큰 값이 나왔으면 현재 탐색하고 있는 값의 빨간 선은 그 값을 가리킨다.
ii) 자신보다 큰 값이 없다면 (스택이 비었다면) 현재 탐색하고 있는 값은 가장 큰 값이 된다.
즉 빨간 선은 제일 왼쪽 끝으로 간다.

이것은 실제로 학원에서 집으로 돌아오기 전에 짠 순서도이다. 선생님께서는 항상 문제를 풀 때 키보드에 바로 손을 대지 말고 먼저 내가 어떻게 코드를 짤 것인지 생각을 하라고 강조하셨다.
이 조언과 미리 짜둔 순서도 덕분에 나는 코드를 짤 때 전보다 더 수월하게 짤 수 있었다.
그렇게 해서 나온 코드이다.

 

HM(최대치) 를 10으로 설정하여 돌려봤을 때 잘 나오는 것을 확인 할 수 있었다.

이런식으로 코드를 짜면 스택을 바로바로 비워줄 수 있기 때문에 속도가 조금 빨라 질 수 있다.
시간복잡도는 탐색할 때 한번 스택으로 다시 검사할 때 한번으로 O(2N)이 나온다