백준

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 문제 정점의 개수 N과 간선의 개수 M이 주어지고 간선이 연결된 정점 2개를 M개 주어진다. 몇 개의 연결 요소가 생기는 지 구하시오. 풀이 노드와 무방향 간선이 주어졌을 때 몇 개의 연결 요소가 만들어지는지 구하는 문제이다. 무방향 그래프이므로 간선의 양 쪽 모두를 담아 두어도 된다. 모든 List를 돌면서 해당 정점과 연결된 모든 정점을 방문하면서 Visit를 체크한다. for(int i=1; i

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제 주어진 배열에서 A[i]의 이전 A[i-M+1] ~ A[i] 값들 중 최솟값을 정해서 출력하라. 풀이 덱을 사용해서 슬라이딩 윈도를 구현하였다. 덱의 마지막부터 살펴보면서 자신보다 큰 값이 있다면 삭제한다. 자신을 덱의 마지막에 추가한다. 덱의 첫 번째가 index 범위를 벗어난다면 삭제한다. 덱의 첫 번째 값이 최소값이므로 buffer writer에 추가한다. import java.util.*; import java.lang..

12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 문제 주어진 문자열의 부분문자열이 주어진 요구사항을 만족하는 경우의 수를 출력 풀이 다음과 같은 규칙으로 해결하였다. 먼저 요구하는 조합을 배열에 넣고 이때 0이라면 check++해주었다. 초기화하는 로직으로 end값을 M까지 높이면서 arr[end]의 값에 따라 pass의 값을 추가해주었다. 값을 추가했을 때 만약 요구하는 조합과 같다면 check++했다. 이제 end를 1칸씩 늘리고 start도 한 칸씩 늘리면서 pass를 갱신해갔다. ..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 자신을 기준으로 우측에 있는 수열들 중 가장 가까운 값을 오큰수라고 한다. 각 수열을 기준으로 모든 오큰수를 출력하세요. 풀이 수열을 모두 배열에 저장한다. 수열 전체를 반복하는데 만약 현재 수열보다 작은 수를 가진 인덱스가 있다면 오큰수 배열에 현재 값을 넣고 pop해준다. 그리고 현재 인덱스를 큐에 담는다. 만약 오큰수 배열에 0이 들어 있다면 오큰수가 없는 것이므로 -1을 출력하고 오큰수가 있다면 오큰수를 출력한다. import java.io.BufferedRea..

11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 절댓값 힙은 절댓값이 가장 작은 숫자를 출력한다. (절댓값이 같다면 작은 값을 먼저 출력) 입력에 0이 주어진다면 값을 출력하고 나머지 값이 들어온다면 값을 절댓값 힙에 넣는다. (입력이 0이고 힙이 비어있다면 0을 출력) N번의 값이 주어질 때 값을 출력하시오. 풀이 우선순위 큐는 람다식을 사용하여 만들었다. 이 람다식의 리턴값이 양수라면 첫 번째 값이 크다고 인식하고, 람다식이 음수라면 두 번째 값이 크다고 인식하여 우선순위를 정한다..

2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 N장의 카드 (1부터 N)이 있을 때, 다음의 규칙에 따라 카드를 제거해서 남은 1장을 출력한다. 가장 아래 (초기값으로 가장 작은 수)를 삭제한다. 가장 아래값을 가장 위로 이동시킨다. 한 장이 남을 때 까지 반복한다. 풀이 문제에 나온 순서대로 규칙을 적용하였다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { public static v..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 N까지의 수열이 있을 때 스택으로 출력이 가능한지 여부 및 push pop 순서 출력 풀이 다음의 규칙을 통해서 문제를 해결했다. 입력받은 값이 현재 수열값보다 같거나 작을때까지 push한다. (”+” 출력) 만약 스택 top의 값이 입력받은 값과 같다면 pop한다. (”-” 출력) 만약 스택 top의 값이 입력받은 값과 다르다면 만들어질 수 없는 수열이기 때문에 NO를 출력..

2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 문제 구간 합들 중에서 K가 되는 구간의 경우의 수를 구하시오. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] arg..