백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-5347 LCM 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/5347

반응형

---

솔루션 살펴보기!!

import math

def gcd(a, b):
    return b if a == 0 else gcd(b % a, a)

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

def main():
    t = int(input())
    for _ in range(t):
        a, b = map(int, input().split())
        print(lcm(a, b))

if __name__ == "__main__":
    main()

---

코드 풀이 전략

1. 유클리드 호제법을 이용한 GCD 계산: 주어진 두 수의 최대 공약수(GCD)를 구하기 위해 유클리드 호제법을 사용합니다. 유클리드 호제법은 두 수 aaa, bbb에 대해, aaa와 bbb의 GCD는 bbb와 a%ba\%ba%b의 GCD와 같다는 점을 이용한 재귀적 방법입니다.
2. LCM 계산: 두 수의 LCM은 GCD를 이용하여 아래 공식을 통해 구할 수 있습니다.즉, 두 수의 곱을 GCD로 나누면 LCM을 얻을 수 있습니다.
3. 입력 및 출력 처리:
   • 여러 테스트 케이스를 처리하기 위해 입력으로 테스트 케이스의 개수 ttt를 받고, 각 테스트 케이스마다 두 정수 aaa와 bbb가 주어집니다.
   • 각 테스트 케이스에 대해 LCM을 계산하여 결과를 출력합니다.

주요 코드 흐름

1. gcd 함수:
   • 이 함수는 재귀적으로 두 수의 최대 공약수를 유클리드 호제법으로 계산합니다.
   • 기저 조건은 첫 번째 인자가 0이 되었을 때, 두 번째 인자가 최대 공약수가 됩니다.
2. lcm 함수:
   • math.gcd(a, b)는 Python의 내장 함수로 GCD를 계산하며, 이를 사용하여 두 수의 LCM을 구합니다.
   • GCD를 구하고, 두 수의 곱을 그 GCD로 나누어 LCM을 반환합니다.
3. main 함수:
   • 먼저 입력으로 테스트 케이스의 개수 ttt를 받습니다.
   • 각 테스트 케이스마다 두 정수 aaa, bbb를 입력받아 lcm 함수를 이용해 LCM을 계산하고 출력합니다.

---

728x90

코드 면접 준비

위 코드와 관련된 코드 면접에서 알아야 할 주요 개념은 여러 가지 중요한 알고리즘과 데이터 처리 기법에 대한 이해를 요구합니다. 다음은 이 코드와 관련된 주요 개념입니다.

1. 최대 공약수(GCD)와 최소 공배수(LCM)

• **최대 공약수(GCD)**는 두 수의 공통 약수 중 가장 큰 수를 의미하며, **최소 공배수(LCM)**는 두 수의 공통 배수 중 가장 작은 수를 의미합니다.
• GCD와 LCM은 수학에서 중요한 개념일 뿐만 아니라, 알고리즘 문제에서 매우 자주 등장합니다. 두 수의 LCM을 구하기 위해 GCD를 사용하는 공식을 기억하는 것이 중요합니다.
• 유클리드 호제법: GCD를 구하는 가장 효율적인 방법으로, 반복적이거나 재귀적인 방식으로 두 수의 나머지를 계산해나가는 방법입니다. 면접에서 이를 설명할 수 있어야 합니다.

2. 재귀 함수의 이해

• gcd 함수는 재귀 함수로 구현되어 있습니다. 재귀는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법입니다.
• 재귀적 알고리즘의 핵심은 기저 조건과 재귀 호출 조건입니다. 이 코드에서는 a == 0이 기저 조건으로 작동하여 재귀 호출을 종료합니다.
• 면접에서 재귀 함수의 작동 원리와 이를 어떻게 변환해 반복문으로 대체할 수 있는지 설명할 수 있어야 합니다.

3. 복잡도 분석

• 시간 복잡도:
  • 유클리드 호제법의 시간 복잡도는 두 수 aaa와 bbb의 최대 공약수를 구할 때, 각 단계에서 a%ba\%ba%b를 구하는 작업이 이루어지며, 이는 O(log⁡(min⁡(a,b)))O(\log(\min(a, b)))O(log(min(a,b)))의 시간 복잡도를 가집니다. 즉, 매우 효율적인 알고리즘입니다.
  • 전체 코드는 여러 테스트 케이스를 처리하기 위해 반복문을 사용하므로, 입력되는 모든 쌍의 aaa와 bbb에 대해 시간 복잡도는 O(tlog⁡(min⁡(a,b)))O(t \log(\min(a, b)))O(tlog(min(a,b)))가 됩니다.
• 공간 복잡도:
  • 재귀 호출이 이루어질 때 스택 메모리를 사용하지만, GCD를 구하는 재귀 호출의 깊이는 O(log⁡(min⁡(a,b)))O(\log(\min(a, b)))O(log(min(a,b)))이므로 공간 복잡도는 매우 작습니다.

4. 입출력 처리

• 이 코드는 여러 테스트 케이스를 처리하는 구조입니다. 코드 면접에서 입력을 어떻게 받고, 출력하는지를 신경 써야 합니다.
• 입력으로 주어지는 테스트 케이스의 개수만큼 반복하며, 각 케이스에서 두 숫자를 처리하는 방식은 효율적인 문제 해결 방법을 묻는 질문에서 자주 나옵니다. 이를 잘 설명할 수 있어야 합니다.

5. 정수 범위 및 오버플로우 처리

• LCM을 계산할 때, a×ba \times ba×b의 결과가 매우 커질 수 있습니다. Python에서는 기본적으로 큰 수에 대해 자동으로 처리가 되지만, 다른 언어(C, C++, Java 등)에서는 정수 오버플로우를 고려해야 합니다.
• 따라서 면접에서 만약 LCM을 구현할 때 오버플로우를 방지하는 방법에 대해 논의할 수 있으면 좋습니다. 이 문제를 해결하기 위해 GCD를 먼저 계산한 뒤 나누기를 먼저 수행하는 것이 좋은 방법입니다.

6. 알고리즘의 변형 가능성

• 유클리드 호제법을 사용하지 않고 다른 방식으로 GCD를 구하는 방법도 있을 수 있습니다. 예를 들어, 두 수의 약수를 모두 구한 뒤, 그 공통 약수 중 최대값을 찾는 비효율적인 방법을 사용할 수도 있습니다. 그러나 이는 시간 복잡도가 좋지 않기 때문에 면접에서 이러한 비효율적인 방법과 유클리드 호제법의 차이를 설명할 수 있어야 합니다.

7. 모듈화 및 재사용성

• 이 코드는 모듈화가 잘 이루어져 있습니다. gcd와 lcm 함수는 각각 하나의 역할을 담당하며, 이를 이용해 재사용 가능성이 높습니다.
• 면접에서 좋은 코드 구조는 함수 단위로 분리하여 모듈화하는 것이므로, 이러한 코드 작성 습관을 보여주는 것이 좋습니다.