yyyy년 mm월 dd일은 무슨 요일일까?

띠지·2021년 11월 7일

콘웨이의 둠스데이 알고리즘 (Doomsday algorithm)

1. 소개

임백준님의 누워서 읽는 알고리즘을 읽다가, 날짜를 보고 요일을 알 수 있는 신기한 알고리즘을 접하게 되어 더 알아보게 되었다.

학교 전공 수업 중 콘웨이의 생명 게임에 대해서 배운 적 있는 데, 같은 분이 만든 알고리즘이라 해서 더 신기하게 느껴졌다.

둠스데이 알고리즘의 기본적인 아이디어는, 한 해의 둠스데이 (그 해 2월의 마지막 날)의 요일을 알면, 그 날과 요일이 무조건 같은 날들을 통해 특정한 날짜에 빠르게 접근함으로서 요일을 알아내는 것이다.

2. 우리가 외울 수 있는 방법

둠스데이와 요일이 같은 날들

둠스데이와 요일이 같은 날들은 다음과 같다.

2월의 마지막 날 = 둠스데이
- 윤년이 아닐 경우 2월 28일
- 윤년의 경우 2월 29일
4월 4일
6월 6일
8월 8일
10월 10일
12월 12일

즉 둠스데이가 일요일이라면 6월 6일, 10월 10일은 일요일이 되는 것이다.

요일 구하기

이 글을 작성하는 2021년의 둠스데이 (2월 28일) 는 일요일이다.
둠스데이 알고리즘을 통해 크리스마스가 무슨 요일인지 알아보는 절차는 다음과 같다.

2021년의 둠스데이는 일요일
12월의 둠스데이와 요일이 같은 날은 12일
25일 - 12일 = 13일
13 mod 7 = 6이므로 일요일에서 6일 지난 토요일이 정답이 된다.

(A mod B 의 값은 A를 B로 나눈 나머지이다.)
(매년 크리스마스는 항상 둠스데이 하루 전이다.)

같은 방법으로 10월 8일을 알아보면...

10월 10일은 일요일이다.
8 - 10 = - 2
- (2 mod 7) = - 2 이므로 일요일이 되기 2일 전인 금요일이 정답이 된다.

둠스데이와 요일이 같은 홀수 달

2월을 제외한 짝수달은 월=일 인 날이 둠스데이와 요일이 같은 날이지만, 홀수 달에서는 성립하지 않는다.
그래서 사람마다 외우기 쉽게 다양한 바리에이션이 존재한다.

1월
- 윤년이 아닐 경우 1월 3일
- 윤년일 경우 1월 4일
- 년도가 4로 나눠지면 윤년이므로 4일, 아닌 경우 3일으로 기억하기 좋다.
3월
- 3월 21일 (321)
- 3월 0일 (= 2월의 마지막날 = 둠스데이)
- 21일은 321이라서 외우기 쉽고, 3월 0일로 외우면 나머지 연산이 간단하다는 장점이 있다.
5월 / 9월
- 9월 5일
- 5월 9일
- 영어권에서 사무직 일, 반복적인 일을 표현할 때 사용하는 (출퇴근 시간) nine-to-five 를 연상할 수 있는 9월 5일과 그것을 뒤집은 5월 9일
7월 / 11월
- 7월 11일
- 11월 7일
- 편의점 세븐일레븐 을 연상할 수 있는 7월 11일과 그것을 뒤집은 11월 7일

XX년의 둠스데이 알아내기

그렇다면 둠스데이가 무슨 요일인지는 어떻게 알 수 있을까?
우선 2021년의 둠스데이는 일요일이다.
한 번 외워두면 2021년의 모든 날짜에 대해서 요일을 알아낼 수 있다.

방법 1: 가까운 년도에 대해서 사용할만한 방법

둠스데이는 매년 한 요일씩 증가한다.
2021년의 둠스데이가 일요일이었으므로, 2022년의 둠스데이는 월요일이고, 2023년의 둠스데이는 화요일이 된다.

예외적으로 윤년으로 넘어갈 때는 둠스데이가 2일 증가한다.
2024년은 윤년이므로 목요일이 된다.

방법 2: 모든 년도에 대해서 적용 가능한 방법

복잡하지만 항상 적용 가능한 방법이다.

[1]
세기별로 기준일이 있다.
1800 ~ 1899: 금요일
1900 ~ 1999: 수요일
2000 ~ 2099: 화요일
2100 ~ 2199: 일요일
금, 수, 화, 일의 기준일은 계속해서 반복된다. (ex: 2200 ~ 2299: 금요일)

[2]

A: 년도의 끝 두자리 수를 12로 나눈 몫
B: 년도의 끝 두자리 수를 12로 나눈 나머지
C: B를 4로 나눈 몫
기준일 + A + B + C 이 그 해의 둠스데이가 된다.

2021년을 예시로 계산해보면

기준일: 화요일
A: 21 // 12 = 1
B: 21 mod 12 = 9
C: 9 // 4 = 2
화요일 + 12 = 일요일 임을 확인 할 수 있다.

위에서 나온 방법들을 모두 사용해 1888년의 11월 11일이 무슨 요일인지 계산해보면...

기준일: 금요일 (1800 ~ 1899)
A: 88 // 12 = 7
B: 88 mod 12 = 4
C: 4 // 4 = 1
둠스데이 = 금요일 + 12 = 수요일

11월의 둠스데이와 요일이 같은 날은 11월 7일이다.
11 - 7 = 4이므로, 수요일 + 4 = 일요일이다.

정답!

3. with Python

파이썬으로 구현해본 둠스데이 알고리즘

# 인자로 받은 연도의 doomsday를 반환하는 함수
def get_doomsday(year):
    # 기준일 계산을 위해 연도를 앞 2자리, 뒷 2자리로 나눔
    century, year_end = divmod(year, 100)

    # century를 4로 나눈 나머지가 ...
    # 0이면 화요일 (2), 1이면 일요일 (0) ...
    base_dates = [2, 0, 5, 3]
    base_date = base_dates[century % 4]

    # 방법2로 doomsday 구하기
    a, b = divmod(year_end, 12)
    c = b // 4
    doomsday = (base_date + a + b + c) % 7

    return doomsday


# 인자로 받은 연도가 윤년인지 확인하는 함수
def is_leap_year(year):
    if year % 400 == 0:
        return True

    if year % 100 == 0:
        return False

    if year % 4 == 0:
        return True

    return False


# 더해줘야 할 날짜가 며칠인지 구하는 함수
def get_plus_day(year, month, day):
    # 0월은 없으므로 -1
    # 이후 차례대로 1월 3일, 2월 28일, 3월 0일, 4월 4일 ...
    same_days = [-1, 3, 28, 0, 4, 9, 6, 11, 8, 5, 10, 7, 12]

    # 윤년일 경우 1월 4일, 2월 29일로 만들어줌
    if is_leap_year(year):
        same_days[1] += 1
        same_days[2] += 1

    plus_day = (day - same_days[month]) % 7

    return plus_day


def doomsday():
    year, month, day = map(
        int, input("yyyy mm dd의 형태로 날짜를 입력해주세요. (띄어쓰기로 구분)\n").split()
    )

    doomsday = get_doomsday(year)
    plus_day = get_plus_day(year, month, day)

    dow_index = (doomsday + plus_day) % 7
    day_of_the_week = ["일요일", "월요일", "화요일", "수요일", "목요일", "금요일", "토요일"]

    return f"{year}년 {month}월 {day}일은 {day_of_the_week[dow_index]} 입니다."


print(doomsday())