고코딩

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 ..

문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다. 이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여..

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

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 예제 입력 예제 출력 7 3 정답 처음에는 N만큼의 배열을 만든..

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

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

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

JAVA를 어느정도 공부하다보면 예외처리 오류를 해줘야 한다는 구문을 많이 만날 수 있었다. 입력할때마다 예외가 발생해 항상 try~catch구문으로 예외처리를 해주었는데 사실 정확한 의미와 구성 방식을 몰랐다. 심지어 throws와 throw는 누구도 알려준적이 없어서 처음으로 자바프레임워크를 사용했을 때 처음 보는 수식어 때문에 많이 당황했었다. 이 포스팅으로 예외처리에 대한 간단한 이해를 해보자. try~catch와 throws의 차이 try~catch의 의미를 검색해보면 발생한 예외를 처리한다. 라고 되어있고, throws는 예외처리가 발생한 메소드를 호출한 메소드에게 예외를 처리한다, 라고 되어있다. 처음 이 글을 읽었을때는 이게 무슨소리인가 싶었다. 하지만 잘 곱씹어 읽어보면 처리하는 순간이 ..

지인이 코딩테스트 문제를 풀던중 계속해서 메모리 초과가 발생하는 문제가 있었다. 문자열들을 입력받아 정렬하는 문제였는데 아무리 봐도 메모리초과가 발생할만한 곳이 없었다. 문자열도 String이 아닌 StringBuffer로 받아서 사용하고 있었기에 의심을 하지 못했다. 문제는 + 연산에서 발생했다. 생각해보니 StringBuffer에서는 append를 사용하도록 기능을 주고 있었다. 그럼 append와 + 연산은 무슨 차이일까? String, StringBuffer,StringBuilder의 특징 String과 StringBuffer, StringBuilder의 가장 큰 차이점은 String은 Imutable이라는 점이다. Imutable은 불변하지 않는 이라는 뜻을 가지고 있는데 String은 문자열 ..

순회는 이진 트리에 있는 모든 노드를 한번씩 방문하여 노드가 가지고 있는 데이터를 처리하는 것이다. 여기서 처리라 함은 노드 안의 데이터를 출력할 수도 있고, 데이터 값을 변환할수도 있다. 순회의 종류에는 총3가지가 있다. 전위순회 중위순회 후위순회 현재 노드를 방문하여 데이터를 읽는 작업을 D또는 V라고 한다. 현재 노드의 왼쪽 서브트리로 이동하는 작업을 L이라고 한다. 현재 노드의 오른쪽 서브트리로 이동하는 작업을 R이라고 한다. 전위 순회 전위 순회의 순서는 현재노드(V) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순으로 순회 한다. VLR 이라고도 부른다. 전위 순회로 트리를 순회하면 방문하는 노드의 순서이다. 중위 순회 중위 순회의 순서는 왼쪽 서브트리(L) -> 현재노드(V) -> 오..

앞서 포스팅한 스택과 큐는 자료구조에서 선형 구조라고 한다. 선형 구조는 데이터가 순차적으로 나열되어진 형태를 말하는데, 트리는 비선형구조로 이루어져있다. 비선형구조는 데이터가 계층적(혹은 망)으로 구성되어있다. 선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 들어나느데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 보통 컴퓨터의 폴더 구조가 대표적인 트리의 형태를 가지고 있다. 트리(Tree)의 개념 계층적인 자료를 표현하는데 적합한 자료구조 이다. 노드(node)와 간선(edge)"브랜치(Branch)라고도 불린다" 로 구성되어 있다. 제일 최상위에 위치한 노드를 루트노드(Root Node)라 부르고 나머지 노드들을 서브..

Queue Queue는 자료구조의 스택과 반대의 구조라고 생각하면 된다. 큐는 FIFO(First In First Out)의 형태를 가지게 됩니다. 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다. Enqueue : 큐 맨 뒤에 데이터를 추가 Dequeue : 큐 맨 앞쪽의 데이터를 삭제 특징 큐의 한쪽 끝은 Front로 정하여 삭제연산만 수행한다. 다른 한쪽 끝은 Rear로 정하여 삽입연삼나 수행한다. 그래프 넓이 우선 탐색(BFS)에서 사용된다. 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다. 먼저 들어온 입력먼저 처리 Java로 큐를 구현 먼저 자바에서 제공해주는 Queue클래스를 이용해 Queue를 구현해보자. 자바에서는 스택을..