2485번 가로수 문제, GCD와 벡터 인덱스의 함정 파헤치기

오늘은 백준 알고리즘 문제 2485번, '가로수'를 풀면서 겪었던 시행착오와 그 과정에서 얻은 교훈들을 공유하고자 합니다. 처음에는 단순해 보였던 이 문제가 GCD(최대공약수)와 C++ 벡터의 인덱스 관리라는 복병을 만나면서 꽤나 진땀을 뺐습니다.

학습 주제

• 오늘 공부한 주제: 백준 2485번 '가로수' 문제 풀이 및 C++ 벡터 인덱스 관리, GCD 결합법칙 이해
• 학습 날짜: 2026년 2월 3일

질문과 탐구

문제를 처음 봤을 때, 가로수들의 위치가 주어졌을 때 목표하는 간격으로 만들기 위해 추가로 심어야 하는 나무의 수를 구하는 것이 목표였습니다. 직관적으로 각 가로수 사이의 간격을 구하고, 이 간격들의 최대공약수(GCD)가 최종 목표 간격이 될 것이라고 생각했습니다.

• 주요 질문:
  • n개의 수들의 최대공약수는 어떻게 구할까?
  • GCD가 결합법칙 gcd(a, b, c) = gcd(gcd(a, b), c)를 만족하는 이유는 무엇일까?
  • C++ 벡터에서 인덱스를 잘못 사용하면 어떤 문제가 발생하는가?
  • 메모리 초과 오류는 왜 발생하는가?

핵심 학습 내용

1. n개의 수의 GCD 구하기

처음에는 gcd(a, b) 함수만 있으면 되는 줄 알았지만, 문제의 구조상 여러 간격들의 GCD를 구해야 했습니다. GCD는 결합법칙이 성립하므로, gcd(a, b, c) = gcd(gcd(a, b), c)와 같이 순차적으로 GCD를 계산하여 n개의 수들의 GCD를 구할 수 있다는 것을 배웠습니다.

// n개의 수들의 GCD를 구하는 함수
int gcd_of_array(vector<int>& nums) {
    int result = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        result = gcd(result, nums[i]); // 순차적으로 GCD 계산
    }
    return result;
}

2. GCD 결합법칙의 이해

'GCD가 왜 결합법칙이 성립하는지'가 처음에는 직관적으로 와닿지 않았습니다. AI와의 대화를 통해 GCD의 정의(x와 y를 나누는 모든 공약수 중 가장 큰 수)에 집중하여, d가 a, b, c를 모두 나눈다면 d는 gcd(a, b)도 나누고, gcd(gcd(a, b), c)도 나눈다는 것을 이해했습니다. 즉, 공약수 집합이 같기 때문에 최대공약수도 같다는 원리를 명확히 파악할 수 있었습니다.

3. C++ 벡터 인덱스 접근의 함정

이 문제에서 가장 큰 벽은 C++ 벡터의 인덱스 접근 문제였습니다. diff 벡터에 값을 push_back하지 않고 diff[i] = ...와 같이 바로 인덱스로 접근하려다 보니, 실제 벡터의 크기보다 큰 인덱스에 접근하여 정의되지 않은 동작이나 메모리 초과 오류를 발생시켰습니다.

• 잘못된 접근 방식: diff 벡터가 size=1인데 i=1로 diff[1]에 접근
• 올바른 접근 방식: push_back을 사용하거나, 이미 충분한 크기가 확보된 상태에서 [] 연산자 사용

AI는 이 부분을 명확히 지적하며 push_back 사용을 권장했고, 이후 diff 벡터의 크기(n-1)와 반복문의 범위(0부터 diff.size()-1까지)를 일치시키는 것도 중요함을 배웠습니다.

이해한 내용

이번 문제 풀이를 통해 C++ 벡터를 사용할 때 인덱스 범위를 항상 확인하고, push_back과 같은 안전한 메서드를 활용하는 것이 얼마나 중요한지 뼈저리게 느꼈습니다. 또한, GCD의 결합법칙이 단순히 공식 암기가 아니라 그 원리 자체를 이해해야 다양한 문제에 응용할 수 있다는 것을 알게 되었습니다.

처음에는 diff 벡터에 더미 값을 넣어 인덱스 오류를 피하려 했지만, 이는 근본적인 해결책이 되지 못함을 깨달았습니다. 결국 diff 벡터의 크기와 반복문의 범위를 정확히 일치시키는 것이 핵심이었습니다.

실전 적용

• 이 지식을 어디에 적용할 수 있을지:
  • 앞으로 C++로 코딩할 때 벡터 인덱스 범위를 세심하게 관리하게 될 것입니다.
  • GCD 관련 문제에서 결합법칙을 활용하여 효율적인 해법을 설계하는 데 도움이 될 것입니다.
  • 메모리 제약이 있는 문제를 풀 때, 불필요한 벡터 사용을 줄이고 O(1) 메모리 공간 복잡도를 달성하는 방법을 고민하게 될 것입니다.
• 실습 계획:
  • 유사한 유형의 백준 문제 (예: GCD를 활용하는 다른 수학 문제)를 풀어보며 GCD 활용 능력을 키웁니다.
  • C++ STL 컨테이너 (vector, array 등)의 인덱스 접근 및 삽입/삭제 관련 동작 방식을 더 깊이 공부합니다.
  • 시간 복잡도와 공간 복잡도를 고려한 최적화 기법들을 익힙니다.

추가 학습 계획

• 더 깊이 공부하고 싶은 부분:
  • GCD를 이용한 다양한 알고리즘 문제
  • C++ STL 컨테이너의 내부 동작 원리 및 최적화 방안
  • 알고리즘 문제 해결 시 메모리 사용량을 줄이는 다양한 기법
• 관련 자료 찾기:
  • GCD 관련 수학 원리 설명 자료
  • C++ std::vector 공식 문서 및 사용 예제
  • 알고리즘 문제 풀이에서 메모리 초과 오류 해결 사례
• 다음 학습 주제:
  • 최대공약수와 최소공배수를 활용하는 문제 (예: 유클리드 호제법 확장)
  • 동적 계획법 (DP) 문제 해결 전략

참고 자료

• AI와의 대화: ChatGPT
• 문제: 백준 2485번 '가로수'
• C++ GCD 함수 구현: 유클리드 호제법