[BOJ] 윤년 - 2753

[Bronze V] 윤년 - 2753

문제 링크

성능 요약

메모리: 31120 KB, 시간: 40 ms

분류

구현, 사칙연산, 수학

제출 일자

2024년 9월 11일 17:19:16

문제 설명

연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오.

윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다.

예를 들어, 2012년은 4의 배수이면서 100의 배수가 아니라서 윤년이다. 1900년은 100의 배수이고 400의 배수는 아니기 때문에 윤년이 아니다. 하지만, 2000년은 400의 배수이기 때문에 윤년이다.

입력

첫째 줄에 연도가 주어진다. 연도는 1보다 크거나 같고, 4000보다 작거나 같은 자연수이다.

출력

첫째 줄에 윤년이면 1, 아니면 0을 출력한다.

후기

나의 제출은 다음과 같았다

import sys
input = sys.stdin.readline

n = int(input())

print(int((n%4 == 0 and n%100 != 0) or (n%400 == 0)))

나름 짧게해서 괜찮아보이는데? 라고 생각했는데 역시 숏코딩에는 미친 천재들이 많았다.

다음은 숏코딩 4등의 답안이다.

이 답안의 공간/시간복잡도는 31256KB, 44ms이다.

n=int(input())
print(+(n&-n>3|8>>n%50))

일단 이해가 안됐던 문법과 로직은 다음과 같다.

1. print()의 첫 번째로 나오는 연산자인 +는 무엇을 의미하는 것인가?
2. &- 연산자는 무엇이며, 왜 4의 배수를 >3으로 표현하였는가?
3. >> 연산자는 무엇이며, 왜 50으로 나누었는가?
4. 비트연산이 and와 or 보다 연산이 빠른 이유는 무엇인가?

claude에게 물어보았다.

1. print()의 + 연산자:
   여기서 +는 불리언 값을 정수로 변환하는 역할을 한다. True는 1로, False는 0으로 변환된다.
   이는 int(True)나 int(False)와 같은 효과를 더 간단히 표현한 것이다.
2. n&-n>3:
   &는 비트 AND 연산자다. n&-n은 n의 가장 오른쪽 1 비트만 남기는 연산이다.
   4의 배수는 이진수로 표현했을 때 최소 100이므로, 가장 오른쪽 1 비트의 위치가 3번째 이상이다.
   따라서 n&-n>3은 n이 4의 배수인지 확인하는 조건이 된다.
   
   
3. 8>>n%50:
   >>는 비트 우측 시프트 연산자다. n%50은 0부터 49 사이의 값을 가진다.
   8>>(n%50)는 8을 n%50만큼 우측으로 시프트한다.
   이 결과는 n이 100이나 200의 배수일 때만 0이 되고, 400의 배수일 때는 1이 된다.

나는 +연산자가 불리언 값을 정수로 변환하는 역할을 하는지 몰랐었다. 결국 +안의 값에 따라 1 또는 0을 출력할 것이다.

다음으로는 시프트 연산자에 대한 내용인데, 이것도 직접 비트연산을 해 보았지만 잘 이해가 되지 않아 자세히 살펴보았다.

n&-n 연산에 대한 고찰

1. -n의 의미:
   • 컴퓨터에서 음수는 2의 보수로 표현된다.
   • -n은 n의 모든 비트를 뒤집고 1을 더한 값이다.
2. & 연산:
   • 비트 AND 연산으로, 두 비트가 모두 1일 때만 1을 반환한다.
3. n&-n의 결과:
   • 이 연산은 n의 가장 오른쪽에 있는 1 비트만 남기고 나머지는 모두 0으로 만든다.

예시:

n  = 01100 (12)
-n = 10100 (2의 보수)
n&-n = 00100 (4)

이 연산의 특징:

• 4의 배수는 이진수로 끝자리가 00이다.
• 따라서 4의 배수에 대해 n&-n을 하면 항상 4 이상의 값이 나온다.
• 4의 배수가 아닌 수는 n&-n의 결과가 4 미만이다.

"가장 오른쪽에 있는" 비트라는 표현을 좀 더 명확히 설명하겠다.
"가장 오른쪽에 있는 1인 비트"라고 말하는 것이 더 정확하다. 이진수에서 오른쪽에서부터 왼쪽으로 읽어가며 처음 만나는 1을 의미한다.

