99클럽 코테 스터디 36일차 TIL (적어도 대부분의 배수) - 백준

오늘은 99클럽 코테 스터디 36일차입니다. 벌써 8월의 마지막 주차이네요..

개강 시즌이 되겠군요.. (백수지만,,) 이번주도 화이팅입니다!

오늘 문제는 완전 탐색 (브루트포스) 유형의 문제입니다. 한 번 살펴볼까요?

---

1. 오늘의 학습 키워드

• 배수
• 브루트포스 알고리즘
• 완전 탐색

---

2. 문제: 적어도 대부분의 배수 (1145번)

• 단계: 🥉브롲느 1티어
• 알고리즘 분류: 브루트포스 알고리즘
• 출처: https://www.acmicpc.net/problem/1145

적어도 대부분의 배수 성공

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	14052	8798	7527	63.481%

문제

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

예제 입력 1 복사

30 42 70 35 90

예제 출력 1 복사

210

예제 입력 2 복사

1 2 3 4 5

예제 출력 2 복사

4

예제 입력 3 복사

30 45 23 26 56

예제 출력 3 복사

1170

예제 입력 4 복사

3 14 15 92 65

예제 출력 4 복사

195

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 브루트포스 알고리즘

---

3. 나의 풀이

문제 분석

이 문제는 주어진 다섯 개의 자연수 중 적어도 세 개로 나누어지는 가장 작은 수, 즉 "적어도 대부분의 배수"를 찾는 것입니다.

이를 위해서는 다음과 같은 절차를 따를 수 있습니다:

1. 주어진 다섯 개의 자연수 중 3개, 4개, 또는 5개의 조합을 고려합니다.
2. 각 조합에 대해 그 수들의 최소공배수를 계산합니다.
3. 계산된 최소공배수들 중 가장 작은 값을 찾습니다.

이 방법을 적용하기 위해선 최소 공배수를 구하고, 조합을 구할수 있는 itertools 모듈의 combinations 메서드를 사용할 수 있습니다.

하지만, 이 문제의 알고리즘 유형은 브루트포스 알고리즘이기 때문에 첫 접근은 완전 탐색 알고리즘 기반으로 진행했습니다.

문제 풀이

브루트포스 알고리즘을 사용하여 문제를 해결하려면 가능한 모든 수에 대해 배수 여부를 검사하는 방식으로 접근할 수 있습니다. 이 방법은 주어진 다섯 개의 자연수 중 적어도 세 개 이상의 수로 나누어지는 가장 작은 수를 찾는 방식으로 작동합니다.

브루트포스 알고리즘의 동작 방식:

1. 주어진 수들 중 최소값부터 시작하여 1씩 증가시키며 검사합니다.
2. 현재 수가 주어진 다섯 개의 수 중 세 개 이상의 수로 나누어지는지를 확인합니다.
3. 조건을 만족하는 가장 작은 수를 찾으면 그 수를 출력합니다.

이 방법은 직관적이며 간단하지만, 효율성은 떨어집니다. 그래도 문제의 크기가 크지 않기 때문에 가능한 접근 방식입니다.

아래는 이 알고리즘을 구현한 코드입니다:

import sys
integer_list = list(map(int,sys.stdin.readline().split()))

i = min(integer_list)
while True:
    cnt = 0
    
    for n in integer_list:
        if i % n == 0:
            cnt += 1
    if cnt >= 3:
        print(i)
        break
    
    i += 1

코드 설명:

• i를 주어진 수들 중 가장 작은 값부터 시작하여 1씩 증가시킵니다.
• 현재의 i가 주어진 수들 중 적어도 세 개의 수로 나누어지는지를 확인합니다. cnt 변수를 사용하여 나누어지는 수의 개수를 셉니다.
• cnt가 3 이상이면 그 값을 출력하고 반복을 종료합니다.
• 조건을 만족하지 않으면 i를 1 증가시키고 다시 검사합니다.

이 코드의 시간 복잡도는 어떻게 될까요?

보통, 완전 탐색 (브루트포스)알고리즘의 시간복잡도는 자료구조의 크기로 나옵니다.

