위상 정렬을 구하는 두 가지 방법

위상 정렬이란 다음과 같은 그래프가 있다 각 노드는 해야할 작업이며 작업은 이전 작업이 끝나야 시작할 수 있다 예를 들어 3번 작업을 하기 위해서는 2번 작업을 먼저 해야하고 2번 작업을 하기 위해서는 1번 작업을 먼저해야한다 그러므로 작업순서는 1 2 3이 된다 그러면 다음과 같은 경우를 보자 3번이나 5번 작업을 하기 위해서는 2번 작업을 먼저 해야하고 2번 작업을 하기 위해서는 1번과 4번 작업을 해야한다 그러므로 작업 순서는 1 4 2 3 5 or 4 1 2 3 5 or 1 4 2 5 3 or 4 1 2 5 3 이 될 수 있다 이처럼 작업 순서가 있는 경우 작업 순서를 구하는 것을 위상 정렬이라 한다 위상 정렬하는 방법 위상 정렬을 구하는 방법에는 두 가지가 있다 진입 차수가 0인 노드를 지우면서..

스택 - 괄호검사, 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..