스택 - 후위표기식

계산기 문자열로 된 계산식이 주어질 때, 스택을 이용하여 계산식의 값을 계산할 수 있다 중위 표기법의 수식을 스택을 이용하여 후위 표기법으로 바꾼다 후위 표기법의 수식을 스택을 이용하여 계산한다 중위 표기법의 수식을 후위 표기법으로 변환하는 방법 수식을 하나씩 읽는다 수식이 피연산자이면 출력한다 수식이 연산자이면 스택에 push한다 연산자의 우선순위를 따진다 더이상 읽을 수식이 없으면 스택에 있는 연산자를 모두 pop한다 변환 방법의 예 1. 덧셈과 뺄셈의 경우 연산자는 스택에 push, 피연산자는 출력하기 스택에 사칙연산 우선순위가 동등한 연산이 있을 경우 해당 연산을 pop한 후 push하기 중위 표기식이 3+4+5 인 경우의 예 3은 피연산자이므로 출력한다 +는 연산자이므로 push한다 4는 피연산..

스택 - 괄호검사, DFS

스택의 구현 스택을 구현하기 위해서 필요한 자료구조 - 자료를 선형으로 저장할 저장소. 배열을 이용하여 스택 구현이 가능하다 스택의 연산 삽입(push) - 저장소에 자료를 저장한다 삭제(pop) - 저장소에서 자료를 꺼낸다 isEmpty - 스택이 공백인지 아닌지를 확인한다 peek - 스택이 top에 있는 item을 반환한다 static int st[] = new int [10]; int top = -1; // 스택에 마지막 삽입된 원소의 위치를 가리킴 st[++top] = 1; // 단순하게 구현한push st[top--] // 단순하게 구현한 pop // 간단하게 push 구현 void push(int x) { if (++top > st.length) { // overflow } else { st..

시간복잡도 분할 상환 분석(동적 배열의 추가 연산)

동적 배열의 추가(append) 연산 동적 배열의 추가 연산의 시간 복잡도를 계산해보자 다음과 같은 배열에 새로운 데이터를 추가한다고 하자 두 가지 경우에 대해서 생각해 볼 수 있다 1. 배열에 남는 공간이 있을 때 이 경우는 그냥 빈 공간에 데이터를 저장하면 되므로 시간 복잡도는 O(1)이다 2. 배열이 꽉 찼을 때 이 경우는 기존의 배열보다 큰 배열을 만들고 기존 배열에서 새로운 배열로 값을 다 복사해야 된다 기존 배열의 0번 인덱스에 접근해서 값을 복사하고 새 배열의 0번 인덱스에 접근해서 값을 붙여 넣고... 이미 있던 n개의 데이터를 복사해야 되므로 O(n)이 되고 새로운 데이터를 추가해야 되므로 O(1)이 되어 총 O(n+1) = O(n)이 된다 정리 배열에 남는 공간이 있을 때: O(1) 배..