코드 분석:

1. min(integer_list):
   • 이 부분은 리스트에서 최소값을 찾기 때문에 시간 복잡도는 O(len(integer_list))입니다. 하지만 이 연산은 코드 전체의 시간 복잡도에 큰 영향을 미치지 않습니다.
2. while True: 루프:
   • 이 루프는 조건을 만족하는 값을 찾을 때까지 계속 반복합니다. 가장 중요한 부분은 이 루프가 몇 번 실행되는지입니다.
3. for n in integer_list::
   • 이 내부 루프는 integer_list의 각 요소에 대해 i % n == 0인지 확인합니다. 이 부분의 시간 복잡도는 O(len(integer_list))입니다.

전체 시간 복잡도:

• 최악의 경우, while True: 루프는 매우 많은 반복을 수행할 수 있습니다. 예를 들어, i가 최소값부터 시작해서 조건을 만족하는 i를 찾을 때까지 계속 증가합니다.
• 만약 i가 최대 k까지 증가해야 한다면, while 루프의 실행 횟수는 k번입니다. 각 반복에서 리스트를 한 번 순회하므로 각 반복의 시간 복잡도는 O(len(integer_list))입니다.

따라서, 전체 시간 복잡도는 O(k * len(integer_list))입니다.

k는 조건을 만족하는 최소값을 찾기 위해 i가 증가하는 횟수를 나타냅니다. 이 값은 입력된 숫자들의 크기와 분포에 따라 달라질 수 있습니다.

결론적으로, 이 코드의 시간 복잡도는 O(len(integer_list))가 아니라 O(k * len(integer_list))입니다. 여기서 k는 찾으려는 최소값이 얼마나 빨리 발견되는지에 따라 달라질 수 있습니다.

---

4. 다른 풀이

이번 풀이는 앞서 말씀 드렸던, 주어진 다섯 개의 자연수 중 3개, 4개, 또는 5개의 조합을 고려하고, 각 조합에 대해 그 수들의 최소공배수를 계산하는 방법을 사용하려고 합니다. 이 방법을 사용하기 위해 저희는 파이썬의 itertools의 조합 메서드를 사용할 수 있습니다.

---

그럼 itertools에 대해 먼저 알아볼까요?

itertools 모듈은 파이썬의 표준 라이브러리 중 하나로, 반복(iteration)과 관련된 여러 유용한 도구들을 제공합니다. 이 모듈은 특히 순열, 조합, 무한 반복기 등과 같은 고급 반복 작업을 쉽게 처리할 수 있는 함수를 포함하고 있습니다.

itertools 모듈은 주로 다음과 같은 기능들을 제공합니다:

1. 순열과 조합

• itertools.permutations(iterable, r=None): 주어진 이터러블에서 가능한 모든 순열을 생성합니다. r을 지정하면 그 길이의 순열을 생성합니다.
• itertools.combinations(iterable, r): 주어진 이터러블에서 가능한 조합을 생성합니다. 조합의 길이는 r입니다.

예시:

import itertools

data = ['A', 'B', 'C']

# 순열 (순서가 중요)
permutations = list(itertools.permutations(data, 2))
print("Permutations:", permutations)
# 출력: Permutations: [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

# 조합 (순서가 중요하지 않음)
combinations = list(itertools.combinations(data, 2))
print("Combinations:", combinations)
# 출력: Combinations: [('A', 'B'), ('A', 'C'), ('B', 'C')]

2. 반복기 생성

• itertools.cycle(iterable): 주어진 이터러블을 무한히 반복하는 반복기를 생성합니다.
• itertools.repeat(object, times=None): 특정 객체를 주어진 횟수만큼 반복하거나 무한히 반복하는 반복기를 생성합니다.

예시:

import itertools

# cycle을 사용하여 무한 반복
counter = 0
for item in itertools.cycle(['A', 'B', 'C']):
    print(item, end=" ")
    counter += 1
    if counter == 9:
        break
# 출력: A B C A B C A B C

# repeat를 사용하여 반복
repeated = list(itertools.repeat(10, 5))
print("\\nRepeated:", repeated)
# 출력: Repeated: [10, 10, 10, 10, 10]

