대엉코딩

* 스택이란 ?

- LIFO(Last In First Out)

- 떠올리기 쉬운것은 주방에 쌓여있는 식기를 놓으면 좋다. 

- 설거지를 해서 위에 쌓으면 사용을 할 때는 위에서 부터 하나씩 가지고 간다.

* 스택의 연산

- 삽입, 삭제, 비어있는지 확인, 상단 확인, 크기 등의 연산이 있다.

- 객체 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : push(x)

               pop()

               size()              

               peek() -> 스택 상단에 위치한 요소를 반환(봄) (스택이 비어있지 않으면)

    시간복잡도 : size()를 제외하고는 모드 O(1)이라고 할수 있습니다.

                            size()는 어떻게 구현하느냐에 따라 다를 수 있습니다.( 배열이나 연결리스트)

- 말이 나와서 하는 것이지만 추상자료형 (Abstract Data Type)은 사실 어떻게 구현하느냐는 사용자는 알 수 없습니다.

   제가 배웠던 것을 항상 떠올릴 때는 문 밖에서 어떠한 입력을 넣고 요구를 하면 안에서는 어떤식이던지 구현을 하여

   정확한 결과만을 문 밖으로 다시 보내주는 것 입니다. 사용자는 결과를 받지만 내부에 어떤식으로 이를 처리 하였는지는

   알 수 없지요

* 스택 활용의 예

- 문서나 그림, 수식 등의 편집기에서 되돌리기 기능

   (최근 사용했던것 부터 다시 되돌리기를 합니다. -스택을 사용하면 편하겠죠????)

- 함수 호출에서 복귀주소 를 기억 할 때

   (예를 들면, main 함수에서 작업을 수행하다가 다른 함수를 호출해서 그 함수로 이동한다고 하면

     그 함수가 끝나고 났을 때 다시 main 함수로 돌아와서 그 다음 작업을 진행 하여야 합니다.

     그럼 그때 복귀주소를 스택에 넣어 놓습니다.)

- main에서 function A를 호출하고 function A에서 function B 를 호출 한다고 가정을 한다면????

    (스택에 우선 main으로 돌아오기 위한 복귀 주소가 먼저  push될 것입니다. 그다음 function A로 가고

      function B가 수행될 때 function A로 돌아오기 위한 복귀 주소가 그 위에 삽입 될 것 입니다.

      function B가 끝나면 스택에서 맨위 (TOP)을 pop해서 function A 나머지를 수행하고 다시 POP 을

      하면 main함수로 돌아올 수 있습니다.)

* 스택의 구현

 - 1. 배열을 이용

 - 2. 연결리스트를 이용

   직접 구현은 하지 않았지만 연결리스트를 사용하면 처음에 스택 사이즈를 지정 해 줄 필요도 없을 것입니다.

     배열을 이용해서 연결리스트 처럼 구현을 하려면 사이즈를 넘어 갈경우 max사이즈를 두배로 증가시켜서

     다시 배열을 만들고 모든 요소들을 새로운 배열로 이동시키고 원래 배열을  delete 시키고 하는 그런 복잡한

     작업을 해야할 것 입니다. 

https://www.acmicpc.net/problem/2493

처음에는 시간초과가 3번 정도 났나...

문제 파악은  별게 없는 것 같습니다.

그리고 레이저는 입력방향의 반대 방향으로 쏘기 때문에 입력을 받으면서

지금 들어와있는 입력 값들만 보면 됩니다.

처음에는 그 건물로 부터 이전에 들어온 값들을 보면서 크기를 비교 했는데 시간초과

최악의 경우 시간을 훨씬 뛰어 넘기 떄문이겠죠

그래서 비교의 수를 줄이기 위해 어떻게 할까 하다가

만약 1번 건물의 높이가 4이고 2번에 들어온 건물의 높이가 8이면 그 이후 건물들은 1번 건물은 볼필요도 없습니다.

즉 약간 높은건물에 가려서 보이지 않는 다는 느낌을 떠올린다면 스택을 이용하여 풀수 있습니다.

새로운 높은 건물이 들어 온다면 그 이전의 건물들은 모두 스택에서 빼버리는 거죠

숫자가 작을때는 별로 차이가 안나겠지만 숫자가 엄청 커질경우 시간차이가 상당 할 것으로 보입니다.

-첫번째 시간초과 났던 소스 입니다.-

-스택을 이용하여 시간초과를 해결한 코드 입니다.-

추상화 데이터 타입 그런 자료구조를 왜 만들고 왜 필요할까?

생각해보면 스케쥴러를 짜는데

큐(선입선출,FIF0)를 사용하지 않고 배열을 이용한다면....

직접 인덱스(index)관리를 일일히 해주어야 한다는 소리인데

규모가 커지면 이건 정말 쉽지 않은 문제이다.

하지만 추상화데이터타입을 만들고 그를 활용한다면 단지 pop과 푸쉬만 이용하면

따로 직접 index 를 관리 하지 않아도 된다

