딩신 - 코딩의 신

괄호의 값 문제4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.‘()’ 인 괄호열의 값은 2이다.‘[]’ 인 괄호열의 값은 3이다.‘(X)’ 의 괄호값은 2..

Advanced 정렬하기 문제서로 다른 n개의 정수가 주어질 때, 이를 1초안에 오름차순으로 정렬하는 프로그램을 작성하시오. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다. 출력첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다. 예제 입력10 2 5 3 4 8 7 -1 9 10 2예제 출력-1 2 2 3 4 5 7 8 9 10 코드//merge sort import java.util.*; public class Main { public static ArrayList box = new ArrayList(); public static int[] sorted; //첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100..

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

원형 큐 구현하기 문제이 문제에서는 원형 큐를 구현한다. 큐 구현하기 문제에서 설명했듯이, 선형 큐는 “큐가 실제로는 비어있어도 Push와 Pop을 할 수 없는" 문제가 발생할 수 있다. 원형 큐는 이 문제를 해결한다. 원형 큐 역시 큐와 마찬가지로 다음 세 개의 연산을 지원한다. Push X : 큐에 정수 X를 push한다. 만약 rear 포인터가 더 이상 뒤로 갈 수 없다면, “Overflow”를 출력한다. Pop : 큐에서 정수 하나를 pop한다. 만약 front 포인터가 더 이상 뒤로 갈 수 없다면, “Underflow”를 출력한다. Front : 큐의 front에 있는 정수를 출력한다. 만약 큐가 비어있다면 “NULL”을 출력한다. 크기가 n인 원형 큐에 m개의 연산을 하는 프로그램을 작성하시오..

큐 구현하기 문제이 문제에서는 큐를 구현한다. 큐는 다음 세 개의 연산을 지원한다. Push X : 큐에 정수 X를 push한다. 만약 rear 포인터가 더 이상 뒤로 갈 수 없다면, “Overflow”를 출력한다. Pop : 큐에서 정수 하나를 pop한다. 만약 front 포인터가 더 이상 뒤로 갈 수 없다면, “Underflow”를 출력한다. Front : 큐의 front에 있는 정수를 출력한다. 만약 큐가 비어있다면 “NULL”을 출력한다. 크기가 n인 큐에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”, Top은 “3”으로 표현한다. 다음은 크기 4인 큐에 10개의 연산이 입력으로 주어졌을 때의 입력과 출력의 예이다. 참고로, 다음 예제는 선형..

스택 구현하기 문제이 문제에서는 스택을 구현한다. 스택은 다음 세 개의 연산을 지원한다. Push X : 스택에 정수 X를 push한다. 만약 스택이 꽉 차서 push를 할 수 없다면, “Overflow”를 출력한다. Pop : 스택에서 정수 하나를 pop한다. 만약 스택이 비어있어서 pop을 할 수 없다면, “Underflow”를 출력한다. Top : 스택의 top에 있는 정수를 출력한다. 만약 스택이 비어있다면 “NULL”을 출력한다. 크기가 n인 스택에 m개의 연산을 하는 프로그램을 작성하시오. 입력의 편의를 위해서 Push는 “1”, Pop은 “2”, Top은 “3”으로 표현한다. 다음은 크기 4인 스택에 10개의 연산이 입력으로 주어졌을 때의 입력과 출력의 예이다.XYZ 입력첫째 줄에 스택의 크..

숫자박스 (numberbox.cpp) 문제숫자박스에는 자연수들이 적혀있는 종이들이 N장 들어있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자가 상자 안에 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 윤성이가 가지고 있는 숫자 정보의 개수 N (1 ≤ N ≤ 300,000)이가 주어진다. 둘째 줄에는 숫자 정보들이 주어진다. 숫자는 1,000,000이하의 정수이다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 윤성이가 숫자 박스에 있는지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 1,000,000이하의 정수이다. 출력첫째 줄에 입력으로 주어진 M개의 숫자에..

쿼드트리 (quad.cpp) 문제그림 과 같은 이진 이미지는 0 혹은 1 로 자료를 표현한다.그림(b) 는 그림(a) 를 나타내는 배열을 나타낸다. 그림(b) 의 이진 이미지를 저장하기 위해 일명 쿼드트리 구조를 사용한다.쿼드 트리는 NN 배열을 N/2 N/2 크기로 4 등분 했을 때 모두 같은 값을 가지지 않는다면, 다시 N/2 * N/2 배열에서 같은 이진 값을 가지지 않는다면 다시 .....이런 식으로 진행하다 4 등분 된 값이 모두 같은 값을 가지면 확장이 종료된다.그림(c) 는 쿼드 트리의 확장이 종료된 후의 배열이 모습이다.그림(a) 에 있는 이진 이미지를 저장하지 않고 , 그림(c) 로 부터 엔코드된 그림(d) 처럼 쿼드 트리로 이미지를 저장한다.그림(d) 에서 각 노드는 그림(c) 에 있는..

전염병 문제철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다. 철수네 마을은 1번부터 N번까지 번호가 매겨져 있다. 철수네 마을의 구조는 꽤나 복잡한데, i번 마을에서 출발하면 ix2 번 마을에 갈 수 있고, 또한 i/3 번째 마을에도 갈 수 있다. 전염병은 사람에 의하여 옮는 것으로 알려져 있다. 따라서 i번 마을에 전염병이 돌게 되면, ix2 번 마을과 i/3 번 마을 역시 전염병이 돌게 된다. K번 마을이 가장 처음으로 전염병이 돌기 시작했을 때, 전염병이 돌지 않는 마을의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 전체 마을의 개수 N과, 처음으로 전염병이 돌기 시작한 마을 번호 K가 주어진다. ( 1 ≤..

미로찾기 문제아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다. 입력첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다. 출력(N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다. 예제 입력10 10 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1..