3. 누적 합과 곱

• itertools.accumulate(iterable, func=operator.add): 이터러블의 요소에 대해 누적 합을 계산합니다. func 인자를 통해 합 이외의 다른 이진 함수를 적용할 수도 있습니다.

예시:

import itertools
import operator

numbers = [1, 2, 3, 4, 5]

# 기본 누적 합 (add)
accumulated_sum = list(itertools.accumulate(numbers))
print("Accumulated Sum:", accumulated_sum)
# 출력: Accumulated Sum: [1, 3, 6, 10, 15]

# 누적 곱 (multiply)
accumulated_product = list(itertools.accumulate(numbers, operator.mul))
print("Accumulated Product:", accumulated_product)
# 출력: Accumulated Product: [1, 2, 6, 24, 120]

4. Cartesian Product (카르테시안 곱)

• itertools.product(*iterables, repeat=1): 주어진 이터러블들 간의 카르테시안 곱을 계산합니다. 이 곱은 입력된 모든 이터러블의 가능한 조합을 생성합니다.

예시:

import itertools

list1 = ['A', 'B']
list2 = [1, 2]

product_result = list(itertools.product(list1, list2))
print("Product:", product_result)
# 출력: Product: [('A', 1), ('A', 2), ('B', 1), ('B', 2)]

5. 체인 연결

• itertools.chain(*iterables): 여러 이터러블을 하나의 이터러블처럼 연결하여 순회합니다.

예시:

import itertools

list1 = [1, 2, 3]
list2 = ['A', 'B', 'C']

chained = list(itertools.chain(list1, list2))
print("Chained:", chained)
# 출력: Chained: [1, 2, 3, 'A', 'B', 'C']

itertools 모듈은 반복과 관련된 다양한 고급 기능을 제공하여, 복잡한 반복 작업을 간단하고 효율적으로 수행할 수 있게 해줍니다. 이를 통해 코드를 더 간결하게 작성할 수 있으며, 성능 향상에도 기여할 수 있습니다. 다양한 문제에서 itertools의 함수를 활용하면 매우 유용할 것입니다.

사실, 순열과 조합만 잘 알면 될 것 같습니다!!

---

다시 문제로 돌아가서,

이 문제는 주어진 다섯 개의 자연수 중 적어도 세 개로 나누어지는 가장 작은 수, 즉 "적어도 대부분의 배수"를 찾는 것입니다.

이를 위해서는 다음과 같은 절차를 따를 수 있습니다:

1. 주어진 다섯 개의 자연수 중 3개, 4개, 또는 5개의 조합을 고려합니다.
2. 각 조합에 대해 그 수들의 최소공배수를 계산합니다.
3. 계산된 최소공배수들 중 가장 작은 값을 찾습니다.

파이썬에서는 math 모듈의 gcd 함수를 이용해 두 수의 최대공약수를 구할 수 있고, 이를 통해 두 수의 최소공배수를 구할 수 있습니다. 이를 확장하여 여러 수의 최소공배수도 구할 수 있습니다.

구현은 다음과 같습니다:

import math
from itertools import combinations
import sys

def lcm(a, b):
    return abs(a * b) // math.gcd(a, b)

def lcm_multiple(numbers):
    lcm_value = numbers[0]
    for num in numbers[1:]:
        lcm_value = lcm(lcm_value, num)
    return lcm_value

numbers = list(map(int,sys.stdin.readline().split()))

min_lcm = float('inf')

# 3개, 4개, 5개의 조합을 계산
for r in range(3, 6):
    for comb in combinations(numbers, r):
        min_lcm = min(min_lcm, lcm_multiple(comb))

print(min_lcm)

코드 설명:

1. lcm 함수는 두 수의 최소공배수를 계산합니다.
2. lcm_multiple 함수는 주어진 숫자들의 리스트에 대해 최소공배수를 계산합니다.
3. 입력된 다섯 개의 숫자에 대해 3개, 4개, 5개씩의 조합을 생성하고, 각 조합에 대해 최소공배수를 계산하여 가장 작은 값을 찾습니다.

