17103번 골드바흐 파티션 문제, 실수와 개선

'17103번 골드바흐 파티션 문제'를 해결하는 과정에서 발생한 실수와 이를 개선해나간 여정을 담고 있습니다. 처음에는 알고리즘 설계는 옳았으나 구현 디테일에서 반복된 오류로 좌절하기도 했지만, AI와의 질의응답을 통해 해결책을 찾아가는 과정을 공유하고자 합니다.

학습 주제

• 공부 주제: 골드바흐 파티션 문제 해결 및 알고리즘 최적화
• 대화 제목: 17103 골드바흐 파티션 문제에서의 실수와 개선
• 학습 날짜: 2026년 2월 24일

질문과 탐구

처음에는 문제 해결을 위한 기본적인 투 포인터 알고리즘을 적용했으나, 여러 차례의 수정에도 불구하고 시간초과와 잘못된 결과라는 두 가지 문제에 직면했습니다.

• 초기 문제: 골드바흐 파티션 개수 계산 시 while (L < R) 조건으로 인해 같은 소수 두 개를 더하는 경우를 놓치는 실수.
• 두 번째 문제: while (L <= R)로 수정 후 시간초과 발생.
• 궁극적인 질문: 왜 시간초과가 발생하는지, 그리고 이를 해결하기 위한 근본적인 방법은 무엇인지 탐구했습니다.

핵심 학습 내용

이번 대화를 통해 알고리즘 문제 해결 과정에서 겪을 수 있는 다양한 함정과 최적화 방안을 배울 수 있었습니다.

배운 주요 개념

1. 골드바흐 파티션: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다는 정리. 이 문제에서는 이러한 표현의 개수를 세는 것이 목표였습니다.
2. 투 포인터 알고리즘: 정렬된 배열에서 두 개의 포인터를 사용하여 원하는 조건을 만족하는 쌍을 찾는 효율적인 알고리즘.
3. 에라토스테네스의 체: 주어진 범위 내의 모든 소수를 효율적으로 찾는 알고리즘.
4. 합성수의 속성: 모든 합성수는 자신의 제곱근 이하의 소인수를 반드시 가진다는 성질.

중요한 포인트 정리

• 구현 디테일의 중요성: 알고리즘 설계가 아무리 뛰어나도 인덱싱, 범위 설정 등의 작은 실수가 전체 결과에 치명적인 영향을 줄 수 있습니다.
• 시간 복잡도의 중요성: 단순히 답을 구하는 것을 넘어, 주어진 시간 제한 내에 해결 가능한 효율적인 알고리즘을 선택해야 합니다. 특히, 반복적인 연산이 많은 경우 전처리 과정의 효율성이 매우 중요합니다.
• 문제의 본질 파악: 골드바흐 파티션 문제의 핵심은 '골드바흐 정리'나 '투 포인터' 자체가 아니라, 효율적인 소수 판별에 있다는 것을 깨달았습니다.
• 에라토스테네스의 체의 원리:
  • i * i <= max까지만 반복하는 이유: max 이하의 모든 합성수는 반드시 √max 이하의 소인수를 가지기 때문입니다. √max보다 큰 소인수만으로 max를 만들려면 √max보다 큰 다른 인수가 필요하게 되어 모순이 발생합니다.
  • j = i*i부터 배수를 지우는 이유: i의 배수 중 i*i보다 작은 수들은 이미 i보다 작은 소인수 단계에서 제거되었기 때문입니다. 예를 들어, 2i, 3i 등은 2나 3 단계에서 이미 처리됩니다. i*i는 i가 처음으로 만들어내는 새로운 합성수입니다.

예시 코드 (개선된 소수 생성 부분)

vector<bool> isPrime(max + 1, true);
isPrime[0] = isPrime[1] = false;

for(int i = 2; i * i <= max; i++){
    if(isPrime[i]){
        for(int j = i * i; j <= max; j += i){
            isPrime[j] = false;
        }
    }
}

이해한 내용

