99클럽 코테 스터디 2일차 TIL - 백준 14495, 백준 1991

1. 문제: https://www.acmicpc.net/problem/14495

✅ 첫번째 풀이

n = int(input())
arr = [1] * (n+3)

if 1<=n and n<=3:
  print(1)
else:
  for i in range(4, n+1):
    arr[i] = arr[i-1] + arr[i-3]
  print(arr[n])

 

- 초반에 n-1, n-3 인덱스의 예외사항에 걸리고 싶지 않아 n+3 크기의 초기값 1인 배열을 초기화했다.

- 그리고 문제에 f(1) = f(2) = f(3) = 1이므로 이 경우에 1을 print하고, 아닌 경우에 해당 수열 공식을 따르는 것으로 처리했다.

 

하지만 다른 사람의 코드를 보면서 알게된 사실은 !

python의 range가 범위를 벗어나면 for문이 실행되지 않는다는 점이었다.

즉, 위와 같이 1로 초기화했으면 if else문 분기처리하지 않아도 된다.

 

✅ 두번째 풀이

n = int(input())
arr = [1] * (n+3)

for i in range(4, n+1):
  arr[i] = arr[i-1] + arr[i-3]
print(arr[n])

 

2. 문제: https://www.acmicpc.net/problem/1991

💡 키워드: 트리

 

오늘은 트리 순회에 대해 복습했다. 여기서 말하는 "전, 중, 후"가 부모 노드라 생각하고 각각 우선순위 높은 순서대로 노드를 타고 내려가면 된다.

 

✅ 풀이

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**8)  # 재귀함수 사용 시 메모리 리미트 방지

n = int(input())

tree = {}
for i in range(n):
    root, left, right = map(str, input().split())  # 루트, 왼쪽자식, 오른쪽 자식
    tree[root] = (left, right)    # 부모노드: (왼쪽 자식노드, 오른쪽 자식노드)

def preorder(v):  # 전위순회
    if v != ".":
        print(v, end="")
        preorder(tree[v][0])  # 재귀적으로 탐색
        preorder(tree[v][1])


def inorder(v):  # 중위순회
    if v != ".":
        inorder(tree[v][0])
        print(v, end="")
        inorder(tree[v][1])


def postorder(v):  # 후위순회
    if v != ".":
        postorder(tree[v][0])
        postorder(tree[v][1])
        print(v, end="")

preorder('A')
print("")
inorder('A')
print("")
postorder('A')

 

오늘의 배운점

- python에서 1<= n and n<=3 이렇게 쓰지 않아도 1<=n<=3 이런 표현이 가능하다는 점을 알 수 있었다.

- for 문 안의 range가 범위가 성립되지 않는다면, for문이 실행되지 않는다.

- 아래와 같이 input 받는 코드를 더 빠르게 할 수 있다.

import sys

input = sys.stdin.readline
n = int(input())

- 트리의 개념, 용어 및 순회 방식에 대해 복습했다.

- Python에서 재귀함수를 쓸 때는 메모리 초과 방지를 위해 sys.setrecursionlimit(10**8) 을 습관적으로 해주자