자바

[백준] 1966 - 프린터 큐 (자바/Java)

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

[백준] 17298 - 오큰수 (자바/Java)

문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,00..

[백준] 1874 - 스택수열 (자바/Java)

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

[백준] 2559 - 수열 (자바/Java)

문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며, 이때, 온도의 합이 가장 큰 값은 31이다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫..

[백준] 2304 - 창고 다각형 (자바/Java)

문제 N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 지붕의 가장자리는 땅에 닿아야 한다. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다. 그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다..

[백준] 1158 - 요세푸스 문제 (자바/Java)

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

[알고리즘] 삽입 정렬 Insertion Sort (자바/Java)

목차 삽입 정렬 0번째부터 i번째까지 정렬된 배열의 크기를 증가시키며 정렬하는 알고리즘 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열 만들기! 시간 복잡도: $O(n^2)$ 과정 i번째 원소를 정렬할 차례 i-1번째까지의 원소들은 정렬되어 있음 i-1부터 0까지의 원소들과 i번째 원소(key)를 비교하며, i번째 원소보다 작은 원소를 만나면 break, i번째 원소보다 크다면 해당 원소를 오른쪽으로 한 칸씩 shift break한 원소 다음 자리에 i번째 원소를 삽입 1부터 마지막 원소까지 반복 1 0번째 원소는 정렬된 상태 i=1, 10 10..

[자료구조] 트리 & 이진 탐색 트리 Binary Search Tree (자바/Java)

목차 트리 (Tree) 비-선형 자료 구조 (Non-Linear) 선형 자료 구조: 구조에 저장될 데이터들이 순차적으로 저장되는 형태 ArrayList, LinkedList, Map, Stack, Queue 등 비-선형 자료 구조: 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조 Tree 검색 트리 내장 vs 외장 검색 트리 내장 검색 트리: 메인 메모리 내에 존재 외장 검색 트리: 검색 트리가 외부(주로 디스크)에 존재-검색 트리 전체를 메인 메모리에 올려놓고 쓸 수 없는 경우 이진 검색 트리(Binary Search Tree) 특성 각 노드는 키값을 하나씩 갖는다. 이 키값은 모두 다르다. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다. 임의 노드의 키값은 자기..

[자료구조] 스택 Stack 활용: 후위 표기식 계산기 (자바/Java)

목차 스택을 활용하여 후위 표기식 계산기를 구현할 수 있다. 먼저 중위표기식을 후위 표기식으로 바꾸고, 이를 다시 계산해야 한다. 1. 중위 표기식 → 후위 표기식 이 과정이 상대적으로 까다롭다. 먼저 연산자 우선순위를 고려해야 한다. 연산자는 사칙 연산(+ - * /)과 괄호만 들어온다고 가정한다. 1. 입력이 연산자가 아닌 경우 바로 출력해준다. StringBuilder를 사용하여 sb에 append하였다. 2. 입력이 연산자인 경우 2-1. 괄호인 경우 괄호는 연산자 중에서도 특수한 경우이다. 먼저 좌괄호 '('인 경우 stack에 그냥 push한다. 그리고 우괄호 ')'가 나오면, 좌괄호가 나올 때까지 stack에 있는 연산자들을 모두 pop하여 출력한다. 그리고 좌괄호는 연산에 포함되지 않으니,..

[백준] 4949 - 균형잡힌 세상 (자바/Java) 스택 Stack

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