일단 정리해 놓은 부분만 올리자...
Stack(스택)
LIFO(후입선출)인건 알겠는데 그 특성이 어디에 좋은 건가?
- 잠시 하던 일을 멈추고, 다른 볼일을 보고 돌아올 때 좋다.
- 예를 들어 게임을 일시 정지하고 심부름을 가야한다고 생각해보자
- 게임을 하고 있는 초기 스택은 [ 게임 ] 이런 상태다.
- 심부름 명령이 들어오면 stack의 상태는 [ 게임 , 심부름 ] 가 된다.
- 심부름을 완료했다면 stack은 pop되어 다시 [ 게임 ]가 된다.
- 재귀함수 호출을 관리할 때의 경우도 위와 같은 방식으로 생각하면 편하다.
- 예를 들어 게임을 일시 정지하고 심부름을 가야한다고 생각해보자
- 데이터의 역순 처리가 필요한 경우
- 백준 문제풀이에서 짝을 맞추는 상황에서 굉장히 유용하다.
어떤 알고리즘에서 주로 사용되나?
- DFS
- 재귀 또는 스택을 사용해 구현한다.
- 재귀함수가 스택이라 생각하면 편하다.
창의적이다 느낀 코드 : O(1)으로 stack내에서 최소값을 찾기
- stack을 2개 써서 구현하면 가능하다
- 왼쪽 : 그냥 스택 , 오른쪽 : 왼쪽에 push될 때 갱신되는 최솟값만 넣는 스택
(살려줘...)
'SW 정글 일지' 카테고리의 다른 글
정글 개발일지 week10 핀토스의 마무리 (0) | 2024.05.28 |
---|---|
정글 개발일지week09 (1) | 2024.05.21 |
정글 개발일지 week08 (0) | 2024.05.14 |
정글 개발일지 week07 (0) | 2024.05.02 |
정글 에세이 : 과거와 앞으로의 정글 (1) | 2024.03.16 |