PS/BOJ
BOJ 2745 진법 변환 [Java]
BOJ 2745 진법 변환 1. 문제 링크 https://www.acmicpc.net/problem/2745 2. 문제 해설 B진법의 수를 10진법으로 변환하는 방법을 알아보자. 예시로 2진법 수 11001(2진수)을 들겠다. 1x2^4 + 1x2^3 + 0x2^2 + 0x2^1 + 1x2^0 = 25 이다. N진법 수를 각 자리마다 10진법으로 변환하여 sum에 더해주어 10진수를 구했다. 이 때, N진법 수를 string으로 받았기에 아스키 코드를 이용한 문자열 파싱을 해주었다. 3. 코드 보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException ..
BOJ 11005 진법 변환 2 [Java]
BOJ 11005 진법 변환 2 - 문제 링크 https://www.acmicpc.net/problem/11005 - 문제 해설 10진수를 어떻게 진법 변환해주는지를 알아야한다. 간단하게 10진수 10을 2진수로 나타낸다고 해보자. - 10을 2로 나눈다. 몫이 5이고 나머지가 0이다. - 몫 5를 2로 나눈다. 몫이 2이고 나머지가 1이다. - 몫 2를 2로 나눈다. 몫이 1이고 나머지가 0이다. - 몫 1을 2로 나눈다. 몫이 0이고 나머지가 1이다. - 몫이 0이 되면 나눠주는 행위를 그만두고, 나머지를 최종 나머지부터 처음 순으로 써준다. ex) 10 = 1010(2진수) 위 예시에서는 2진수라서 2로 나눠주었지만, n진수라면 n으로 나누어주면 된다. 문제에서 숫자를 표현할 떄 0~9까지는 그대로..
BOJ 9613 GCD 합 [Java]
BOJ 9613 GCD 합 - 문제 링크 https://www.acmicpc.net/problem/9613 - 문제 해설 3중 for문을 이용하여 풀었다. 시간복잡도가 O(N^2xT)인데, 최대 연산 수가 100x100x100 = 1,000,000 이므로 제한 시간 1초 안에 충분히 가능하다. 최대공약수는 두 수를 입력 받으면 최대공약수를 반환하는 gcd 함수를 유클리드 호제법을 이용하여 만들어 해결했다. 그리고 테스트 케이스마다 주어지는 수들을 다 순회하면서 gcd 함수를 실행하고 그 값을 sum에 더해주어 문제를 해결했다. - 코드 보기 import java.io.*; import java.util.*; public class Main { public static long gcd(int x, int ..
BOJ 1850 최대공약수 [Java]
BOJ 1850 최대공약수 - 문제 링크 https://www.acmicpc.net/problem/1850 - 문제 해설 처음에는 굉장히 막막하였다. 문제 예제들의 최대공약수를 생각해보면서 접근 방법이 떠올랐다. 문제 예제들에 유클리드 호제법을 이용해보면 된다. 111과 1111의 경우 1111=111x10 + 1, 111=111x1 + 0 이다. 그러므로 최대공약수는 1이다. 111과 111111의 경우 111111=111x1001 + 0 이다. 그러므로 최대공약수는 111이다. 1로 이루어진 수들끼리의 최대공약수는 모두 1로 이루어져있다는 사실을 추론할 수 있다. 입력 받는 데이터 A, B는 두 자연수 M, N을 이루는 1의 갯수이고, 그러므로 두 자연수 A, B의 최대공약수를 구하면 그것이 M, N..
![BOJ 2609 최대공약수와 최소공배수 [Java]](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbgeZBz%2Fbtrax8Hcq2Z%2F0BUh8iJGckRMgkNubTo3G0%2Fimg.png)
BOJ 2609 최대공약수와 최소공배수 [Java]
BOJ 2609 최대공약수와 최소공배수 - 문제 링크 https://www.acmicpc.net/problem/2609 - 문제 해설 최대공약수와 최소공배수를 구하는 문제이다. 유클리드 호제법을 이용하면 풀 수 있다. 유클리드 호제법이 무엇인지 알아보자. 최대공약수를 구하는 알고리즘인데, 두 자연수 m, n (m > n)이 있다고 하자. 이 때, m을 n으로 나눈 나머지를 r이라고 하면, m과 m의 최대공약수가 n과 r의 최대공약수와 같다는 것이 유클리드 호제법이다. 이 성질을 이용하면 n을 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지 r''을 구하고, 다시 r'을 r''로 나눈 나머지를 구하는 과정을 계속 반복해서 나머지가 0이 되었..