이 코드로 주어진 입력에 대해 "적어도 대부분의 배수"를 정확히 찾을 수 있습니다.

예제 입력을 이용하여 테스트해보면:

# 입력: 30 42 70 35 90
# 출력: 210

이와 같이 출력됩니다.

이 코드의 시간 복잡도를 분석하기 위해서는 각 단계에서 수행되는 연산의 복잡도를 계산해야 합니다.

코드 분석

1. 조합 계산 (combinations(numbers, r)):
   • 이 부분에서는 itertools.combinations 함수를 사용하여 주어진 리스트 numbers의 요소들 중 r개를 선택하는 모든 조합을 생성합니다.
   • r의 값이 3, 4, 5로 변하므로, 각각의 경우에 대해 조합의 수는 다음과 같습니다:
     • $C(n, 3), \ C(n, 4),\ C(n, 5)$
     • 여기서 $C(n, r)$은 조합의 수를 의미하며, 공식은 $C(n, r) = \frac{n!}{r!(n-r)!}$입니다.
   • 총 조합의 수는 $C(n, 3) + C(n, 4) + C(n, 5)$가 됩니다.
2. 최소공배수 계산 (lcm_multiple(comb)):
   • 이 함수는 주어진 조합 comb에 대해 최소공배수를 계산합니다.
   • lcm 함수의 시간 복잡도는 두 수의 최대공약수를 계산하는 데 사용되는 유클리드 알고리즘의 시간 복잡도인 O(log(min(a, b)))입니다. 따라서 lcm_multiple 함수는 조합의 길이만큼 반복하며, 각 반복마다 두 수의 lcm을 계산합니다. 결과적으로, lcm_multiple의 시간 복잡도는 O(r * log(M))이 됩니다.
   • 여기서 M은 리스트 numbers에 있는 수 중 가장 작은 두 수의 값입니다.
3. 전체 시간 복잡도:
   • 각 r에 대해 조합을 생성하는 데 O(C(n, r))의 시간이 걸리고, 각 조합에 대해 O(r * log(M))의 시간이 걸립니다.
   • 이를 모두 고려한 전체 시간 복잡도는 다음과 같습니다:

$O\left(\sum_{r=3}^{5} \left(C(n, r) \times r \times \log(M)\right)\right)$

이는 다음과 같이 세부적으로 나눌 수 있습니다:

• $O(C(n, 3) \times 3 \times \log(M))$
• $O(C(n, 4) \times 4 \times \log(M))$
• $O(C(n, 5) \times 5 \times \log(M))$

최종 시간 복잡도

정리하면, 이 코드의 전체 시간 복잡도는:

$O\left(\left(C(n, 3) \times 3 + C(n, 4) \times 4 + C(n, 5) \times 5\right) \times \log(M)\right) \simeq O(log(M))$

n은 numbers의 길이 (여기서는 5), M은 리스트에서 최소한의 값입니다. 이 식은 n의 값이 5로 고정되어 있기 때문에 상수 시간 내에서 해결됩니다. 일반적으로, 이 코드의 시간 복잡도는 다섯 개의 수에 대해 브루트포스 방식으로 조합을 생성하고, 각 조합에 대해 최소공배수를 계산하는 과정을 포함하므로, 다소 비효율적일 수 있지만 문제의 크기가 작기 때문에 실행 가능합니다.

이렇기 때문에 코드 속도는 두번째 방법이 더 빠른것을 확인할 수 있습니다.

브루트포스 result

조합, 최소공배수 result

---

마무리

이번 문제는 완전 탐색 유형의 문제입니다. 주어지는 데이터 수가 5개로 적었기 때문에 완전 탐색이 가능한 문제였습니다. 또한 itertools의 combinations 모듈과 최공배수를 사용하면 조금더 시간적으로 효율적인 방법을 구상할 수 있는 문제였습니다.

전체 코드는 이 링크를 타고 가시면 시간 비교도 하실수 있습니다.

도움이 되셨다면 좋아요, 팔로우 부탁드립니다.

읽어주셔서 감사합니다!