메모/코딩 문제풀기&다시보기

바뀌기 전 정처기 알고리즘 기출문제를 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); // 출력
	}

 

최대의 약수를 잘 활용하면 효율적인 알고리즘을 만들 수 있었다.