알고리즘77 [알고리즘] 수 묶기 (백준 1744번) 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디하게 풀 수 있는 문제이다. 수를 정렬했을 때 양수 기준으로 가장 큰 수부터 곱해나간다. 단, 1과 쌍이 지어지는 경우는 그냥 더하는게 더 수가 크기 때문에 항상 list[i] * list[i+1]와 list[i] + list[i+1] 중 어떤게 더 큰지 비교해가면서 더한다. 음수는 반대로 가장 작은 수부터 곱해야지 가장 큰 값이 나온다. EX) (-5 * -1 = 5) > (-4 * -1 = 4) Solution import java.io.Buffere.. 2020. 10. 22. [알고리즘] 단어 수학 (백준 1339번) 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 나올 수 있는 알파벳 종류가 10가지이므로 백트랙킹으로 모든 순열을 구해도 된다. 순열을 구할 때 허용되는 최대 시간복잡도가 10!인데 알파벳이 딱 10가지이기 때문이다. 하지만 수학 수식을 활용해서 그리디 하게 풀면 훨씬 쉽게 풀 수 있다. Solution 'ABC', 'BCD' 라는 문자가 있다고 가정해보겠다. 이 두가지 문자를 수학 수식으로 나타내면 'ABC' : 100A + 10B + 1C 'BCD' : 100B + 10C + 1D 로 표현된다. 그.. 2020. 10. 21. [알고리즘] 합분해 (백준 2225번) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제고 예전에 풀어본 적은 있으나 다 까먹었다... 근래에 DP 문제를 거의 안 풀어서 그런가 비교적 쉬운 난이도인데도 어떻게 풀어야할 지 한참 헤멘다... Solution dp[N+1][K+1] 배열을 만든다. dp[i][j]는 i 수를 j개의 수로 이용해서 만들 수 있는 경우의 수다. dp[i][0] = 0, dp[i][1] = 1이다. 즉 0개의 수를 이용해서 정수를 만들 수 있는 경우는 없고 1개의 수를 이용해서 정수를 만드는 경우는 자기자신 딱 하나 밖에 없다. i = k + (i-k)라고 쳤을 때, [k][j-1] * [i-k][1] = [k][j-1]이다... 2020. 10. 20. [알고리즘] 자바로 수학 log 구하기 log 성질 $\log _{3}{5} = \frac{\log {5} }{\log {3}}$ //둘 다 결과는 같다. System.out.println(Math.log10(5) / Math.log10(3)); System.out.println(Math.log(5) / Math.log(3)); 응용 $x^{6} = 64$ 의 $x$ 구하기 $6 = log _{x}{64}$ → $6 = \frac{log _{10}{64}}{log _{10}{x}}$ → $log _{10}{x} = \frac{log _{10}{64}}{6}$ 결론 : $x = 10 ^ {\frac{log _{10}{64}}{6}}$ System.out.println(Math.pow(10, Math.log10(64) / 6)); //결과 : 2.0 2020. 10. 17. 이전 1 2 3 4 5 ··· 20 다음
