728x90 알고리즘115 [JAVA]백준 1748번: 수 이어 쓰기 1 www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 1. 문제 설명 1부터 N까지의 수를 이어서 쓸 때 만들어진 수가 몇 자릿수인지 구하는 문제이다. 같은 자릿수 X를 가진 수들을 다 이어서 수를 만들면 그 수의 자릿수를 9*10^(X-1)*X이다. 수의 개수는 9*10^(X-1)이고 그 수들이 차지하는 길이는 X이므로 위와 같은 식이 나온다. N의 자릿수를 A라고 하면, 1부터 A-1의 자릿수를 가진 수들로 만들어진 길이는 위의 식을 이용해서 구한다. 그 후 A의 자릿수를 가지는 수의 개수는 N-10^(A-1)+1개이고 차지하는 길이는 각각 A이다. 그러므로 마지막에 (N-10^(A-1).. 2020. 11. 15. [JAVA]백준 1735번: 분수 합 www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 1. 문제 설명 두 분수가 주어질 때 두 분수의 합을 기약 분수로 출력하는 문제이다. 두 개의 분모들끼리의 최소공배수를 구하고 이를 두 분수의 합의 분모로 한다. 그리고 두 분수들의 분자들을 분모들이 두 분수의 합의 분모가 되기 위해 곱해지는 수만큼 분자들을 곱하고 합을 구한다. 그 후 두 분수의 합의 분수의 분모와 분자의 최대공약수를 구해 그 수를 나누어 기약 분수를 만든다. 2. 코드 import java.lang.reflect.Array; import jav.. 2020. 11. 14. [JAVA]백준 9996번: 한국이 그리울 땐 서버에 접속하자 www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 1. 문제 설명 주어진 패턴과 일치하는 문자열인지 아닌지 확인하면 된다. *을 기준으로 앞 문자열과 뒷 문자열로 나눈다. 그 후 첫 번째, 새로 입력받은 문자열이 기준 문자열에서 *을 뺀 길이보다 짧은지 확인한다. 만약 짧다면, 이는 패턴이 일치하지 않는 것이기에 NE를 출력하면 된다. 두 번째는, 앞에서 자른 기준 문자열의 앞 문자열, 뒷 문자열과 새로 입력받은 문자열이 일치.. 2020. 11. 5. [JAVA]백준 1058번: 친구 www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 1. 문제 설명 가장 2-친구의 수가 많은 사람의 2-친구수를 구한다. 2-친구란 두 사람이 친구이거나, A와 친구이고 B와 친구인 친구 C가 존재할 경우 A와 B는 2-친구라고 한다. 첫 번째 코드는 플로이드 와샬 알고리즘을 사용했다. O(n^3)의 시간 복잡도를 가지며 모든 꼭짓점 사이의 최단 경로를 구하는 알고리즘이다. 두 번째 코드는 플로이드 와샬 알고리즘에 대한 지식 없이 처음 문제를 풀었을 때 짠 코드이.. 2020. 11. 4. 이전 1 ··· 21 22 23 24 25 26 27 ··· 29 다음 728x90