Class 2 (달팽이는 올라가고 싶다 ~ 영화감독 숌)

solved.ac

• 이번 포스팅에서는 수학 및 정렬 문제들과 마지막으로 브루트포스 문제를 하나 풀어보는 시간 가져보겠습니다.

 

2869번 : 달팽이는 올라가고 싶다

2869번: 달팽이는 올라가고 싶다

• 달팽이가 나무 막대를 올라가는 데 걸리는 총 일 수를 계산하는 문제입니다.
• 달팽이는 낮에 'A'만큼 올라가고 'B'만큼 내려가는데, 목표 높이까지 도달하는 마지막 날에는 내려가지 않습니다.
• 따라서, 전체 막대 높이는 'V'에서 마지막 날에 내려가지 않을 'B'를 뺀 뒤, 실제 상승 높이인 'A-B'로 이를 나누어 총 며칠이 걸리는지 계산이 가능합니다.
• 그러나, 계산 결과가 10.1일과 같이 남는 결과가 생기면 안되기 때문에, 이는 math 모듈의 ceil() 함수로 올림 처리하여 문제를 풀어보았습니다.

import math

def calculate_days_to_climb(A, B, V):
  return math.ceil((V-B)/(A-B))

if __name__ == '__main__':
  A, B, V = map(int, input().split())
  print(calculate_days_to_climb(A, B, V))

 

10989번 : 수 정렬하기 3

10989번: 수 정렬하기 3

• N개의 수를 오름차순으로 정렬하는 문제입니다. 그러나, 여느 정렬 문제와는 달리 이 문제는 메모리 제한이 추가되어 있습니다.
• 일반적으로 정렬 문제는 빈 리스트를 선언한 뒤, 이에 for문과 append()를 통해 요소들을 하나씩 추가하여 마지막에 sort() 함수나 sorted()로 정렬하는 것이 대다수일 것입니다.
• 그렇지만 이 문제와 같이 메모리가 극히 제한되어 있는 상황에서는 아래와 같이 공간 복잡도를 고려해서 미리 리스트의 메모리를 할당해주시면 조금이나마 메모리를 효율적으로 사용할 수 있게 됩니다.
• 또한 추가적으로 제가 사용한 방식은 '계수 정렬'입니다. 쉽게 말해 각 요소의 빈도를 계산하고, 이 정보를 이용하여 리스트를 정렬할 수 있는 방식이라고 보시면 됩니다. 코드를 보시면 더욱 이해가 되실 겁니다. 👍🏻

import sys; input=sys.stdin.readline

def counting_sort(N):
    # 계수 정렬
    count = [0] * 10001
    
    for _ in range(N):
        count[int(input())] += 1
        
    for i in range(10001):
        if count[i] != 0:
            for _ in range(count[i]):
                print(i)
            
if __name__ == '__main__':
    N = int(input())
    counting_sort(N)

 

• 아래 링크는 다양한 정렬 관련 알고리즘을 시각화해주는 페이지입니다. 직접 해보시면 직관적으로 정렬을 이해하시는 데 도움을 줄 것입니다. 참고로 계수 정렬은 영어로 Counting Sort라고 불립니다.

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

11050번 : 이항 계수 1

11050번: 이항 계수 1

• 이항 계수를 구하는 문제로 보통 \( \binom{n}{k}=\frac{n!}{k!(n-k)!} \) 공식을 통해 구할 수 있습니다. 이 공식은 n개 중에서 k개를 선택하는 조합의 수라고 보시면 됩니다!
• 위 공식대로 구현해주시면 되는데, 우선 팩토리얼 함수를 재귀적으로 구현한 뒤에 조합 함수까지 차례로 구현해주시면 되겠습니다.

def factorial(N):
    if N == 0 or N == 1:
        return 1
    return N * factorial(N-1)

def combination(N, K):
    return factorial(N) // (factorial(K) * factorial(N-K))

if __name__ == '__main__':
    N, K = map(int, input().split())
    print(combination(N, K))

 

• 그러나 저번 포스팅에서도 살펴보았듯이, math 모듈에서 gcd(), lcm() 함수와 더불어 조합 관련 함수로 comb()도 제공하고 있습니다. 이 comb() 함수를 사용하여 더욱 간결하게 코드를 작성할 수가 있습니다.

import math

if __name__ == '__main__':
    N, K = map(int, input().split())
    print(math.comb(N, K))

 

1181번 : 단어 정렬

1181번: 단어 정렬

• 먼저 주어진 단어들을 길이순으로 정렬하고, 길이가 같으면 사전순으로 정렬하는 문제입니다.
• 우선 중복 처리를 하기 위해 리스트가 아닌 set()으로 초기 선언을 해줍니다.
• 기본적으로 sorted() 함수는 사전순으로 정렬해주는 특성이 있습니다. 그러나 key 값을 추가하고 그 key 값에 lambda 식을 len()으로 주게 된다면 길이에 따라 정렬을 수행할 수 있는 함수로 변하게 됩니다! 코드를 확인해보시죠.

import sys; input=sys.stdin.readline

if __name__ == '__main__':
    N = int(input())
    words = {input().rstrip() for _ in range(N)}
    sorted_words = sorted(words, key=lambda x: (len(x), x))
    
    for word in sorted_words:
        print(word)

 

1436번 : 영화감독 숌

1436번: 영화감독 숌

• 666부터 1씩 증가시키면서 해당 수에 666이 들어가있는 수들을 찾아내는 문제입니다.
• 브루트포스 문제로, 모든 경우를 살펴보며 조건에 만족하면 Title을 반환해주면 되겠습니다.

def find_movie_title(N):
    title = 666
    count = 1
    
    while count < N:
        title += 1
        if '666' in str(title):
            count += 1
    return title

if __name__ == '__main__':
    N = int(input())
    print(find_movie_title(N))