본문 바로가기

Algorithm/Baekjoon Oline Judge - Java

(76)
[백준] 24479_깊이우선탐색1, 24480_깊이우선탐색2 / DFS, 재귀 Sliver 문제 N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.  입력 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000),간선의 수 M (1 ≤ M ≤ 200,000),시작 정점 R (1 ≤ R ≤ N)이 주어진다.다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u 모든 간선의 (u, v) 쌍의 값은 서로 다르다.  출력 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 ..
[백준] 1025_등수구하기 Sliver  문제 태수가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다.이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다.이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다.예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다 랭킹 리스트에 올라 갈 수 있는 점수의 개수 P가 주어진다.그리고 리스트에 있는 점수 N개가 비오름차순으로 주어지고, 태수의 새로운 점수가 주어진다.이때, 태수의 새로운 점수가 랭킹 리스트에서 몇 등 하는지 구하는 프로그램을 작성하시오.만약 점수가 랭킹 리스트에 올라갈 수 없을 정도로 ..
[백준] 1021_회전하는큐 / Deque 덱, LinkedList Sliver 문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때,..
[백준] 1026_보물 / visited Silver 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.S의 최솟값을 출력하는 프로그램을 작성하시오.  입력 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.  출력 첫째 줄에 S의 최솟값을 출력..
[백준] 10844_쉬운계단수 / DP Silver  문제 45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자.0으로 시작하는 수는 계단수가 아니다.  입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.  출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.   풀이 import java.util.*;class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long ..
[백준] 2293_동전1 / DP Gold  문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.  입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.  출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.    풀이-1 DFS import java.util.*;class Main { static int[] arr; static int coun..
[백준] 2247_별찍기10 / 재귀 Gold  문제 재귀적인 패턴으로 별을 찍어 보자.N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.**** **** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.  입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k   출력 첫째 줄부터 N번째 줄까지 별을 출력한다.    풀이 import java.util.*;class Main { static String[][] arr ; public sta..
[백준] 1806_부분합 / 투포인터 Gold  문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.  입력 첫째 줄에 N (10 ≤ N 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.  출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.     풀이 import java.util.*;import java.io.*; // BufferedReader, InputStreamReaderclass Main { public static void main(String[] arg..