Class 2 (직각삼각형 ~ 블랙잭)

solved.ac

• Class 1에 해당하는 문제들을 모두 살펴보았습니다. 전반적으로 난이도 면에서는 그리 어렵지 않으셨을거라 생각합니다.
• Class 2부터는 본격적으로 브루트포스, 이분 탐색, 에라토스테네스의 체를 이용한 소수 판정, 그리고 다양한 자료 구조 등을 익힐 수 있게 됩니다.
• solved ac에서 제공되는 난이도에 따르면 Class 2에는 브론즈 3 문제부터 실버 2까지의 문제가 수록되어 있습니다.
• 이번 포스팅부터는 Github Gist를 활용하여 코드 스니펫을 삽입할 예정입니다. 또한 비교적 쉬운 난이도의 문제들을 다뤄보도록 하겠습니다.

 

4153번 : 직각삼각형

4153번: 직각삼각형

• 특정 삼각형에서 세 변의 길이가 주어지면 이 삼각형이 직각삼각형인지를 판단하는 문제입니다.
• 우선 세 변의 길이가 입력으로 주어졌을 때 이를 정렬한 뒤, 피타고라스의 정리를 활용하여 직각삼각형 여부를 판단하면 되겠습니다.

def check_right_triangle(a, b, c):
    sides = sorted([a, b, c])
    return 'right' if sides[0] ** 2 + sides[1] ** 2 == sides[2] ** 2 else 'wrong'

if __name__ == '__main__':
    while True:
        a, b, c = map(int, input().split())
        if a == b == c == 0:
            break
        else:
            print(check_right_triangle(a, b, c))

 

1978번 : 소수 찾기

1978번: 소수 찾기

• 주어진 수 중에서 소수의 개수를 찾는 문제입니다.
• 심화 과정이지만 시간 복잡도 측면에서 뛰어난 효율을 보이는 '에라토스테네스의 체' 알고리즘을 사용하였습니다.
• '에라토스테네스의 체' 알고리즘의 기본적인 로직은 다음과 같습니다.

1. 모든 숫자의 소수 여부를 저장하는 리스트와 소수들을 저장할 리스트 생성 (처음에는 0과 1을 제외한 모든 수를 소수라고 가정)
2. 범위를 순회하며 i 가 소수라면 i 를 소수 리스트에 저장
3. 나머지 i 의 배수들은 소수가 아니라고 표시 (True → False)

• 위 로직을 바탕으로 코드를 구현하고 최종적으로 소수인 것들의 숫자들을 카운트해주는 형식으로 풀었습니다.

def sieve_of_eratosthenes(max_num):
    number = [False, False] + [True] * (max_num - 1)
    primes = []

    for i in range(2, max_num + 1):
        if number[i]:
            primes.append(i)
            for j in range(i*2, max_num + 1, i):
                number[j] = False
    return primes

if __name__ == '__main__':
    N = int(input())
    num_list = list(map(int, input().split()))

    max_num = max(num_list)
    primes = sieve_of_eratosthenes(max_num)

    print(sum(1 for num in num_list if num in primes))

알면 도움되는 코딩 테스트 유형: 12) #Primality_Test

• 위 글을 통해서도 '에라토스테네스의 체' 알고리즘에 대하여 더 자세히 알 수 있습니다. 위 작동 방식과는 다를 수 있으나 로직은 같으니 참고하시면 도움이 될 것 같습니다. :)
• 아래는 간단한 시각화입니다. 특정 숫자 목록을 입력하면 그 중에서 소수를 판정해주는 방식으로 진행됩니다. ,(comma)로 구분하여 입력해주셔야 동작합니다!

2231번 : 분해합

2231번: 분해합

• 위 문제는 분해합을 구하는 문제는 아니고, 입력되는 수의 분해합을 만드는 생성자를 찾는 문제입니다.
• 생성자를 찾는 로직은 다음과 같습니다.

1. 자연수를 입력
2. 해당 자연수까지의 모든 숫자를 확인 (이 때 각 숫자는 i)
3. 각 i 에 대하여 i 의 자릿수를 모두 sum
4. 그 후 i 와 sum 을 더하여 이 수가 입력된 자연수와 같다면 i 를 반환 (i 에 해당하는 수가 생성자)

• 위 로직은 완전 탐색이라고도 불리는 '브루트포스' 알고리즘을 적용시킨 것으로, 모든 경우를 탐색해야할 때 유용하게 사용됩니다.

def find_constructor(target):
    for i in range(target):
        temp = sum(map(int, str(i)))
        if i + temp == target:
            return i
    return 0

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

 

2292번 : 벌집

2292번: 벌집

• 주어진 방 번호에 도달하기 위한 최소 개수의 방을 출력하는 문제입니다.
• 벌집을 한 겹 한 겹씩 해쳐나가야 합니다. 현재 겹에서의 방 번호의 최댓값을 코드에서 'step'으로 표기하였습니다. 
• 이 'step'은 이전 단계 최대 번호에 '지금까지 지나온 겹 수 * 6'을 더한 값입니다.
• 따라서 이 식을 코드로 나타내면 다음과 같습니다.

def find_minimum_steps_to_room(N):
    step = 1	# 현재 겹에서 방 번호 최댓값
    count = 1	# 지금까지 지나온 겹 수

    while N > step:
        step += count * 6
        count += 1

    return count

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

 

2798번 : 블랙잭

2798번: 블랙잭

• 여러 수가 주어질 때, 이 중 3개를 합하여 M과 가장 가깝게 되는 수를 출력하는 문제입니다.
• 이와 같은 문제도 '브루트포스' 알고리즘을 활용하여 풀 수 있습니다.
• 저는 3중 반복문으로 모든 경우의 합을 찾아내면서 M보다는 작거나 같은 최댓값을 찾는 방식으로 진행하였습니다.

def find_max_sum_under_limit(n, m, cards):
    max_sum = 0

    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                current_sum = cards[i] + cards[j] + cards[k]
                if current_sum <= m:
                    max_sum = max(max_sum, current_sum)

    return max_sum

n, m = map(int, input().split())
cards = list(map(int, input().split()))
print(find_max_sum_under_limit(n, m, cards))