L.O.K

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net ◎ 문제풀이 입력으로 주어진 수로 만들 수 있는 30의 배수중 가장 큰 값을 구하는 문제이다. 30은 3x10이므로 30의 배수는 항상 뒤가 0으로 끝난다. 그러므로 30의 배수란, 뒤가 항상 0으로 끝나는 수 중 3의 배수가 되는 수를 의미한다. 그럼 3의 배수가 되는 수를 어떻게 구할까? 여기서 중학교 1학년 때 배운 개념이 사용될거라고는 생각도 못했다. 배수 판정법을 이용하면 된다. 어떤 수의..

@문제 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net @문제풀이 두 가지 풀이가 있다. 1) 유클리드 호제법 2) 파이썬 math 라이브러리 사용 유클리드 호제법 자연수 A를 B로 나눌때 나머지 r이라면 유클리드 호제법은 A와B의 최대공약수는 B와 r의 최대공약수와 동일함을 의미한다. 유클리드호제법 증명은 위 영상을 참고바란다. 그러면 B를 r로 나눌때 나머지 r2의 최대공약수도 A와B의 최대공약수와 동일하다. 그러면 r을 r2로 나눌때 나머지 r3의 최대공약수도 A와B의 최대공약수와 동일하다. . . . 그러면 rn-2를 rn-1로 나눌때 나머지 rn이 0이 되면 rn-1..

9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 1. 문제 추상화 짝수는 두 소수의 합으로 표현 가능하다. 이 때, 두 소수의 차이가 최소인 경우를 출력하시오. 2. 알고리즘 첫 번째 방법 조건 : 짝수 - 작은 소수 = 큰 소수 해당 조건을 만족하는 작은 소수를 구한다. 작은 소수 중 가장 큰 소수일 때, 두 소수의 차이가 작다. 두 번째 방법 C는 짝수 C/2 +C/2 = C C/2-1 + C/2+1 = C C/2-2 + C/2+2 = C . . 반복문을 통해, 하나는 -1 씩, 하나는..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1. 문제 추상화 M과 N 사이의 소수를 출력하시오. 2. 알고리즘 첫 번째 방법 ( % 연산 ) 1. M부터 N까지의 자연수를 반복문 변수 i에 저장한다. 2. 이중 for문을 만들어, % 연산을 통해 소수여부를 판단한다. 3. 소수여부는 플래그 변수를 만들어 true, false로 파악한다. 두 번째 방법 ( 아리스토테네스의 체 ) 1. N + 1 크기의 boolean 배열을 만든다. 2. 이중 for문 구조를 만들어, 2의 배수, 3의 배수.... 를 true로 저장한다. 3. true로..

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 1. 문제 추상화 입력받은 N개의 수 중, 소수가 몇 개인지 출력하시오. 2. 제약조건 N은 100이하이고 수는 1000이하의 수가 주어진다. 3. 알고리즘 첫 번째 방법 : 아리스토테스의 체 1. 0~1000까지의 boolean 배열을 만든다. 2. 0~1000까지 i를 1씩 증가시켜 각 i의 배수를 true로 저장한다. 3. 반복문이 끝난 후, false로 남아있는 인덱스가 소수이다. 두 번째 방법 : 제곱근 1. 주어진 수가 5라면 5보다 작은 정수를 5에 나누었을 때 나머지가 0이 아니면 소수이다. 2. 1을 제외하고 2,..