[백준, 자바] 2493번 탑, 스택(Stack)
1. 문제https://www.acmicpc.net/problem/2493 2. 풀이N = 500,000이므로 시간 복잡도 O(N^2)가 걸리는 코드를 작성한다면 시간 초과가 발생한다.이 문제는 시간 복잡도 O(N)으로 풀 수 있어야 한다.현재 건물(i)에서 왼쪽으로 레이저를 쏜다는 것은 (j 그렇다면 (j 그러나 for문을 사용하여 (0, i - 1) 건물을 모두 탐색한다면 시간 복잡도 O(N^2)이 된다. 이 문제는 스택을 사용하여 최근에 접근한 건물부터 탐색하여 해결할 수 있다.스택의 조건은 다음과 같다.현재 건물보다 높은 건물이 나올 때까지 스택에서 건물을 제거한다.스택 최상단에 있는 건물이 현재 건물보다 높은 건물이다.스택이 비어있다면 현재 건물보다 높은 건물이 없다는 것이다.예를 들어, 높이가..
1. 후위 표기식이란?연산자를 피연산자 뒤에 배치하는 표기 방식이다.일반적인 중위 표기식(Infix)에서는 피연산자 사이에 연산자가 위치하지만, 후위 표기식은 피연산자 뒤에 연산자가 위치한다. 중위 표기식1 + 2A + B * C 후위 표기식12+A B C * + 후위 표기식의 특징으로는 괄호가 필요하지 않다는 것이다. 중위 표기식(A + B) * C후위 표기식A B + C * 2. 후위 표기식 계산 방법후위 표기식은 스택(Stack) 자료구조를 사용하여 계산할 수 있다.피연산자는 스택에 저장한다. 스택은 LIFO(Last In, First Out) 구조이다.연산자를 만나면 스택에서 피연산자 두 개를 꺼내고, 연산자와 계산한다. 계산된 값은 다시 스택에 저장한다.연산을 모두 마쳤을 때 스택에 저장된 값..