이번 학습을 통해 저는 알고리즘 문제 해결에 대한 깊이 있는 이해를 얻었습니다.

• 새로 알게 된 것:
  • 문제가 시간 초과로 발생하는 경우, 가장 먼저 의심해야 할 부분은 반복 연산이 많은 전처리 과정이라는 사실을 알게 되었습니다.
  • 합성수의 속성과 소인수 분해의 관계를 명확히 이해하게 되었습니다.
  • 투 포인터 알고리즘이 만능이 아니며, 문제의 특성에 따라 더 단순하고 효율적인 대안(예: 절반 탐색)이 존재함을 알게 되었습니다.
• 개념 정리:
  • 투 포인터 vs 절반 탐색: 골드바흐 파티션 문제의 경우, 소수 목록을 미리 만들어두면 p <= N/2까지만 검사하는 절반 탐색이 투 포인터보다 더 직관적이고 구현이 간단하며 효율적임을 이해했습니다.
  • 소수 생성의 중요성: 알고리즘의 성능은 결국 가장 복잡한 부분, 여기서는 소수 생성 부분의 시간 복잡도에 좌우된다는 점을 명확히 인지했습니다.

실전 적용

이 학습 내용은 앞으로 코딩 테스트를 비롯한 다양한 알고리즘 문제 해결에 큰 도움이 될 것입니다.

• 적용 가능 분야:
  • 수학적 성질을 이용하는 문제
  • 대규모 데이터에 대한 반복 연산이 필요한 문제
  • 에라토스테네스의 체와 같은 소수 관련 문제
• 실습 계획:
  • BOJ 9020과 같이 골드바흐 파티션 문제와 유사한 다른 문제들을 풀어보며 에라토스테네스의 체와 절반 탐색 또는 투 포인터를 조합하는 연습을 꾸준히 할 계획입니다.
  • 시간 복잡도 분석 능력을 더욱 향상시켜, 문제 풀이 시작 단계에서부터 병목 지점을 예측하고 최적의 알고리즘을 선택하는 연습을 할 것입니다.
• 응용 아이디어:
  • 체로 소수 목록을 미리 만들어두면, 어떤 수가 소수의 합으로 표현될 수 있는지(골드바흐의 추측)를 빠르게 검증하는 데 활용할 수 있습니다.

추가 학습 계획

이번 대화를 통해 더 깊이 탐구하고 싶은 부분들이 생겼습니다.

• 더 깊이 공부하고 싶은 부분:
  • 선형 체 (Linear Sieve): O(N)의 시간 복잡도를 가지는 선형 체에 대해 더 자세히 알아보고 싶습니다.
  • 골드바흐 추측: 아직 증명되지 않은 골드바흐 추측 자체에 대한 수학적인 탐구도 흥미롭습니다.
• 관련 자료 찾기:
  • 수학적 증명에 대한 자료를 찾아보며 '왜 log log N 복잡도가 나오는지', '왜 선형 체가 O(N)인지'를 수학적으로 깊이 이해하고 싶습니다.
  • 다양한 코딩 테스트 플랫폼에서 소수 관련 고난도 문제들을 찾아 풀어볼 예정입니다.
• 다음 학습 주제:
  • 이번 경험을 바탕으로 '자료구조 및 알고리즘 심화' 과정을 다시 복습하며, 다양한 문제 유형에 대한 적용 능력을 키울 계획입니다.

참고 자료

이번 학습에서 직접적으로 언급되거나 간접적으로 도움을 받은 자료는 다음과 같습니다.

• ChatGPT와의 대화 기록: 문제 해결 과정에서 AI와의 질의응답 내용을 바탕으로 정리했습니다.
• 알고리즘 관련 온라인 강의 및 문서: 에라토스테네스의 체, 투 포인터 알고리즘 등에 대한 기본적인 이해를 돕는 자료들을 참고했습니다. (구체적인 링크는 이번 대화에서 직접적으로 언급되지 않아 생략합니다.)