알고리즘 - Baekjoon/Silver

[백준] 11576번 : Base Conversion Silver5(실버5) - JAVA[자바]

[Silver V] Base Conversion - 11576 문제 링크 성능 요약 메모리: 11556 KB, 시간: 80 ms 분류 구현, 수학, 정수론 제출 일자 2023년 11월 29일 09:26:12 문제 설명 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 세계에서도 프로그래밍을 하고 싶었던 정이는 백준 사이트에 접속하여 문제를 풀기로 하였다. 그러나 미래세계는 A진법을 사용하고 있었고, B진법을 사용하던 정이는 문제를 풀 수가 없었다. 뛰어난 프로그래머였던 정이는 A진법으로 나타낸 숫자를 B진법으로 변환시켜주는 프로그램을 작성하기로 하였다. N진법이란,..

[백준] 1992번 : 쿼드트리 Silver1(실버1) - JAVA[자바]

[Silver I] 쿼드트리 - 1992 문제 링크 성능 요약 메모리: 12756 KB, 시간: 84 ms 분류 분할 정복, 재귀 제출 일자 2023년 11월 28일 09:35:10 문제 설명 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇..

[백준] 1780번 : 종이의 개수 Silver2(실버2) - JAVA[자바]

[Silver II] 종이의 개수 - 1780 문제 링크 성능 요약 메모리: 314592 KB, 시간: 740 ms 분류 분할 정복, 재귀 제출 일자 2023년 11월 27일 10:10:31 문제 설명 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하..

[백준] 1074번 : Z Silver1(실버1) - JAVA[자바]

[Silver I] Z - 1074 문제 링크 성능 요약 메모리: 13936 KB, 시간: 104 ms 분류 분할 정복, 재귀 제출 일자 2023년 11월 26일 13:37:36 문제 설명 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c..

[백준] 9613번 : GCD합 Silver4(실버4) - JAVA[자바]

[Silver IV] GCD 합 - 9613 문제 링크 성능 요약 메모리: 11552 KB, 시간: 76 ms 분류 유클리드 호제법, 수학, 정수론 제출 일자 2023년 11월 26일 10:53:59 문제 설명 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다. 출력 각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다. 1. 2중 for문으로 일어날 수 있는 상황을 다 처..

[백준] 1850번 : 최대공약수 Silver1(실버1) - JAVA[자바]

[Silver I] 최대공약수 - 1850 문제 링크 성능 요약 메모리: 20048 KB, 시간: 240 ms 분류 유클리드 호제법, 수학, 정수론 제출 일자 2023년 11월 26일 10:38:16 문제 설명 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 입력 첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다. 출력 첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다. 1. 자리수끼리의 최대..

[백준] 1699번 : 제곱수의 합 Silver2(실버2) - JAVA[자바]

[Silver II] 제곱수의 합 - 1699 문제 링크 성능 요약 메모리: 12308 KB, 시간: 124 ms 분류 다이나믹 프로그래밍, 수학 제출 일자 2023년 11월 25일 10:33:09 문제 설명 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의..

[백준] 11004번 : K번째 수 Silver5(실버 5) - JAVA[자바]

[Silver V] K번째 수 - 11004 문제 링크 성능 요약 메모리: 663552 KB, 시간: 4136 ms 분류 정렬 제출 일자 2023년 11월 24일 10:09:12 문제 설명 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 출력 A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..