추상화데이터타입을 이용하는 이유 중 하나는 **인덱스 관리의 어려움** 이 있지 않을까?

스택에 함수 call과 관련된 정보를 담을 때도 스택이라는 자료구조를 이용하지 않으면 생각만 해도 끔찍하다...

들은 내용중 기억에 남기고 싶은 내용이라 정확하지 않을 수 있지만 기록을 해놓습니다...

https://www.acmicpc.net/problem/10773

- 0이 들어 올 경우 이전의 받았던 숫자를 하나 지운다.

- 문제 자체에

#정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.#

- 이러한 조건이 있어서 따로 예외처리를 할 필요도 없었다.

- 스택을 써도 좋고 저는 그냥 벡터로 했습니다.

https://www.acmicpc.net/problem/1874

- 스택 의 LIFO 개념을 인지하기 위한? 문제 인 것 같다.

- 스택에는 오름차순으로 들어간다는 점.

- 저는 원하는 결과 수열을 처음에 입력 받아서 큐에 넣어서 하나씩 비교 하였습니다.

- 스택에 넣는 과정에서 큐의 front에 있는 값과 비교를 해서 같지 않으면 스택에 넣고

- 같으면 스택에 넣었다가 뺀다 (한번은 들어갔다 나와야함.)

- 그 후 뺐을때 queue에서도 pop을 해준다.

- 그리고 그 상태에서 stack.top() 값과 queue.front()의 값이 같다면 또 빼주어야 한다 스택 큐 모두에서

- 그래서 for문을 모두 돈 후에 스택이 비어 있으면 수열이 제대로 완성이 될수 있는 것이므로 성공이고

- 그렇지 않다면 스택을 이용해서 원하는 수열을 만들 수가 없는 것이다.

- 그것을 구분하여 출력해주면 된다.( 안되는 경우에 +,-가 아닌 NO만 출력해야 하므로

- 반복문을 돌면서 출력을 해주면 안된다. 그래서 vector<bool>에 push,pop이 일어날 때 마다

- 차례대로 넣어놓고 마지막에 수열이 완성될 수 있는경우 이를 이용하여 +,-를 출력하였다.

- 자료구조는 자신이 필요하다 싶은, 그리고 더 효율적일 것 같은 자료구조를 선택하면 될거 같다.

- 저도 더 컴팩트하고 쉬운 방법은 없는 지 생각해보겠읍니다.

 # 메모리 영역의 구성

메모리 영역은 위와 같이 구성되는데 "가상 메모리의 구성" 이다.

스택 영역은 주로 지역변수, 매개변수, 함수의 반환값, 함수 호출의 주소 등이 저장된다.

힙영역은 주로 동적 할당을 할 때 사용되는 영역인데 다들 잘 알듯이

c++에서 new, delete이 c 에서 malloc, free 등이 있는데 동적 할당을 하고 사용을 했으면 해제 하는것에도 주의를

기울여 주어야 할것이다. 

# 다른 영역의 메모리를 사용할 때의 속도의 차이는 어떻게 될까?

- 이를 한번 알아보도록 하자.!

- 배열은  int 형으로 크기는 10000

- 충분한 횟수의 함수 호출(1000001)

-#include<time.h> , clock_t 를 이용한 시간 계산

 1. 배열을 정적영역에 선언해서 할당 받는 함수.

 2. 배열을 스택영역에 선언해서 할당 받는 함수.

 3. 배열을 힙영역에 선언해서 할당 받는 함수.

코드의 이해는 어렵지 않을 것이다. 다음과 같다.

결과는 어떻게 될까?.....

<결과화면>

위와 같다. 시간 자체 값은 변경될수 있지만

비교를 해보면 

정적영역에 선언   <   스택영역에 선언  <  힙영역에 선언

순이다.

동적할당의 경우

-컴퓨터의 저장소는 <  레지스터 / 캐쉬 L1 / 캐쉬 L2  /  memory / HDD >

 순으로 왼쪽에 있는 저장장치 일수록 속도가 빠르고 용량이 작으며 용량당 가격이 비싸다.

오른쪽으로 갈수록 느리지만 용량이 크고 값이 싸다

그래서 OS에게 요청해서 memory allocation 은 memory에서 일어나므로 느릴수 밖에 없다.

일반적인 힙 성능 문제들이 있다.

- 할당 작업으로 인한 속도 저하

        만약 사용가능한 블록이 사용가능 목록에 없다면 런타임에 더 큰 블록을 찾거나 새블록을 할당 받아와야한다.

- 해체 작업으로 인한 속도저하

- 힙 경합으로 인한 속도 저하 

        두개이상의 쓰레드가 접근 하려고 하는 경우 한 쪽 작업이 완료되어야 접근가능

-힙 손상으로 인한 속도 저하

알고 싶었던 내용과 그러한 현상이 나타난 이유를 기재 해보았습니다.

틀린 부분이 있을 수 있습니다. 알려주시면 수정하겠습니다. !