[프로그래머스/Day 11] 2016년 - 첼러의 공식

1. 문제 개요

프로그래머스의 '2016년' 문제를 풀면서 겪었던 시행착오와 해결 과정을 정리합니다.

이 문제의 핵심은 "특정 날짜의 요일을 어떻게 계산하는가?" 였습니다.

이를 해결하기 위해 독일의 수학자 크리스티안 첼러가 고안한 첼러의 공식(Zeller's congruence)을 도입했습니다.

 

구체적으로는 2016년 5월 24일의 요일을 구하는 예시와, 이를 프로그래밍(C++) 알고리즘 문제(프로그래머스 '2016년')에 적용했을 때 발생한 오류를 분석하고 올바른 로직을 도출하는 과정을 다루었습니다.

---

2. 첫 번째 접근: (시행착오)

첼러의 공식을 그대로 코드화하는 과정에서 두 가지 치명적인 오류가 발생하여 틀린 답을 도출했습니다.

 

• 오류 1: 1월과 2월의 예외 처리 누락
  • 현상: 입력받은 월(Month)을 그대로 공식에 대입했습니다. (예: 1월 → 1, 2월 → 2)
  • 원인: 첼러의 공식은 3월을 한 해의 시작으로 봅니다. 따라서 1월과 2월은 전년도의 13월, 14월로 변환하여 계산해야 한다는 대전제를 어겼습니다.
• 오류 2: 음수 모듈러(%) 연산 미처리
  • 현상: 계산 결과가 음수가 나왔을 때, C++의 % 연산자가 음수를 반환하여 배열 인덱스 에러 또는 잘못된 매핑이 발생했습니다.
  • 원인: 수학적 Mod 연산과 달리 프로그래밍 언어(C/C++ 등)에서는 음수의 나머지를 음수로 반환하므로, 7을 더해 양수로 보정하는 과정이 필요했습니다.

[수정 전 코드]

1. 일요일부터 토요일까지 담은 요일 맵을 초기화한다.
2. 일, 월, 연도 뒤 두 자리, 연도 앞 두자리를 각 변수로 설정한다.
3. 첼러의 공식에 대입해 계산한다.
4. 결과로 나온 숫자를 요일 맵에 대조해 결과를 구한다.

string solution(int a, int b) {
    string answer = "";
    
    // 1. 일요일부터 토요일까지 담은 요일 맵을 초기화한다.
    map<int, string> dayMap = {
        {0, "SAT"},
        {1, "SUN"},
        {2, "MON"},
        {3, "TUE"},
        {4, "WED"},
        {5, "THU"},
        {6, "FRI"}
    };
    
    // 2. 일, 월, 연도 뒤 두 자리, 연도 앞 두자리를 각 변수로 설정한다.
    const int q = b;
    const int m = a;
    const int K = 16;
    const int J = 20;
    int calcValue = 0;
    
    // 3. 첼러의 공식에 대입해 계산한다.
    calcValue = (q + ((13 * (m + 1)) / 5) + K + (K / 4) + (J / 4) - (2 * J)) % 7;
    
    // 4. 결과로 나온 숫자를 요일 맵에 대조해 결과를 구한다.
    answer = dayMap[calcValue];
    
    return answer;
}

 

 

---

3. 두 번째 접근: 로직의 이해

오류를 수정하기 위해 공식의 수학적 구성 원리를 깊이 있게 이해하고 코드를 재설계했습니다.

3-1. 공식의 구성 원리 (숫자의 비밀)

 

• 13과 5: 3월부터 시작되는 달들의 날짜 수(31, 30, 31...) 패턴을 수학적으로 근사하기 위한 기울기(약 2.6)입니다. 불규칙한 2월을 맨 뒤로 보냈기에 가능한 식입니다.
• 4: 4년마다 돌아오는 윤년(366일)으로 인해 밀리는 요일을 보정합니다.
• -2J: 100년 단위로 윤년을 건너뛰는 그레고리력의 규칙과 세기에 따른 요일 변화를 반영한 상수입니다.
• Mod 7: 요일은 7일 주기로 순환하기 때문입니다.

3-2. 올바른 알고리즘 적용

위 원리에 따라 코드를 다음과 같이 수정했습니다.

1. 입력 변환: if (month < 3) 조건문을 사용하여 1, 2월인 경우 month += 12, year -= 1 처리를 수행했습니다.
2. 나머지 보정: 최종 결과값에 % 7을 수행한 후, 값이 0보다 작으면 +7을 하여 양수 인덱스를 확보했습니다.

[수정 후 코드]

1. 일요일부터 토요일까지 담은 요일 맵을 초기화한다.
2. 일, 월, 연도를 각 변수로 설정한다.
3. 1월, 2월은 전년도 13월, 14월로 변경한다.
4. 첼러의 공식에 대입해 계산한다.
5. 음수 모듈러 처리
6. 결과로 나온 숫자를 요일 맵에 대조해 결과를 구한다.

// 2. 일, 월, 연도를 각 변수로 설정한다.
int q = b;
int m = a;
int year = 2016;

// 3. 1월, 2월은 전년도 13월, 14월로 변경한다.
if(m < 3)
{
    m += 12;
    year -= 1;
}

int K = year % 100;
int J = year / 100;


// 4. 첼러의 공식에 대입해 계산한다.
int calcValue = (q + ((13 * (m + 1)) / 5) + K + (K / 4) + (J / 4) - (2 * J)) % 7;

// 5. 음수 모듈러 처리
if(calcValue < 0)
{
    calcValue += 7;
}

 

 

---

4. 정리

첼러의 공식은 달력 없이 요일을 맞힐 수 있는 강력한 도구이지만, 그레고리력의 규칙성을 수학식으로 압축했기 때문에

"3월이 시작, 1/2월은 전년도 끝"이라는 전제 조건을 반드시 지켜야 합니다.

• 최종 결과:
  • 수정된 로직으로 계산한 2016년 5월 24일의 요일은 화요일(Tuesday)입니다.
• 결론:
  • 알고리즘 문제 풀이 시 수학 공식을 사용할 때는 해당 공식의 정의 범위와 사용하는 언어의 연산 특성(음수 나머지 처리)을 모두 고려해야 정확한 구현이 가능합니다.