밤이 블로그

BOJ#2824 최대공약수 * 문제https://www.acmicpc.net/problem/2824 * 해설두가지 방법으로 풀어보았습니다. 1. BigInteger를 이용 2. A와 B를 다음과 같이 표현할 수 있습니다. 예를 들어 A = 30, B = 20일 때A = 2^(1) * 3^(1) * 5^(1)B = 2^(2) * 5^(1) 최대공약수는 위에서 볼 수 있듯이 gcd = 2^(min) * 5^(min) = 2^(1) * 5^(1) * 나의 코드 BigInteger를 이용한 풀이BigInteger a = BigInteger.valueOf(1); BigInteger b = BigInteger.valueOf(1); BufferedReader br = new BufferedReader(new Inpu..

BOJ#1339 단어 수학 * 문제https://www.acmicpc.net/problem/1339 * 풀이 이 문제는 두가지 풀이법으로 풀어보겠습니다. 예)MCR ACDEB 1) 수학으로 풀기 위의 두 숫자를 풀어보면MCR = M * 100 + C * 10 + R * 1ACDEB = A * 10000 + C * 1000 + D * 100 + E * 10 + B * 1 두 숫자를 더해보면MCR + ACDEB = 10000A + 1001C + 100M + 100D + 10E + R + B 가 됩니다. 하나의 문자는 하나의 숫자(0~9)로 대응되고합의 최대값을 구하고 싶으므로 즉, 10000A + 1001C + 100M + 100D + 10E + R + B의 최대값을 구하면 되는 것입니다. A -> C ->..

BOJ#2089 -2진수 * 문제 https://www.acmicpc.net/problem/2089 * 풀이 기존에 10진수를 2진수로 변환하는 알고리즘과 같이주어진 수를 (-2)로 나누어 가면서, 나머지들을 저장하는 방법을 쓴다. 단, 주의할 점으로는 나머지를 올림 해야 한다는 것이다. * 참고http://kin.naver.com/qna/detail.nhn?d1id=11&dirId=1113&docId=57428826&qb=7Iut7KeE7IiYIOydtOynhOyImCDrs4DtmZgg7JuQ66as&enc=utf8§ion=kin&rank=9&search_sort=0&spq=0 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232089_MinusB..

BOJ#1373 2진수 8진수 * 문제https://www.acmicpc.net/problem/1373 * 풀이2진수, 8진수, 16진수 간 변환은 2진수를 중심으로 하면 편합니다.즉, 8진수와 16진수 간의 변환도 일단 2진수로 변환을 한 후 다시 변환을 해주시는 것이 좋습니다. 2진수 11001100이 있을 때,2자리씩 묶으면 4진수11 00 11 00 → 30303자리씩 묶으면 8진수011 001 100 → 3144자리씩 묶으면 16진수1100 1100 → CC 1. String으로 입력 받은 2진수 입력값의 길이를 조사한다.2. 길이가 3으로 나누어 떨어지지 않는 경우, "0" 또는 "00"을 추가시켜준다.3. 3자리씩 끊어 가면서 int 변환한 후 8진수 값으로 변환한다. * 나의 코드https..

BOJ#4134 다음 소수 * 문제https://www.acmicpc.net/problem/4134 * 풀이 이 문제는 2가지 버전으로 풀어 보았다. Solution#1 (메모리 : 73836 KB, 시간 : 1308 MS)입력값이 0

BOJ#1929 소수 구하기 * 문제https://www.acmicpc.net/problem/1929 * 풀이 - 단순히 접근하면, 체크하려는 모든 수 x에 대해 2부터 x까지 %연산을 해보는 방법이 있겠다. 그러나 주어진 숫자가 커질 수록 많은 시간이 걸리기 때문에 시간을 줄일 수 있는 방법을 생각해야 한다. (정의) 소수 : 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. 에라스토테네스의 체 1. 2, 2를 제외한 모든 2의 배수를 제외한다.2. 3, 3을 제외한 모든 3의 배수를 제외한다.3. 4, 4를 제외한 모든 4의 배수를 제외한다....반복... 출처 및 공부 자료 : https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ※ 주의할 점 - ..

BOJ#2609 최대공약수 최소공배수 * 문제https://www.acmicpc.net/problem/2609 * 풀이 두 자연수 a, b가 주어졌을 때 (a>b), 두 자연수의 최대공약수를 구하는 알고리즘 : 유클리드 호제법두 자연수의 최소공배수를 구하는 알고리즘 : a*b/최대공약수 유클리드 호제법유클리드 호제법(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.호제법이란, 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다. m >= n일 때,① m을 n으로 나눈다. 나머지를 r이라고 한다.② 나머지 r이 0이면 n이 최대공약수이다. 나머지가 0이 아니라면 m의 값을 n으로 설정하고, n의 값은 r로 설정한 다음 ①로 되돌아가서 ..

* 문제 https://www.acmicpc.net/problem/1007 * 풀이 평면 상에 N개의 점이 찍혀있다. (N은 짝수) N개의 점을 이용해서 벡터를 만든다. 벡터는 당연히 N/2개 나올 것이다. 문제를 자세히 보니, N개 점들의 좌표가 주어지고 평면벡터이다. 평면 상에 2개의 점 A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4)가 주어졌고 임의의 벡터를 구성했다고 가정해보자. 2개의 임의의 벡터이다. AB = (x1-x2, y1-y2) CD = (x3-x4, y3-y4) 위 2개의 벡터의 합은 아래와 같다. AD+CD = (x1+x3-(x2+x4), y1+y3-(y2+y4)) 위 벡터의 크기는 Math.sqrt((x1+x3-(x2+x4))^2, (y1+y3-(y2+..

* 문제https://www.acmicpc.net/problem/1004 * 풀이 (생각의 흐름)주어진 예제 그림에서 힌트를 얻었다.→ 출발점을 감싸고 있는 원의 수 + 도착점을 감싸고 있는 원의 수 : 주어진 예제에서는 OK→ 그러나 한 원이 출발점과 도착점을 모두 포함하는 경우 : NG→ 따라서 위 경우의 수를 제외해야 함 ※ 출발점을 감싸고 있는 원의 수 + 도착점을 감싸고 있는 원의 수 - 두 점을 모두 포함하는 원의 수 = 출발점이나 도착점 1개만 포함하고 있는 원의 수 * 코드 for (int j = 0; j < n; j++) { st = new StringTokenizer(br.readLine()); Circle c = new Circle(Integer.parseInt(st.nextToken..

* 문제https://www.acmicpc.net/problem/1002 * 풀이 : 두 원의 위치 관계를 수학식으로 표현할 수 있어야 한다. d < r - r' ≤ d ≤ r + r' < d 1) 두 좌표가 같은 경우 반지름까지 같은 경우 : -1 (무한대) 반지름이 다른 경우 : 0개 2) 두 좌표가 다른 경우 d < r - r' or r + r' < d : 0개 r - r' = d or d = r + r' : 1개 r - r'