본문 바로가기

전체 글376

[백준] 17175번 : 피보나치는 지겨웡~ – JAVA [자바] https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 문제 문제 풀이 백준 17175번 피보나치는 지겨웡~은 이전에 많이 풀어봤던 피보나치 문제이다. 이 문제 역시 DP를 이용해서 풀 수 있다. 이 문제에서는 피보나치 함수가 다음과 같이 주어졌다. int fibonacci(int n) { // 호출 if (n < 2) { return n; } return fibonacci(n-2) + fibonacci(n-1); } 그리고 이 피보나치 함수에 인자로.. 2022. 4. 8.
[알고리즘] 배낭 문제 (Knapsack Problem) 목차 배낭 문제란? 배낭 문제란 담을 수 있는 최대 무게가 정해진 배낭이 있고 각각의 무게와 가치가 주어진 물건들이 주어졌을 때, 배낭에 담은 물건들의 가치가 최대가 되도록 하게 물건을 고르는 방법을 찾는 문제이다. 배낭 문제 예시 4가지의 물건 ABCD가 있고 배낭의 최대 무게는 5라고 가정하겠다. 무게가 1, 가치가 30인 물건을 A; 무게가 2, 가치가 20인 물건을 B; 무게가 3, 가치가 40인 물건을 C; 그리고 무게가 4, 가치가 10인 물건을 D라고 하겠다. 그리고 우리가 가진 가방의 최대 무게는 5이다. 이때 이 가방에 넣을 수 있는 최대 가치가 몇인지를 구하는 것이다. 예를 들어서 B와 C를 넣어서 총가치가 60이 되도록 가방에 넣을 수 있고, 아니면 A와 D를 넣어서 총가치가 40이 .. 2022. 4. 7.
[백준] 1788번 : 피보나치 수의 확장 – JAVA [자바] https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 문제 풀이 백준 1788번 피보나치 수의 확장은 DP, 그중에서도 피보나치를 이용해서 푸는 문제이다. 이 문제의 조금 다른 점은 바로 피보나치의 확장, 즉 음수 n이 주어졌을 때도 이 음수 n의 피보나치 값을 구해야 한다는 것이다. 이 문제는 그렇게 어렵지 않다. 일반 피보나치와 거의 똑같은 문제이다. 피보나치는 다음과 같다 F(0) = 0 F(1) = 1; F.. 2022. 4. 7.
[백준] 11053번 : 가장 긴 증가하는 부분 수열 – JAVA [자바] https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 문제 풀이 백준 8394번 악수는 실버 4 난이도의 DP를 이용해서 푸는 문제이다. 이 직사각형 탁자가 하나 있고 사람들 n명은 한 면에 앉아 있는다. n명이 자리를 벗어나지 않고 악수를 하는 방법의 수를 구해주면 된다. 예시를 보면서 이 문제를 풀어보겠다. n = 1: 1명이 있으면 악수를 아무와도 못 하므로 방법은 1가지다. n = 2: 2명이 있으면 악수를 안 하는 거 하나, 악수를 하는 거 하나, 총 2가지다. 줄은 악수를 의미한다. n = 3 : 3명이 있으면 밑에 있는 사진처럼 3가지 방법.. 2022. 4. 6.
[백준] 2670번 : 연속부분최대곱 – JAVA [자바] https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 문제 ​ 문제 풀이 백준 2670번 연속부분최대곱 문제는 DP를 이용한 실버 4 난이도의 문제이다. 이 문제는 정답 비율이 35.866% (2022년 4월 5일 기준)으로 실버 4 난이도의 문제 치고는 낮은 편이다. 내가 생각했을 때는 아마도 소수점을 셋째 자리까지 반올림하고 출력하는 부분에서 사람들이 많이 틀리지 않나 싶다. 나도 처음에는 여기서 틀렸었다. 이번 문제는 1차원 dp .. 2022. 4. 6.
[백준] 10211번 : Maximum Subarray – JAVA [자바] https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 문제 문제 풀이 백준 10211번 Maximum Subarray는 주어진 배열에서 연속되는 부분 배열중에 가장 큰 합을 출력하는 문제다. 이 문제는 DP를 이용해서 푸는 문제인데 DP 이론이 조금 부족하면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/4 [알고리즘] 다이나믹 프로그래밍 (Dyn.. 2022. 4. 3.
[백준] 15624번 : 피보나치 수 7 – JAVA [자바] https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 문제 풀이 백준 15624번 피보나치 수 7은 피보나치와 나머지를 이용해서 푸는 문제이다. 즉 n이 커지면 피보나치 수가 너무 커지니까 나머지로 구해서 수를 int 범위를 벗어나지 않게 하는 것이다. fib(n) = (fib(n-1) + fib(n-2)) % 1000000007; 이 코드가 기본 코드가 되겠다. 코드 import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) th.. 2022. 4. 2.
[백준] 7861번 : Longest Ordered Subsequence – JAVA [자바] https://www.acmicpc.net/problem/7861 7861번: Longest Ordered Subsequence A numeric sequence of ai is ordered if a1 ≤ a2 ≤ … ≤ aN. Let the subsequence of the given numeric sequence (a1, a2, …, aN) be any sequence (ai1, ai2, …, aiK), where 1 ≤ i1 < i2 < … < iK ≤ N. For example, the sequence (1, 7, 3, 5, 9, 4, www.acmicpc.net 문제 문제 풀이 백준 7861번 Longest Ordered Subsequence는 백준 11053번 가장 긴 증가하는 부분 수열이랑.. 2022. 4. 1.
반응형

티스토리툴바