Algorithm

[BOJ/JAVA] 15810번: 풍선 공장

15810번: 풍선 공장https://www.acmicpc.net/problem/15810키워드풍선을 담당하는 N명의 스태프대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰각 스태프가 풍선 하나를 만드는 시간(분) A_i를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?구현매개변수 탐색을 이용하여 구현한다.범위가 int 범위를 초과하므로 long 자료형을 이용한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 가장 빨리 만들 수 있는 직원이 걸리는 시간 * M 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;mid 시간내로 만들 수 있는지 체크한다. mid 시간 내로 만들 수 있다면high = ..

[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[] 값으로 만들 수 있..

이진 검색 트리

1. 이진 검색 트리란?💡자료들을 일정한 순서에 따라 정렬한 상태로 저장해두는 트리사용 예시캐릭터 생성 시 특정 닉네임이 이미 저장되어있는지 확인하기나보다 1등 위인 사람과 1등 아래인 사람을 찾기 대부분 언어 표준 라이브러리에서 제공하기 때문에, 직접 구현하지 않는다.2. 이진 검색 트리의 정의와 조작2-1. 이진트리란?💡한 노드당 최대 2개의 자식 노드만 가질 수 있는 트리따라서 관련 객체 작성 시 다음처럼 구현이 된다.class Node { int data; Node left, right; }2-2. 이진 검색 트리의 특징N개의 원소 중에서 원하는 원소를 찾기까지 걸리는 시간은 다음과 같다.O(log⁡N)O(\log{N})O(logN)시간이 logN이 걸리기 위해선 노드들이 특별한 방식으로 저장될 ..

[BOJ/JAVA] 1822번: 차집합

키워드집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램구현집합 연산 중 차집합 연산을 이용하여 구현한다.A.removeAll(B)A집합에는 속하지만, B집합에는 속하지 않게 A를 바꾼다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Set; import java.util.StringTokenizer; import java.util.TreeSet; public class java_1822 { static Set aSet, bSet; public static void main(String[] args) throws IOExcepti..