대박을 꿈꾸는 노력하는 컴돌이

문제 출처: http://rucifer.tistory.com/entry/Algorithm-%EB%AC%B8%EC%A0%9C-01-%EC%A0%95%EC%88%98-%EC%86%8C%EC%9D%B8%EC%88%98-%EB%B6%84%ED%95%B4

정수 소인수 분해 문제의 재귀 풀이: http://sarojaba.tistory.com/233

위 포스트에서 스마트 돌고래 님께서 동적계획법으로 풀어달라는 요청이 있었습니다. 동적계획법을 적용하기 좋은 문제라고 생각되어 적당히 풀어서 풀이를 올립니다.

사용 언어는 Java이고, 파일 입출력은 생략하였고, 샘플 케이스만 만족시켰습니다. 나름 충실히 주석 적어놓았습니만 궁금하신 부분은 언제든 질문하시기 바랍니다. 또한 많은 지적 부탁드립니다.

위키피디아에 소인수 분해 문제에 대한 다양한 알고리즘이 존재하였습니다. 시간이 된다면 공부해서 올리도록 하겠습니다.

main과 solve 메소드는 앞선 포스트의 코드와 내용이 동일합니다. factor 메소드만 보셔도 될듯합니다. 이해하기 쉽게 각 케이스별로 배열을 재계산하게 코딩하였지만 실제 사용한다면 모든 케이스가 배열을 공유하여 계산량을 줄일 수 있도록 전역으로 두시기 바랍니다.

###java
public class PrimeFactorUsingDynamic {
public static void main(String[] args) {

solve(45);
solve(12);
solve(67);
solve(100);
solve(200);
}

/**
* 문제를 푼다.
*
* @param input
* 입력값
*/
public static void solve(int input) {

// 소인수를 더한다.
int output = factor(input);

// 입력값과 계산값이 같으면 소수이다.
boolean isPrime = (output == input);

if (isPrime) {
System.out.println("Prime Number");
} else {
System.out.println(output);
}
}

/**
* 소인수의 합을 구한다. 단, 입력값이 소수인 경우 입력값과 출력값은 같다.
*
* @param n
* 정수 ex) 12 = 2*2*3
* @return 소인수의 합 ex) 7 = 2+2+3
*/
public static int factor(int n) {

// 계산된 값들을 저장할 배열.
// 0과 1은 빈칸으로 두고 사용하지 않는다.
int[] arr = new int[n + 1];

// 2부터 인자로 받은 숫자까지 순차적으로 계산해간다.
for (int i = 2; i < n + 1; i++) {

// 몫을 저장하기 위한 변수
int t = i;

// 몫이 1이라는 뜻은 계산이 끝났다는 의미이다.
while (t != 1) {

// 인수는 2부터 시작한다.
int f = 2;

// 정확히 나누어 떨어지지 않으면 인수를 하나씩 증가시킨다.
while (t % f != 0) {
f++;
}

// 나누어 떨어지는 인수로 나눈다.
t /= f;

// 혹시 이전에 미리 계산된 값이 있으면 사용한다.
if (arr[t] != 0) {
arr[i] = f + arr[t];
break;
}

// 인수를 더해서 저장한다.
arr[i] += f;
}
}

// 모든 계산이 끝나면 배열의 마지막 수가 입력값의 소인수를 모두 더한 값이다.
return arr[n];
}
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

문제 출처: http://rucifer.tistory.com/entry/Algorithm-%EB%AC%B8%EC%A0%9C-01-%EC%A0%95%EC%88%98-%EC%86%8C%EC%9D%B8%EC%88%98-%EB%B6%84%ED%95%B4

이미 출제하신 분께서 반복하는 방법으로 풀어놓으셔서 좀 다르게 풀어볼려고 재귀적인 방법으로 풀어보았습니다. 재귀의 특성상 코드는 보기 편하지만, 성능에 효율적이진 못한것 같습니다.

사용 언어는 Java 이고, 입출력은 생략하였습니다. 주석은 나름 이해하기 편하도록 달아보았습니다. 지적 많이 해주시기 바랍니다.

###java
public class PrimeFactor {
public static void main(String[] args) {

solve(45);
solve(12);
solve(67);
solve(100);
solve(200);
}

/**
* 문제를 푼다.
*
* @param input
* 입력값
*/
public static void solve(int input) {

// 소인수의 합을 구한다.
int output = factor2(input);

// 입력값과 계산값이 같으면 소수이다.
boolean isPrime = (output == input);

if (isPrime) {
System.out.println("Prime Number");
} else {
System.out.println(output);
}
}

/**
* 소인수의 합을 구한다. 단, 입력값이 소수인 경우 입력값과 출력값은 같다.
*
* @param input
* 정수 ex) 12 = 2*2*3
* @return 소인수의 합 ex) 7 = 2+2+3
*/
public static int factor2(int input) {

// 재귀의 탈출 조건은 입력값이 소수인 경우이다.
if (input == 1) {
return 0;
}

// 인수. 초기값은 가장 작은 소수
int factor = 2;

// 0으로 떨어질때까지 인수를 증가시킨다. 루프의 탈출 조건이 적합한 소인수이다.
while (input % factor != 0) {
factor++;
}

// 현재 인수와 이후로 구할 인수를 더한다. 소인수를 나눈 몫을 이용해 다음 계산을 한다.
return factor + factor2(input / factor);
}
}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.