날짜 계산#

시간 계산의 경우, 월별로 일수를 리스트로 만들어두는게 좋다.

1
num_of_days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
2
day_of_week = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]

어떤 요일인지 물어보는 문제의 경우는 위처럼 요일 리스트도 만들어두는게 편하다.
기준 날짜의 요일과 지난 일수를 7로 나눈 나머지를 활용하면 특정 날짜의 요일을 쉽게 구할 수 있다.

진법 변환#

이진수에서 십진수로, 또는 십진수에서 팔진수로 등등, 진법 변환을 코드로 자동화해봐라 하는 주제다.

1
while True:
2
    if N < B:
3
        digits.append(N)
4
        break
5
    digits.append(N%B)
6
    N //= B
7

8
for digit in reversed(digits):
9
    print(digit, end="")

어떤 수를 십진수로 바꾸거나, 십진수를 다른 진수로 바꾸는건 어렵지 않다.

B진수를 십진수로 바꾸는건 digit마다 B의 거듭제곱으로 곱한 이후 더하면 되고,
십진수를 B진수로 바꾸는건, N이 B보다 작아질 때까지 B로 나누면서 나머지를 digit으로 추가하면 된다.

그러면 10이 아닌 A, B에 대해 A진수를 B진수로 표현하려면 어떻게 해야 할까?
A진수 숫자를 십진수로 바꿔서 다시 B진수로 변환하면 된다.

수학적으로는 십진수로 바꾼다 보다는 정수 값으로 해석 후 다른 진법으로 재표기한다고 한다지만
코드로 짤 때는 그냥 A진수를 십진수로 바꾸고 다시 B진수로 바꾼다 라고 말해도 된다.

구간 칠하기 & 사각형 칠하기#

구간 칠하기는 어려울게 없다.

코드트리에서 인덱스와 구간을 동일시해서 좀 헷갈리는 부분이 있었는데
문제에서 어느 범위까지 포함시키라고 하는지를 잘 읽고, 뒤에 인덱스를 추가할지 뺄지만 결정하면 된다.

주어진 범위가 음수 인덱싱을 필요로 하는 상황이면 offset을 더하면 된다.

사각형 칠하기는 2차원 배열을 사용하면 구간 칠하기보다 더 쉽다.

사각형이 겹치는 영역을 어떻게 계산하지???
계산 안하고 그냥 주어진 범위를 1로 칠하고, 마지막에 1로 칠해진 영역 넓이를 구하면 됨.

값을 반환하는 재귀함수#

먼저 값을 반환하는 함수는 결과값을 얻는 것이 목적이다.
재귀 함수는 그 결과값을 얻기 위해 자기 자신을 다시 호출한다.

가장 쉬운 예시는 팩토리얼이다. $n!$ 을 구하려면 $(n-1)!$ 을 알아야 한다.

factorial(n)의 목적은 $n!$ 을 반환하는 것이다.
그런데 $n! = n \times (n-1)!$ 이므로, 함수 안에서 factorial(n-1)을 호출한 뒤
그 결과에 n을 곱하면 된다.

그럼 factorial(n-1)은 어떻게 구할까?
마찬가지로 $(n-1)! = (n-1) \times (n-2)!$ 이므로 factorial(n-2)를 호출하면 된다.

이 과정은 인자가 계속 작아지면서 반복된다. 하지만 재귀 호출이 영원히 이어지면 안 되므로
더 이상 자기 자신을 호출하지 않고 바로 값을 반환하는 지점이 필요하다.

이 지점을 베이스 케이스라고 한다.
팩토리얼에서는 보통 $1! = 1$ 이므로, 인자로 1이 들어왔을 때 1을 반환하는 상황이 베이스 케이스가 된다.

1
def factorial(n: int):
2
    if n <= 1:
3
        return 1
4

5
    return factorial(n-1) * n

정리하면, 값을 반환하는 재귀 함수는 베이스 케이스와 재귀 케이스를 나눠서 생각하면 된다.

베이스 케이스에서는 더 이상 재귀 호출을 하지 않고 기본값을 반환한다.
팩토리얼에서는 factorial(1)이 여기에 해당하고, 1을 반환한다.

재귀 케이스에서는 현재 문제를 더 작은 문제로 줄인 뒤, 그 결과를 이용해 현재 단계의 값을 계산해서 반환한다.
팩토리얼에서는 factorial(n-1)의 결과에 n을 곱해서 factorial(n)의 결과를 만든다.

결국 값을 반환하는 재귀 함수는 더 작은 문제로 나누지 않아도 바로 답을 알 수 있는 상황과
작은 문제의 결과를 이용해 현재 단계의 값을 계산하는 방법을 코드로 표현한 것이다.

값을 반환하지 않는 재귀함수#

이쪽은 어떤 계산 결과를 돌려받는 것이 목적이 아니다.
대신 재귀 호출이 진행되는 과정에서 출력하거나, 방문하거나, 상태를 기록하는 것이 목적이다.

예를 들어 숫자를 출력하는 문제를 생각하면, 함수의 목적은 n에 대한 값을 계산해서 반환하는 것이 아니라
n부터 1까지의 숫자를 특정 순서로 출력하는 것이다.

1
def print_num(n: int):
2
    if n == 0:
3
        return
4

5
    print(n)
6
    print_num(n - 1)

여기서 return은 값을 돌려주기 위한 것이 아니라, 더 이상 재귀 호출을 하지 않고 함수를 끝내기 위한 장치다.

즉 값을 반환하지 않는 재귀함수에서도 베이스 케이스는 필요하지만, 그 역할은 “기본값 반환”이 아니라 “호출 종료”에 가깝다.

값을 반환하지 않는 재귀함수에서 가장 중요하게 느낀 건, 재귀 호출 전후에 어떤 코드를 두느냐에 따라 실행 순서가 달라진다는 점이다.

1
def f(n):
2
    if n == 0:
3
        return
4

5
    print(n)
6
    f(n - 1)

이렇게 print가 재귀 호출보다 앞에 있으면 함수가 아래로 내려가면서 출력된다.

1
f(3)
2
print(3)
3
  f(2)
4
  print(2)
5
    f(1)
6
    print(1)
7
      f(0) 종료

반대로 print를 재귀 호출 뒤에 두면, 가장 깊은 곳까지 내려갔다가 다시 돌아오면서 출력된다.

1
def f(n):
2
    if n == 0:
3
        return
4

5
    f(n - 1)
6
    print(n)

1
f(3)
2
  f(2)
3
    f(1)
4
      f(0) 종료
5
    print(1)
6
  print(2)
7
print(3)

이 부분은 트리 순회를 생각하면 더 직관적이었다.

1
현재 노드를 먼저 처리하면 전위 순회
2
왼쪽 재귀와 오른쪽 재귀 사이에서 처리하면 중위 순회
3
자식 재귀를 모두 끝낸 뒤 처리하면 후위 순회

결국 재귀는 함수가 계속 아래로 내려가는 호출 과정과, 베이스 케이스를 만나 다시 위로 돌아오는 반환 과정이 분리되어 있다.
그리고 현재 단계에서 할 일을 재귀 호출 앞에 둘지 뒤에 둘지에 따라, 그 일이 내려가면서 실행될지 돌아오면서 실행될지가 결정된다.