12의 경우, 12를 이진수로 표현하면 1100이다.
오른쪽에서부터 읽어가면 0, 0, 1, 1 순서로 비트를 만난다.
첫 번째로 만나는 1은 세 번째 자리에 있다.

따라서 12(1100)의 경우, n&-n 연산 후 결과는 0100(4)가 된다.
이는 가장 오른쪽에 있는 1인 비트만 남기고 나머지는 모두 0으로 만든 결과다.

다른 예를 더 들어보겠다:

10 (1010) -> n&-n = 0010 (2)
24 (11000) -> n&-n = 01000 (8)
7 (111) -> n&-n = 001 (1)

8>>n%50 연산에 대한 고찰

1. 비트 우측 시프트 연산자 >>:
   이 연산자는 비트들을 오른쪽으로 지정된 수만큼 이동시킨다.
   왼쪽에 빈 자리는 0으로 채워진다.
   
   
2. n%50의 의미:
   n을 50으로 나눈 나머지를 구한다.
   결과는 0에서 49 사이의 값이 된다.
   
   
3. 시프트 연산의 결과:
   8(1000)을 오른쪽으로 0~49칸 이동시키는 것이다.
   
   0칸 이동: 1000 (8)
   1칸 이동: 0100 (4)
   2칸 이동: 0010 (2)
   3칸 이동: 0001 (1)
   4칸 이동 이상: 0000 (0)
   
   
4. 윤년 판단에 활용:
   • n이 100의 배수일 때 (n%100 == 0), n%50은 0이 된다.
   • n이 400의 배수일 때 (n%400 == 0), n%50은 0이 된다.
   • 하지만 400의 배수일 때는 다른 조건에 의해 1이 되어야 한다.

이 연산의 결과:

• n이 100의 배수이지만 400의 배수가 아닐 때: 8 (1000)
• n이 400의 배수일 때: 0 (0000)
• 그 외의 경우: 0 (0000)

이렇게 해서 100의 배수이면서 400의 배수가 아닌 경우만 1이 아닌 값(8)이 나오게 되고, 이를 통해 윤년 여부를 판단하는 데 활용된다.

이 방식은 매우 간결하지만 이해하기 어려운 트릭이다. 실제 코드에서는 명확성을 위해 일반적인 산술 연산과 조건문을 사용하는 것이 좋다.

... 라고 해서 이해를 마치고 계산 방식에 맞게 계산을 하고 있는데 갑자기 엉뚱한 소리를 한다.
n이 300일 때 1이 출력되기 때문에 위 코드는 틀린 것이라는 말이다.

여기서 claude를 결제한 나를 후회하게 만드는 상황이 발생했다.

똑같은 질문을 GPT한테 해보았다.

n=int(input())
print(+(n&-n>3|8>>n%50))


파이썬에서 위 코드를 수행했을 때, n이 300이면 나오는 결과는?

이후 Gemini와 뤼튼한테도 똑같이 물어봤는데 한번에 옳은 답을 하지 못하였다...
물론 GPT도 왜 0이 나오는지에 대해서는 명확히 설명하진 못하였고 재차 물어봐야만 답을 해줬다.

이 숏코딩의 핵심은 비트연산자도 있지만, 연산자의 우선순위도 있다.

python에서의 연산자 우선순위

1. 괄호 ()
2. 지수 **
3. 단항 연산자: +, - (양수, 음수) ~ (비트 NOT)
4. 곱셈 및 나눗셈 연산자: *, /, // (나눗셈), % (나머지)
5. 덧셈 및 뺄셈 연산자: +, -
6. 비트 시프트 연산자: <<, >>
7. 비트 AND 연산자: &
8. 비트 XOR 연산자: ^
9. 비트 OR 연산자: |
10. 비교 연산자: ==, !=, >, >=, <, <=, is, is not, in, not in
11. 논리 NOT 연산자: not
12. 논리 AND 연산자: and
13. 논리 OR 연산자: or
14. 조건부 표현식: if ... else
15. 대입 연산자: =, +=, -=, *=, /=, //=, %=, **=, &=, |=, ^=, >>=, <<=
16. 표현식 해석 연산자: lambda

결론

생성형 AI에 대한 맹신은 금지다!