알고리즘 - Baekjoon

[백준] 16928번 : 뱀과 사다리 게임 Gold5(골드 5) - JAVA[자바]

[Gold V] 뱀과 사다리 게임 - 16928 문제 링크 성능 요약 메모리: 12972 KB, 시간: 112 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 11월 17일 10:37:28 문제 설명 뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어..

[백준] 16948번 : 데스 나이트 Silver1(실버1) - JAVA[자바]

[Silver I] 데스 나이트 - 16948 문제 링크 성능 요약 메모리: 13680 KB, 시간: 128 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 11월 17일 09:25:11 문제 설명 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다. 데스 나이트는..

[백준] 1629번 : 곱셈 Silver1(실버1) - JAVA[자바]

[Silver I] 곱셈 - 1629 문제 링크 성능 요약 메모리: 12856 KB, 시간: 112 ms 분류 분할 정복을 이용한 거듭제곱, 수학 제출 일자 2023년 11월 16일 10:58:00 문제 설명 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

[백준] 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..

[백준] 11051번 : 이항 계수2 Silver2(실버2) - JAVA[자바]

[Silver II] 이항 계수 2 - 11051 문제 링크 성능 요약 메모리: 12904 KB, 시간: 108 ms 분류 조합론, 다이나믹 프로그래밍, 수학 제출 일자 2023년 11월 8일 10:19:14 문제 설명 자연수 N과 정수 K가 주어졌을 때 이항 계수 NK를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N) 출력 (NK)를 10,007로 나눈 나머지를 출력한다. import java.util.Scanner; class Main{ public static final int DIV = 10007; public static void main(String[] args) { Scanner sc = new ..