스택
-
백준 17298 오큰수Algorithm/BOJ 2021. 4. 6. 18:20
출처: www.acmicpc.net/problem/17298 분류: 스택 접근방식 스택을 이용해서 풀 수 있었는데, 처음에 접근을 떠올리지 못해서 다른 분들의 풀이를 참고해서 겨우 풀었습니다. 아직 오큰수를 찾지 못한 수들을 스택에 담아줍니다. 현재 a[i]가 스택의 top 보다 크다면 top의 오큰수는 a[i]가 됩니다. 스택의 있는 수들은 아직 오큰수를 찾지 못한 수들이기 때문에 오른쪽에 있으면서 가장 큰 수가 바로 a[i] 입니다. 따라서 스택에는 오큰수를 찾지 못한 인덱스를 넣어주면서 a[i] 보다 크다면 빼서 해당 인덱스의 오큰수를 a[i]로 기록해주고, 다음으로 a[i]의 오큰수를 또 찾아야 하기 때문에 stack에 a[i]의 인덱스 i 를 넣어주고 넘어가줍니다. for i in 0..
-
StackComputer Science/DataStructure 2020. 3. 3. 14:54
- 선형 자료구조 - LIFO (후입선출) 선형 자료구조의 일종. Last In First Out (LIFO) 방식으로, 나중에 들어온(push) 원소가 먼저 나온다.(pop) 접시를 위로 쌓아놓은 형태를 떠올리면 쉽다. 따라서 스택의 앞에 원소를 넣는 것은 O(n)이고 스택의 뒤에 추가하는 것은 O(1)의 시간복잡도를 갖는다. 참고로 CPU는 function 이나 method의 return 주소를 스택에 넣는데, 재귀 함수 등과 같이 함수가 종료되기 전에 너무 많은 함수를 호출해 CPU의 스택이 부족해지면 "stack over flow"가 발생한다. Implement Swift는 사실상 내부적으로 Stack을 이미 지원하고 있다고 볼 수 있다. public struct Stack { fileprivat..