java

[BOJ/JAVA] 16401번: 과자 나눠주기

16401번: 과자 나눠주기https://www.acmicpc.net/problem/16401키워드반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.구현나누는것 여러개로 나눌 수 있지만, 하나로 합칠 수 없음에 주의하자. 매개변수 탐색을 이용하여 구현한다. 템플릿low, high 값은 항상 범위 내로 설정한다.low = 0high = 길이가 가장 긴 과자 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2..

[BOJ/JAVA] 1351번: 무한 수열

1351번: 무한 수열https://www.acmicpc.net/problem/1351키워드무한 수열 A는 다음과 같다.A_0 = 1A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.0 ≤ N ≤ 10^122 ≤ P, Q ≤ 10^9구현중요한 것은 N, P, Q의 범위가 매우 크다는 것이다.배열로 만들기에는 너무 크기 때문에, Map을 이용하여 필요한 데이터만 저장하도록 하자.int 대신 long 자료형을 이용하자statch HashMap cacheA_i에서 i일 때 A_i의 값을 저장한다.statc long dp(long index)index가 0인 경우1을 반환한다.캐시값이 존재하는 경우캐시값을 반환한다.A[index] = A_[i..

[BOJ/JAVA] 2302번: 극장 좌석

2302번: 극장 좌석문제 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.https://www.acmicpc.net/problem/2302키워드공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.“VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.주어진 조건을 만족하면서 사람들..

[BOJ/JAVA] 11052번: 카드 구매하기

11052번: 카드 구매하기요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.https://www.acmicpc.net/problem/11052키워드카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재민규는 돈을 최대한 많이 지불해서 카드 N..

[BOJ/JAVA] 5557번: 1학년

5557번: 1학년상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.https://www.acmicpc.net/problem/5557키워드마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다.상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다.상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램구현초기값은 항상 맨 앞에 있는 숫자이다.결과..

플로이드 최단 경로 알고리즘

플로이드 최단 경로 알고리즘💡모든 정점 쌍에 대해 최단 거리를 구할 때 쓰는 알고리즘개요board[u][v]정점 u에서 정점 v까지의 최단거리를 저장최단 거리를 찾는 방법정점 u에서 정점 v까지 바로 가는 거리를 w(u, v)라고 하자이 때, u→a→v를 가는 거리가 u→v 거리보다 짧다면 갱신하는 방식이다.코드public class 플로이드 { static int board[][]; static void floyd() { // 자기 자신의 거리는 0 for (int i = 0; i < board.length; i++) { board[i][i] = 0; } // 거리 계산하기 for (int k = 0; k < board.length; k++) { for (int i = 0; i < board.lengt..

벨판-포드의 최단 경로 알고리즘

벨판-포드💡다익스트라의 음수 간선 문제를 해결한 최단 경로 알고리즘다익스트라와의 차이벨판-포드는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄이는 방식동작 과정upper[]시작지점으로부터 각 정점까지 최단 거리의 상한시작점→시작점의 거리는 0나머지는 매우 큰 수로 저장시작점이 아닌 임의의 두 지점 u, vdist[u]시작지점 → u 까지의 최단 거리dist[v]시작지점 → v 까지의 최단 거리이때, 다음이 성립한다.dist[v] ≤ dist[u] + w(u, v)dist[u] ≤ upper[u]upper[u] + w(u, v) ≤ upper[v]종료 조건과 정당성의 증명어떻게 upper[] 의 값을 dist[] 값으로 만들 수 있..

[BOJ/JAVA] 1612번: 가지고 노는 1

1612번: 가지고 노는 1동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 이 원숭이는 수를 이리저리 가지고 노는 것을 매우 좋아한다. 그중에서도 1을 가지고 노는 것을 매우매우매우매우매우 좋아한다. 이제 원숭이가 1을 가지고 노는 법을 알아보자. 원숭이는 1만으로 이루어진 수를 매우매우매우매우매우매우매우 좋아한다. 그래서 어떤 자연수 N이 있을 때, N의 배수 중에서 1만으로 이루어진 수가 있을 까 생각하게 되었다.https://www.acmicpc.net/problem/1612키워드N의 배수 중에서 1만으로 이루어진 수중에 가장 작은 수의 자릿수구현countNumberLength입력받은 값의 자릿수를 계산하는 메소드입력받은 정수를 String으로 바꾼다.해당 문자열의 길이를 반환한다.s..

[BOJ/JAVA] 1644번: 소수의 연속합

1644번: 소수의 연속합하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.https://www.acmicpc.net/problem/1644키워드하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수구현N이하의 소수 구하기에라토스테네스의 체를 이용하여 소수를 구한다.primeList 소수를 저장한다.N이하 소수의 누적합 구하기..

[BOJ/JAVA] 10830번: 행렬 제곱

10830번: 행렬 제곱크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.https://www.acmicpc.net/problem/10830키워드크기가 N*N인 행렬 A가 주어진다.A의 B제곱을 구하는 프로그램구현matrixMultiply두 정방행렬의 곱을 구하는 메소드시간복잡도 O(N^3)정방행렬의 곱은 다음과 같다.[a1a2a3a4]∗[b1b2b3b4]=[a1b1+a2b3a1b2+a2b4a3b1+a4b3a3b2+a4b4]\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} * \begin{bmatrix} b_1 & b_2 \\ b_3 &..