본문 바로가기

💻Study/Java

(6)

[알고리즘] 윤년 구하기 윤년의 조건은 다음과 같습니다. 1. 100의 배수가 아니면서 4의 배수이다. 2. 4의 배수가 아니면서 100의 배수이다. 3. 400의 배수이다. 셋 중 하나의 조건을 만족하면 윤년입니다. 예를 들어 2020년의 경우, 1번의 조건을 만족하므로 윤년입니다. 2000년은 3번의 조건을 만족하므로 윤년입니다. 저는 이게 한번에 알아듣기가 어려워서 벤다이어그램으로 그려보았습니다. 색칠된 ① 영역 또는 ② 영역에 해당하는 해가 윤년입니다. 이를 코드로 어떻게 나타내면 될까요? ① : year%400 == 0 ② : (year%4==0) && (year%100!=0) ② 영역은 이 수식을 생각하면 됩니다. 4의 배수-100의 배수는, 4의 배수에서 100의 배수가 아닌 것을 제외하면 된다는 뜻입니다. 그러면 ..

[알고리즘] 소수 구하기(3) - 에라토스테네스의 접근 앞서 소수 구하는 알고리즘을 두 가지 알아보았습니다. 이들을 개선한 세 번째 방법에 대해 알아보겠습니다. 사실 좀 어렵습니다. 정신을 바짝 차리고... 시작합니다. 두 번째 방법을 다시 한번 살펴보겠습니다. 2 이상 n-1 이하의 모든 소수로 나누었을 때 나누어 떨어지지 않는다. 이 방법을 어떻게 개선할 수 있을까요? 나눗셈의 횟수를 줄이면 됩니다. 이미 한 차례 나눗셈의 횟수를 줄였는데, 어떻게 하면 다시 줄일 수 있을지 생각해 보겠습니다. 이쯤에서 다시 한 번 상기해야 할 것은, 소수 구하기의 본질은 '약수 구하기'라는 것입니다. 프로그램 상에서는 n%i==0이 성립할 때 i는 n의 약수라고 판단합니다. 약수 구하기를 하면서 이러한 방법을 사용해 본 적이 있을 것입니다. 100을 예시로 들어보겠습니다..

[알고리즘] 소수 구하기(2) - 에라토스테네스의 체 아래는 소수 구하기(1)에서 했던 이야기의 요약입니다. (참고 : https://unounou.tistory.com/5) 2 이상 n-1 이하의 모든 정수로 나누었을 때 나누어 떨어지지 않는다. (1) ↓ 2 이상 n-1 이하의 모든 소수로 나누었을 때 나누어 떨어지지 않는다. (2) 7이 2로 나누어 떨어지지 않는다면, 2의 배수인 4와 6으로도 나누어 떨어지지 않습니다. 7%2 7%3 7%4 → 불필요한 연산 7%5 7%6 → 불필요한 연산 방법(1)에서는 위의 나눗셈을 전부 했지만 이 중에는 불필요한 연산이 존재합니다. 7%4와 7%6입니다. 즉, 방법(1)에서 불필요한 연산을 제거한 것이 방법(2)입니다. 딱 봐도 그렇지만 방법(2)가 더 어렵습니다. 하지만 어려울 수록 차분히, 차근차근! 이 방..

[알고리즘] 소수 구하기(1) 자연수(=양의 정수)는 세 가지로 나누어 집니다. 1, 소수, 그리고 합성수입니다. 소수란, 1과 자기 자신을 제외한 어떤 정수로도 나누어 떨어지지 않는 정수를 뜻합니다. 1과 소수를 제외한 모든 자연수는 합성수에 속합니다. 예를 들어 7의 약수는 1과 7 뿐이므로 소수이고, 6의 약수는 1, 2, 3, 6이므로 합성수입니다. 어떤 자연수가 소수인지 아닌지 판별하기 위해서는 해당 숫자의 약수를 생각해 보면 된다는 뜻입니다. 약수의 개념은 초등학교 때 처음 배워 계속 써먹기 때문에 머리로는 금방 판단할 수 있지만 수가 조금만 커지면 힘들어집니다. 2, 3, 5, 7, 11, 13...까지는 금방이지만, 479가 소수인지 판단하려면 어떨까요? 이를 판단하기 위해서는 알고리즘을 생각해 봐야 합니다. 2 이상 ..

양의 정수의 길이 구하기 문제를 푸는 도중 정수의 길이를 구해야 하는 부분이 있었습니다. 방법은 다양하게 있을 것 같습니다. 효율적인 방법부터 아주 비효율적인 방법까지.. String의 길이를 구할 때는 간단하게 length() 메소드를 사용하면 되지만, 정수는 약간 다른 방식을 사용해야 합니다. 그 중에서 가장 간단한 방법 두 가지를 포스팅해봅니다. 1. Math.log() 메소드 이용 : (int)(Math.log10(num)+1) 결론부터 말하자면 (int)(Math.log10(num)+1)에서 num에 자릿수를 구하고자 하는 숫자를 넣으면 됩니다. 참고로 num에 음수 또는 0은 대입할 수 있으나 원하는 값이 나오지 않을 것입니다. 예를 들어, int(Math.log10(32)+1)을 하면 2가 리턴될 것입니다. 32는 ..

String.format과 System.out.printf 다음과 같은 코드를 해석하는 법을 알아보도록 하겠습니다. int n = 2; int a = 3; int b = 4; int c = 5; System.out.printf(String.format("%%2d, %%%dd, %%d", n), a, b, c); 복잡해 보일 수록 차근차근 접근해야 합니다. 일단 안쪽에 있는 String.format("%%2d, %%%dd, %%d", n)을 먼저 살펴보도록 하겠습니다. Java에서 제공하는 String 클래스의 format 메소드는 지정된 위치에 값을 대입한 것을 문자열 형식으로 반환하는 메소드입니다. 형식은 C나 Java의 printf와 동일하게 %d, %s, %f 등의 서식을 사용합니다. 예를 들어, String.format("%3d, %2d", 10, 20)..

이전 1 다음

티스토리툴바