17298:오큰수 [백준 문제풀이][Python]
문제:https://www.acmicpc.net/problem/17298난이도: 골드 4스택을 이용하여 최댓값을 구하는 문제. 처음 보는 개념이라 이해하는데 꽤 애를 먹었다.아이디어1처음에는 단순하게 최댓값을 찾아서 계속 업데이트 해주는 방식을 생각해봤는데, 단순 계산으로도 O(n^2)이 넘어서 안된다. 입력 값이 10만이기 때문에 O(nlogn) 또는 O(n)으로 풀어야 된다.아이디어2다음은 스택을 사용한 풀이이다. 혼자 생각한건 아니고, 대충 찾아보면서 삽질 좀 했다.스택은 선입후출(Last In Fisrt Out)의 방식을 가진 자료구조로, 선입선출 방식인 큐와 대비되는 방식이다. 이를 이용해서 최댓값을 구할 수 있는데, 스택을 하나의 탑으로 보자면, 값이 들어올때마다 탑의 맨 윗부분부터 비교하면서..
2024.07.24