6588. <골드바흐의 추측>

6588번: 골드바흐의 추측 (acmicpc.net)

6588번: 골드바흐의 추측

주어진 짝수를 소수의 합으로 표현하는 문제이다.

1. 시간 제한 0.5

매우빡시다. 일단 test case는 10만번 이하이고 짝수는 100만이하이다.

 

2. 가장 효율적인 알고리즘 > 에리토스테네스..

 이를 활용하고  플러스 메모이제이션을 활용해서 배열을 하나만 만들것이다.

 즉, 짝수의 max범위가 100만이니 우리는 100만까지만 관찰하면 된다. 따라서 100만짜리의 크기의 소수판별 배열을 만들면 while문의 test case 10만번 동안 배열을 만들고 또 만들고 이럴 필요가 없으니 시간 상 메모리 상 효율적인 프로그램을 짤 수있는 것이다.

 

3. 클래스 배열

내가 짠 코드는 클래스아래에다가 선언을 하여 여러 메서드안에 활용을 하게 끔 했다. 이는 가독성 측면에서 좋다.

 허나 메인 메소드에서 배열을 선언하지 않아서 황당할수도 있을 분들께 설명을 덧붙이자면

 아래 isprime()메서드는 사실 배열을 초기화하는 메서드이다.

다시말해, 위의 클래스아래 선언된 primearr을 초기화하는 녀석이다.

 

 

 아래 메인메서드를 보면 primearr= new를 선언하지 않았는데도 메인에서 쓰고 있다. 그 이유는 위의 클래스 아래에다가 primearr을 선언했기 때문에 아래에도 가능하다.

즉 , static으로 해놓은 isprime(); 이걸 한번 선언해줘야 배열이 초기화가 되기에 우리가 원하는 형태인 소수 판별 배열로 만들고 나서, 아래에 for문에 입장해야한다는 것이다.

  package 소수판별;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class _6588_골드바흐의추측_again {
	static final int max = 1000000;
	static boolean[] primearr = new boolean[max+1];
	
	//primearr을 초기화하는 부분이다.
	public static boolean[]  isprime() {
		primearr[0] = primearr[1] = false;
		Arrays.fill(primearr, true);
		for(int i=2; i*i<=max; i++) {
			for(int j=i*i; j<=max; j+=i) {
				primearr[j]= false;
			}
		}
		return primearr;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		//test case less than 10만
		//test case >> 짝수
		//n =a+b > if 여러가지 out b-a max b 최대 a최소 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		//main에 얘를 선언해야 클래스 배열을 초기화 한 상태 즉 우리가 원하는 형태로 변경할수있음.
		 isprime();
		
		while(true) {
			int x = Integer.parseInt(br.readLine());
			if(x==0) {
				break;
			}
			for(int i=2; i<=x/2; i++) {
				if(primearr[i] && primearr[x-i]) {
					sb.append(x+" = "+i+" + "+(x-i)).append('\n');
					break;
				}
			}
			
			
			
		}
		System.out.println(sb);
		
		
		

	}

}

>> 부연 설명 of memoization

메모이제이션은 동일한 계산을 반복해야 하는 경우, 이전에 계산한 값을 메모리에 저장해두고, 다시 그 값을 필요로 할 때 저장해둔 값을 재활용하는 기법을 말합니다. 이 기법은 중복된 계산을 줄이는 데 효과적이기 때문에 프로그램의 성능을 향상시키는 데 도움을 줍니다.

위에서 제시한 코드에서는 소수 판별 결과를 primearr 배열에 미리 저장해두고, 이를 필요할 때마다 재활용하므로, 이는 메모이제이션 기법에 해당합니다.

메모이제이션은 특히 '다이나믹 프로그래밍'이라는 알고리즘 설계 기법에서 자주 사용됩니다. 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법론인데, 이때 작은 부분 문제의 결과를 메모이제이션을 통해 저장해두고 재활용하면 효율적으로 문제를 해결할 수 있습니다.