[Java] 백준 12865 (평범한 배낭) 자바 문제 풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/12865   알고리즘 분류다이나믹 프로그래밍배낭 문제 풀이대표적인 DP 알고리즘을 사용하는 배낭 문제이다.Bottom-UP 방식을 사용했고 DP의 SubProblem은 물건을 담을 때나 담지 않을 때를 생각했다. 예시는 백준에 나와있는 입출력을 기준으로 아래의 표와 함께 설명하겠다.  초기 상태 (행 0): DP 테이블의 첫 번째 행은 물건을 하나도 고려하지 않은 상태이다. 따라서 모든 값이 0으로 초기화되어 있다. 당연히 배낭의 무게가 얼마이든지 물건을 하나도 넣지 않으면 가치는 0이기 때문이다.물건 \ 무게01234567X00000000 물건 1 (무게 6, 가치 13) - 행 1:배낭의 무게가 1부터 5까지는 물건 1의 무게(6)를 담을 수..
[Java] 백준 1262 (알파벳 다이아몬드) 자바 문제 풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/1262  알고리즘 분류구현 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine());..
[Java] 백준 1015 (수열 정렬) 자바 문제 풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/1015  알고리즘 분류정렬 똑같은 두개의 배열을 두고 하나는 비내림차순(오름차순) 으로 정렬할 때순서에 맞게 index 번호를 출력하는 문제이다.  우선, StringTokenizer를 사용하여 입력된 수들을 배열에 하나씩 저장하였다. StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i     그 다음, 배열을 복사한 뒤 원본 배열은 Arrays.sort() 함수를 사용하여 오름차순으로 정렬해주었다 int [] arr = temp.clone(); Arrays.sort(temp);   이제 두 개의 배열을 비교하며 원래 배열의 각 요소가 정렬된 배열에서 어떤 ..
[Java] 백준 14501 (퇴사) 자바 문제풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net 알고리즘 분류다이나믹 프로그래밍 풀이    public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int [] day = new int[n]; int [] money = new int[n]; ..
[Java] 백준 2535 (아시아 정보올림피아드) 자바 문제 풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/2535 2535번: 아시아 정보올림피아드 첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사 www.acmicpc.net 알고리즘 분류 구현 정렬 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void ma..
[Java] 백준 1527 (금민수의 개수) 자바 문제 풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 분류 브루트포스 알고리즘 풀이 처음엔 완전탐색으로 하나씩 String으로 변환 후 체크했다. 하지만 메모리 초과가 발생하였고, 재귀 호출을 사용해 문제에 접근했다. 핵심 로직이다. 매개변수로 받은 n을 어차피 한자리씩 늘어나니 10을 곱하고 7, 4를 더했다. ( 7 -> 77 or 74 ) 왜냐하면 7와 4만 필요할 뿐 나머지는 필요가 없기 때문이다. 재귀호출을 빠져나오는 조건문은 b..
[Java] 백준 2075 (N번째 큰 수) 자바 문제 풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 분류 자료 구조 정렬 우선순위 큐 풀이 정렬을 해서 풀어야 하는 문제이다. 하지만 메모리 제한이 12MB이므로 2차원 배열을 다 입력받고 정렬을 했다간 메모리 초과가 날 것 같아, 우선 순위 큐로 문제를 접근했다. PriorityQueue를 선언하고 람다식을 사용해 ( (o1, o2) -> o2 - o1 ) 높은 수 부터 정렬했다. PriorityQueue queue = new PriorityQ..
[Java] 백준 1312 번 (소수) 문제 풀이
·
BOJ, Programmers
https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 알고리즘 분류 수학 풀이 간단한 연산 문제인줄 알아서 자꾸 뜨는 런타임오류로 인해 한참 해멨다. BigDecimal를 사용해도 10의 10,000,000제곱까지는 표현하기 어렵기 때문이다. 그래서 나눗셈을 구현해 문제를 풀었다. 나눗셈은 a와 b를 나눈 나머지에 10을 곱하는 반복적인 연산이라고 한다. 그리고 우리가 알아야 할 것은 1의자리 즉, 몫을 알아야 하므로 result라는 변수에 계속..
[Java] 백준 1448 번 (삼각형 만들기)
·
BOJ, Programmers
https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 알고리즘 분류 수학 그리디 정렬 풀이 그리디 알고리즘과 정렬을 이용해 문제를 풀었다. 먼저 삼각형의 성립 조건을 알아야 한다. 삼각형의 성립 조건: a, b, c(가장 긴 변)이 있을 때 a + b > c 이어야 삼각형이 성립이 된다. 그래서 입력받은 배열을 정렬 후 뒤에서부터 차례로 삼각형이 성립이 되는지 if 조건문을 사용해 구했다. Arrays.sort(arr); fo..