Kwin's Development Diary.

Stack : 후입 선출(LIFO: Last In First Out)의 성격을 지닌 자료구조이다. [자료구조] 스택 (Stack)에 대한 설명글 [자료구조] 스택 (Stack) 스택(stack) - 스택에 저장된 원소는 top으로 정한 곳만 접근이 가능하다. ㄴ 후입 선출 구조(LIFO, Last-In-First-Out) : 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제된다. 스택의 연산 kwin0825.tistory.com 선언 import java.util.Stack; Stack 변수명 = new Stack(); ㄴ 위 같은 경우는 자료형에 넣은 자료형만 삽입, 삭제 가능 Stack 변수명 = new Stack(); ㄴ 위 같은 경우는 어떤 자료형이든 삽입, 삭제 가능(이전에 int형을..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 문..

문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()")와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는..

문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주..

문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보..

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열이 VPS..

수식의 표기법 - 전위 표기법 (prefix notation) : 연산자를 피연산자 앞에 표기하는 방법 (ex +AB) - 중위 표기법 (infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 (ex A+B) - 후위 표기법 (postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 (ex AB+) 중위 표기식 ㅡ변환ㅡ> 전위 표기식 ① 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현 ② 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동 ③ 괄호 제거 EX) A * B - C / D 1단계 : ((A * B) - (C / D)) 2단계 : -(*(A B) / (C D)) 3단계 : -*AB/CD 중위 표기식 ㅡ변환ㅡ> 후위 표기식 ① 수식의 각 연산..

스택(stack) - 스택에 저장된 원소는 top으로 정한 곳만 접근이 가능하다. ㄴ 후입 선출 구조(LIFO, Last-In-First-Out) : 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제된다. 스택의 연산 - 삽입(push) ① top의 위치를 하나 증가(∵ top은 스택에서 마지막 자료를 가리키기 때문) 이때, 만약 top의 위치가 스택의 크기보다 커지면 오버플로우가 발생하므로 연산 수행하지 않고 종료. ② 스택의 top이 가리키는 위치에 삽입 -①-> -②-> ←top C ←top B ←top B B A A A - 삭제(pop) ① 스택이 공백이 아니라면 top이 가리키는 원소를 먼저 반환 ② 스택의 top의 위치를 그 아래의 원소로 변경(top 위치 하나 감소) -①-> -②..