2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 주어진 N이 소수라면 2보다 크거나 같고 N보다 작은 수로 나눠 떨어지면 안된다. ( 주어진 N이 N>2를 만족하는 자연수 ) 예를들어 10을 소수인지 판단 하려면 2보다 크거나 같고 9보다 작은 수로 나눠보면된다 ( 10은 소수가 아니기 때문에 2와 5로 나눠떨어진다. ) 즉 자기보다 작은 수에 의해 나눠떨어지면 소수가 아니다. 이 원리를 이용하면 소수를 빠르게 구할 수 있다. 그 중 대표적인 알고리즘이 에라토스테네스의 체. 에라토스테네스의 체는 특정 범위내에 있는 모든 소수를 빠르게 찾기 위한 알고리즘 중 하나이다. 에라토스테네스의 체를 이용해 ..

1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼같은 경우는 결과로 워낙 큰수가 나오기 때문에 다음과 같은 형태로 문제가 많이 나온다. 팩토리얼 결과중 0의 갯수를 구하는 문제다. 0은 2x5일때 발생한다. 그렇기 때문에 팩토리얼을 소인수분해 해서 2x5의 갯수를 구하면 된다. 단, 2는 모든 짝수에 다 들어가지만 5는 모든 홀수에 다 들어가진 않는다. 따라서 2x5의 갯수는 5의 갯수와 같다. 구현하면서 25, 125와 같이 5가 2번, 3번 들어가는 숫자들을 잘 처리해줘야한다. import java.io.BufferedReader; import java.io.BufferedWriter..

1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 최대공약수를 구하는 문제인데 입력값이 조금 특이하다. 2라고 입력되었으면 11을 의미하고 3이라고 입력되었으면 111을 의미한다. 즉 2 3 이 입력되면 11과 111의 최대공약수를 구해야하는 문제다. 먼저 최대공약수(영어약자는 gcd)를 구하는 공식을 보자. 아래에 gcd(8,24)를 구하는 과정을 써봤다. 앞서 말했듯이 입력을 2와 3으로 했다면 11과 111의 최대공약수를 구해야한다. 하지만 문제에서 주어진 입력가능한 자연수의 크기는 ..

17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 17298번 오큰수를 약간 응용한 버전. 오큰수 문제를 풀었다면 쉽게 풀수 있다. 횟수 개념만 추가된것 외에는 차이가 없다. 변수명과 해당 변수에 담긴 값. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arra..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 시간초과로 상당히 고생한 문제. 처음 내가 풀었던 방식은 아래와 같다. 3이 있으면 우측으로 쭉 읽으면서 3보다 큰수가 나오면 break를 걸도록했다. 이렇게 하면 2중 for loop를 사용하게 되는데 worst case의 경우 n!이 나온다. 따라서 이렇게 풀면 당연히 시간초과. 결국 풀다가 백준님 강의를 듣고 아래의 소스코드로 정답을 맞췄다. 해당 문제를 시간내 통과하기 위해서 Stack을 사용했다. 3 5 2 7이라는 숫자가 있다면 먼저 0(숫자3의 인덱스)을 Stack..

Spring In Action 5판을 따라하면서 공부중이다. JDBC를 사용해서 데이터를 읽고 쓰는 챕터가 있다. 해당 챕터에서 h2-console에 접속해서 INSERT한 데이터를 확인하는 부분이 있는데 교재대로 했을때 테이블이 제대로 조회되지 않았다. testdb로 접속은 되나 실제로 내가 사용한 테이블은 보이지 않았다. 분명 h2 버전도 교재랑 맞춰서 진행했는데 Spring 버전에 따라 default 설정이 바뀌는지 testdb에는 실습에서 사용한 테이블이 없었다. Application을 실행하면 로그에 아래와 같이 JDBC url이 출력된다. h2-console에서 testdb 대신 아래 형광펜으로 표시한 값을 JDBC url에 입력해야한다. 끝.