메모/코딩 문제풀기&다시보기
바뀌기 전 정처기 알고리즘 기출문제를 Java로 풀기 (1)
JinHee Han
2020. 9. 30. 20:37
*정보처리기사 시험이 바뀌기 전에 기출문제로 나왔던 알고리즘 문제를 푸는 글 입니다.
따라서 현재 바뀐 정보처리기사 시험에는 나오는지 안나오는지 알수 없습니다.
[문제]
어떤 정수의 약수중 자신을 제외한 약수를 모두 합하면 자신과 같아지는 수가 있다. 예를 들어 6의 약수 1, 2, 3, 6 중 6을 제외한 1, 2, 3 을 더하면 6이 되어 자신과 같아진다. 4부터 1000까지 정수중 이러한 약수를 갖는 수를 찾아 출력하는 알고리즘을 완성하시오.
[풀기]
문제에서 친절하게도 핵심 키워드를 알려준다.
* 최대의 약수의미 설명 : 어떤수의 모든 약수중 자신을 제외하면 그 절반값이 최대의 약수가 된다. 예를들어 20의 모든 약수는 1, 2, 4, 5, 10, 20 인데 자신(20)을 제외하면 20의 절반값인 10이 최대약수가 된다.
public void algo1(){
String result = ""; //결과 출력을 위한 변수
int addNum = 0; // 약수 총합을 저장할 변수
for( int i = 4; i <= 1000; i++) { // 4~1000 까지 반복
int k = i/2; // 최대 약수 구하기
for(int j = 1; j <= k ; j++) {
if(i % j == 0) { // 약수인지 아닌지 확인
addNum += j;
}
}
if( addNum == i) { // 약수 총합이 자신과 같은지 확인
System.out.println(i + " ");
}
addNum = 0;
}
System.out.println(result); // 출력
}
최대의 약수를 잘 활용하면 효율적인 알고리즘을 만들 수 있었다.