알고리즘 - Baekjoon/Gold

[백준] 12865번 : 평범한 배낭 Gold V(골드5) - JAVA[자바]

[Gold V] 평범한 배낭 - 12865 문제 링크 성능 요약 메모리: 52892 KB, 시간: 204 ms 분류 다이나믹 프로그래밍, 배낭 문제 제출 일자 2023년 11월 16일 10:29:11 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 ..

[백준] 13460번 : 구슬 탈출 2 Gold1(골드1) - JAVA[자바]

[Gold I] 구슬 탈출 2 - 13460 문제 링크 성능 요약 메모리: 17976 KB, 시간: 152 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션 제출 일자 2023년 11월 15일 15:07:16 문제 설명 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 ..

[백준] 1941번 : 소문난 칠공주 Gold3(골드3) - JAVA[자바]

[Gold III] 소문난 칠공주 - 1941 문제 링크 성능 요약 메모리: 58416 KB, 시간: 204 ms 분류 백트래킹, 너비 우선 탐색, 브루트포스 알고리즘, 조합론, 그래프 이론, 그래프 탐색, 수학 제출 일자 2023년 11월 9일 11:50:24 문제 설명 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주..

[백준] 11401번 : 이항 계수 3 Gold1(골드1) - JAVA[자바]

[Gold I] 이항 계수 3 - 11401 문제 링크 성능 요약 메모리: 12920 KB, 시간: 152 ms 분류 조합론, 분할 정복을 이용한 거듭제곱, 페르마의 소정리, 수학, 모듈로 곱셈 역원, 정수론 제출 일자 2023년 11월 8일 10:59:52 문제 설명 자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N) 출력 (N K)를 1,000,000,007로 나눈 나머지를 출력한다. import java.util.Scanner; class Main{ public static final long DIV = 1000000007; pub..

[백준] 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개를 넘지 않는다. ..

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

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