첫 날인 만큼 크게 어려운 문제들을 풀진 않았고, Python 기초를 복습할 수 있는 문제들 및 수학문제들 위주로 풀어 보았다.

자료구조와 알고리즘

• 자료구조: 데이터를 효율적으로 저장, 접근, 수정할 수 있도록 설계된 구조
• 알고리즘: 어떠한 문제를 해결하기 위해 정해 놓은 일련의 절차

파이썬 문제 풀이 유의점

빠른 입출력

• 백준에서 파이썬으로 문제풀이 시 input()은 시간 초과가 뜰 수 있음
• 더 빠른 sys.stdin.readline() 사용하기
  • 보통 매번 치기 번거로우므로, input을 재정의해서 사용

import sys
input = sys.stdin.readline
a = list(map(int, input().split()))
# 입력: 1 2 3
# 결과: a = [1, 2, 3]

import sys
input = sys.stdin.readline
n = int(input()) # 입력: 2
a = [list(map(int, input().split())) for _ in range(n)]

# 입력:
# 1 3 5
# 2 4 6
# 결과: a = [[1, 3, 5], [2, 4, 6]]

• 단, sys.stdin.readline()은 입력 끝에 개행 문자 \n을 포함
• 앞선 예시에선 int 함수 사용 시 \n이 무시되므로 문제없지만, 문자열 처리 시 문제가 발생할 수 있음
• .strip()을 써서 \n을 제거

import sys
input = sys.stdin.readline
s = input()             # 입력: lgtwins
print(s == "lgtwins")   # s = "lgtwins\n" 이므로 False
s = s.strip()
print(s == "lgtwins")   # s = "lgtwins" 이므로 True

• sys.stdin.readline()으로도 시간 초과가 뜨면 언어를 PyPy로 바꿔서 시도해 보기
  • C로 만들어진 기존 Python과 다르게, Python으로 Python을 만든 언어
  • 어지간한 경우 PyPy가 Python보다 빠름

최대 재귀 깊이 설정

• 파이썬의 기본 최대 재귀 허용 깊이는 1,000
  • 무한 재귀로 인한 스택 오버플로우를 방지하기 위한 설정
• 아래 코드로 수동으로 늘릴 수 있음, 일반적으로 10^6 정도가 적당

import sys
sys.setrecursionlimit(10**6)

• PyPy에서는 Python과 달리 정해진 재귀 제한이 없음
  • 단 10만 단위 정도 들어가면 스택 오버플로가 발생함
  • 재귀 문제에서는 PyPy 말고 Python 사용을 권장

10진수 <-> n진수 간 변환

n진수를 10진수로

print(int('0b110', 2))    # 2진수 110 -> 10진수 6
print(int('0o75', 8))     # 8진수 75 -> 10진수 61
print(int('0x3F', 16))    # 16진수 3F -> 10진수 63

10진수를 n진수로

# 해당 함수들은 string을 반환함에 유의
print(bin(6))             # 0b110
print(oct(8))             # 0o75
print(hex(63))            # 0x3f

실제 계산 방법

• 10진수 -> $n$진수: n으로 계속 나누며 구한 나머지를 역순으로 나열

def ten_to_n(x, n):
    # 정수값 x를 n진수로 변환
    digits = []
    digit_char = "0123456789ABCDEF"
    
    while x > 0:
        # x를 n으로 나누었을 때 몫과 나머지 반환
        x, r = divmod(x, n)
        digits.append(digit_char[r])
        
    digits.reverse()
    result = "".join(digits)
    return result

print(ten_to_n(59, 2))  # 111011
print(ten_to_n(59, 8))  # 73
print(ten_to_n(59, 16)) # 38

• $n$진수 -> 10진수: 각 자리수에 n의 제곱수를 곱해 더함

def n_to_ten(x, n):
    # n진수 값 x를 10진수로 변환
    result = 0
    digit_dict = {'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15}
    
    for idx, digit in enumerate(x[::-1]):
        if digit in digit_dict:
            digit = digit_dict[digit]
        result += (n ** idx) * int(digit)
        
    return result

print(n_to_ten("111011", 2))  # 59
print(n_to_ten("73", 8))  # 59
print(n_to_ten("3B", 16)) # 59

에라토스테네스의 체

• $2$부터 $N$까지 범위의 수 중 소수를 구하는 알고리즘
  내용이 길어져 별도 포스트로 대체

문제풀이

4344. 평균은 넘겠지

백준 / Bronze 1 / 4344. 평균은 넘겠지

• 파이썬 문자열 포맷팅으로 소수점 자리 수를 설정할 때, 자동으로 반올림이 됨
• 즉 round 함수를 사용하지 않고도 반올림 처리 가능

ratio = 66.666666
print(f"{ratio:.3f}%")          # 66.667%
print(f"{round(ratio, 3)}%")    # 66.667%

2577. 숫자의 개수

백준 / Bronze 2 / 2577. 숫자의 개수

• collections.Counter를 이용해 문자열, 리스트 등 iterable 객체의 원소별 개수를 나타내는 딕셔너리를 만들 수 있음
  • key: 원소, value: 해당 원소의 개수

a = Counter("123456654456")
print(a)
# Counter({'4': 3, '5': 3, '6': 3, '1': 1, '2': 1, '3': 1})

• 사용법은 일반적인 딕셔너리와 동일
• 없는 키를 인덱싱할 시, 에러가 아니라 0을 리턴

print(a['4'])               # 3
print(a['2'])               # 1
print(a['0'])               # 없는 키: 0
print(a['ㄹㅇㄹㅇㄹㅇ'])     # 없는 키: 0

• .most_common() 메서드로 가장 많이 등장한 항목을 정렬해서 볼 수 있음
• (원소, 개수) 쌍의 리스트를 개수의 내림차순으로 반환

print(a.most_common())
# [('4', 3), ('5', 3), ('6', 3), ('1', 1), ('2', 1), ('3', 1)]

print(a.most_common(2)) # 상위 2개만
# [('4', 3), ('5', 3)]

2628. 종이자르기

풀이가 길어져 별도 포스트로 대체

9020. 골드바흐의 추측

풀이가 길어져 별도 포스트로 대체

2869. 달팽이는 올라가고 싶다

풀이가 길어져 별도 포스트로 대체