모노토닉 스택(monotonic stack)을 이용한 나보다 큰 첫 번째 수 찾기 문제(오큰수,NGE,next greater element)

1. 모노토닉 스택(monotonic stack) 스택 내부의 원소들을 항상 오름차순, 혹은 내림차순 상태를 유지하도록 만드는 자료구조 나보다 크거나, 작은 숫자가 언제 처음 나오는지를 찾는데 유용하다. 알고리즘 문제에서 보통, "배열에서 나보다 크면서 오른쪽에 있는 수 중 첫번째 수는?" 예를 들어, [5,3,1,4,2]가 있다고 하자. 각 숫자에 대해서 "오른쪽에 있는 나보다 큰 첫번째 수"들을 모두 O(N)에 찾으라고 한다면? 스택 []을 두고, 왼쪽부터 오른쪽 차례대로 순회한다. 스택이 비어있으니까 [5] 2번째 3이 들어오는데, 스택의 마지막 수 5가 3보다 더 크므로 그대로 입장 [5,3] 3번째 1이 들어오는데 스택의 마지막 수 3이 1보다 더 크므로 [5,3,1] 4번째 4가 들어오는데 ..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 12. 23.
• textsms

O(1)에 스택의 최솟값을 찾는 min stack 기법?

https://www.acmicpc.net/problem/8858 은행원이 현금 보유액 S를 가지고 있다. 고객이 입금을 하러 온다면, 입금 금액을 기록하고 고객이 가져온 현금을 새 봉투에 넣은 다음, 이전 입금 봉투 위에 쌓는다. 입금 봉투는 이처럼 스택 구조로 쌓이게 된다. 고객이 X원을 출금하러 온다면, 봉투 스택이 비어있는 경우 전액을 현금 보유액 S에서 지급 봉투에 든 금액들 중 가장 작은 금액보다 X가 작다면, 전액을 현금 보유액 S에서 지급 그렇지 않다면, 봉투 스택의 맨 위에서부터 하나씩 꺼낸 다음, 필요한 금액을 충당 마지막에 꺼낸 봉투에서 일부 금액만 사용하면, 남은 돈은 현금 보유액 S로 넣는다. 만약 모든 봉투를 다 사용했는데 X를 다 지급하지 못하면 남은 금액은 현금 보유액 S에..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 11. 27.
• textsms

스택으로 쌓아놓은 수열에서 조건을 만족하는 값들이 언제부터 다 나오는가?

17162번: 가희의 수열놀이 (Small) 여러개의 쿼리가 주어지는데,  1. 스택의 맨 뒤에 숫자를 추가 2. 스택이 비어있지 않으면 맨 뒤의 원소를 제거 3. 맨 뒤에서부터 최소 몇개의 수를 선택해야, 이들을 mod로 나누었을때 0,1,2,..,mod-1이 최소 1개 이상 나타나는가? 예를 들어 [2,3]인 경우 4로 나누면 나머지는 [2,3]인데, 여기서 0,1이 없으므로 -1 [2,3,1,4]인 경우 4로 나누면 나머지는 [2,3,1,0]인데 여기서 0,1,2,3이 모두 나왔으므로 4 -----------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 2. 27.
• textsms

O(N)으로 순서쌍 찾기1 - 기울기가 K인 직선의 개수

28137번: 뭐라고? 안들려 N개의 좌표가 주어질때, A,B를 두개의 좌표에 배치하여 이들을 이은 직선의 기울기가 K인 경우의 수를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------------------- 2개의 점을 선택하는 순서쌍을 찾는거니까 단순하게 이중포문을 생각할 수 있지만 N  O(N)에는 찾아야한다는 소리인데... O(N)에 순서쌍을 찾는 문제들은 보통 해시맵(dict)을 쓰는 경우가 많다 두 점을 이은 직선의 기울기가 k라는 뜻은? 두 점의 좌표 (x1,y1), (x2,y2..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 2. 19.
• textsms

가장 긴 연속하는 올바른 괄호 부분 문자열의 길이 구하는 알고리즘

15926번: 현욱은 괄호왕이야!! 괄호로만 이루어진 문자열이 주어질때 연속하는 부분 문자열 중 가장 긴 올바른 괄호 문자열의 길이를 구하는 문제 ------------------------------------------------------------------------------------------------------------------------------------------------------- 올바른 괄호 문자열을 구하는 알고리즘은 스택을 이용해서  스택이 비어있는데 (이 들어오면 넣고 스택이 비어있지 않을때, (이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 (이 들어올 수 있고 )이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 제거하고 마지막에 스택이 비면 올바른 ..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 2. 17.
• textsms

코딩테스트 복기 - 배열에서 특정 수보다 작은 수 중 가장 가까운 수를 찾는 방법(find nearest element than smaller one on the left side)

1. 문제 배열이 주어질때, 특정한 수보다 작으면서 가장 가까운 수를 찾고자 한다. 예를 들어 [3,1,2,10,5,6,4]가 주어질때, 10보다 작으면서 가까운 수는 바로 옆에 2와 5가 있다 이 경우 인덱스가 더 작은 2를 출력하고 싶고 1의 경우는 만족하는 원소가 없으므로 -1을 출력한다. 2. 풀이 - 왼쪽에서 더 작은 원소의 위치를 찾기 생각보다 어렵던데..? 그냥 많이 어려운데 적어도 생각나는건 $O(N^{2})$ 브루트 포스뿐.. 하지만 n이 10만이 넘어가는데 브루트 포스가 통과할리는 없을 것 같고 스택을 이용해서 O(N)에 효율적으로 풀 수 있다고 한다 알고리즘을 보면 의외로 간단하네.. 생각하기가 어렵지 일단 A의 i번째 원소에 대해 왼쪽에서 작으면서 가장 가까운 원소를 찾는다 그래서 ..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2023. 5. 22.
• textsms