알고리즘 - Baekjoon

[백준] 1747번 : 소수&팰린드롬 Silver1(실버1) - JAVA[자바]

[Silver I] 소수&팰린드롬 - 1747 문제 링크 성능 요약 메모리: 19612 KB, 시간: 176 ms 분류 브루트포스 알고리즘, 수학, 정수론, 소수 판정, 에라토스테네스의 체 제출 일자 2023년 11월 1일 11:23:13 문제 설명 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 출력 첫째 줄에 조건을 만족하는 수를 출력한다. import java.util.Scanner; class Main{ pu..

[백준] 2294번 : 동전2 Gold5(골드5) - JAVA[자바]

[Gold V] 동전 2 - 2294 문제 링크 성능 요약 메모리: 13200 KB, 시간: 136 ms 분류 다이나믹 프로그래밍 제출 일자 2023년 11월 1일 11:14:21 문제 설명 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 ..

[백준] 1202번 : 보석 도둑 Gold2(골드2) - JAVA[자바]

[Gold II] 보석 도둑 - 1202 문제 링크 성능 요약 메모리: 326064 KB, 시간: 2880 ms 분류 자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬 제출 일자 2023년 10월 30일 14:33:36 문제 설명 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다..

[백준] 9328번 : 열쇠 Gold1(골드1) - JAVA[자바]

[Gold I] 열쇠 - 9328 문제 링크 성능 요약 메모리: 28264 KB, 시간: 408 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현 제출 일자 2023년 10월 30일 11:26:38 문제 설명 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. ..

[백준] 12026번 : BOJ 거리 Silver1(실버1) - JAVA[자바]

[Silver I] BOJ 거리 - 12026 문제 링크 성능 요약 메모리: 16036 KB, 시간: 172 ms 분류 다이나믹 프로그래밍 제출 일자 2023년 10월 26일 13:30:32 문제 설명 BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다. 스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다. BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다. 스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할..

[백준] 16922번 : 로마 숫자 만들기 Silver2(실버2) - JAVA[자바]

[Silver III] 로마 숫자 만들기 - 16922 문제 링크 성능 요약 메모리: 17016 KB, 시간: 156 ms 분류 백트래킹, 브루트포스 알고리즘, 조합론, 구현, 수학 제출 일자 2023년 10월 26일 11:37:00 문제 설명 로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다. 하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다. 실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 ..

[백준] 13706번 : 제곱근 Silver4(실버 4) - JAVA[자바]

[Silver IV] 제곱근 - 13706 문제 링크 성능 요약 메모리: 14636 KB, 시간: 144 ms 분류 임의 정밀도 / 큰 수 연산, 이분 탐색, 수학 제출 일자 2023년 10월 26일 10:47:15 문제 설명 정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. 출력 첫째 줄에 정수 N의 제곱근을 출력한다. import java.io.*; import java.math.BigInteger; class Main { public static void main(String args[]) throws Exception { BufferedReader br = ne..

[백준] 7576번 : 토마토 Gold5(골드 5) - JAVA[자바]

[Gold V] 토마토 - 7576 문제 링크 성능 요약 메모리: 120592 KB, 시간: 644 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우..