BOJ 1874 스택 수열

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

https://github.com/simjaemun2/BaekJoon/blob/ddca9cb6c5182a2621cd2c01829daedd8bab1c56/BOJ1874/BOJ18874.cpp

분류 : 스택

난이도 : MH

cnt = 스택에 push 한 값

cnt < input

-> 계속 push

스택.탑 != a

-> 답 없음

else

-> 팝, 다음 단계 계속

BOJ 10799 쇠막대기

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

https://github.com/simjaemun2/BaekJoon/blob/f863f80281b64f325831043f2d57789e125de9b6/BOJ10799/BOJ10799.cpp

난이도 : M

분류 : 스택

BOJ 2167 2차원 배열의 합

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

https://github.com/simjaemun2/BaekJoon/blob/f89717ec547b5feb53bf13c3ce97cd37771321bb/BOJ2167/BOJ2167.cpp

분류 : DP

난이도 : MH

BOJ 2163 초콜릿 자르기

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

https://github.com/simjaemun2/BaekJoon/blob/master/BOJ2163/BOJ2163.cpp

분류 : DP

난이도 : MH

a*b-1 로 간단하게 풀 수 있다

BOJ 11659 구간 합 구하기 4

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

https://github.com/simjaemun2/BaekJoon/blob/master/BOJ11659/BOJ11659.cpp

분류 : DP

난이도 : MH

BOJ 9012 괄호

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

https://github.com/simjaemun2/BaekJoon/blob/master/BOJ9012/BOJ9012.cpp

분류 : stack

난이도 : M

[Largest Rectangle in Histogram]

https://leetcode.com/problems/largest-rectangle-in-histogram/

stack을 이용해 O(n) 시간에 구할 수 있다.

height = [2,1,5,6,2,3]

아래와 같은 Histogram이 입력으로 들어온다고 가정하자.

모든 height를 방문하면서 stack에 집어 넣는데, 규칙은 다음과 같다.

현재 반복문의 인덱스를 i라고 할 때,

height[i] <= height[stack.top()] 인 모든 경우에 대하여

stack.pop()을 한 후, 사각형의 넓이를 계산하는 과정을 수행한다.

아래 그림에서 회색 음영의 사각형은 현재 stack에 추가되는 사각형을 의미한다.

점선 테두리의 사각형은 stack에서 pop 되는 사각형이고, 노란색 음영의 사각형은 이 떄 계산하는 사각형의 넓이를 의미한다.

모든 사각형이 stack에 추가되었을 때, stack에 남아 있는 사각형의 넓이를 계산할 수 없다. 따라서, height 배열의 마지막에 0 을 추가한 후, 반복문 순회를 시작해야 한다. 그러면 마지막에 남은 사각형의 넓이를 계산할 수 있다.

[Maximal Rectangle]

https://leetcode.com/problems/maximal-rectangle/

[Largest Rectangle in Histogram] 문제의 응용 버전이다.

입력으로 받은 큰 사각형에서 반복문을 통해 각 row마다 높이를 계산하는 작업을 전처리한 후, 각 row마다 [Largest Rectangle in Histogram] 문제처럼 stack을 이용한 sweeping 작업을 수행한다.

O(n^2) 의 시간이 걸린다.

DP로 문제를 푸는 방법은 답이 생각나지 않아서 해결하지 못했다.

[Maximal Square]

https://leetcode.com/problems/maximal-square/

[Maximal Rectangle]문제의 하위 버전이다.

DP를 이용하여 쉽게 풀 수 있다.

[Path Sum]

https://leetcode.com/problems/path-sum/

[Path Sum 2]

https://leetcode.com/problems/path-sum-ii/

[Binary Tree Paths]

https://leetcode.com/problems/binary-tree-paths/

모두 stack을 이용하여 풀 수 있다.

[Implement Stack using Queues]

https://leetcode.com/problems/implement-stack-using-queues/

[Implement Queue using Stacks]

https://leetcode.com/problems/implement-queue-using-stacks/

stack, queue를 2개씩 만들어서, 하나의 stack or queue에 pop()할 item을 하나씩 유지

[Simplify Path]

https://leetcode.com/problems/simplify-path/

stack

Python "///".split("/") = ['','','',''] 과 같이 리턴

[Palindrome Partitioning]

https://leetcode.com/problems/palindrome-partitioning/

def dfs(sublist, str)

if not str

ret += sublist

else

for str의 0번 인덱스 시작 길이가 1부터 len(str)까지의 모든 substring

if substring is palindrome

dfs(sublist += substring, str에서 substring을 제외한 나머지)

[Binary Tree Preorder, Inorder, Postorder]

https://leetcode.com/problems/binary-tree-preorder-traversal/

https://leetcode.com/problems/binary-tree-inorder-traversal/

https://leetcode.com/problems/binary-tree-postorder-traversal/

stack, hash

reverse(preorder) = postorder