백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-21920 서로소 평균 편 (python)

문제 살펴보기!!

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

반응형

---

솔루션 살펴보기!!

import sys
import math

def main():
    input = sys.stdin.read().split()  # 입력 데이터를 모두 읽고, 공백을 기준으로 나눔
    ptr = 0  # 현재 읽고 있는 위치를 나타내는 포인터

    N = int(input[ptr])  # 정수 N (리스트 A의 길이)
    ptr += 1  # 다음 포인터 위치로 이동

    A = list(map(int, input[ptr:ptr + N]))  # N개의 정수를 리스트 A로 저장
    ptr += N  # N개의 숫자를 읽었으므로 포인터 이동

    X = int(input[ptr])  # 비교할 정수 X

    total = 0  # X와 서로소인 수의 합을 저장할 변수
    count = 0  # X와 서로소인 수의 개수를 저장할 변수

    # 리스트 A의 각 원소에 대해 X와의 최대공약수를 검사
    for a in A:
        if math.gcd(a, X) == 1:  # 최대공약수가 1이면 서로소임
            total += a  # 총합에 추가
            count += 1  # 개수 증가

    # 서로소인 수의 평균 계산
    average = total / count if count > 0 else 0  # 개수가 0일 경우 0으로 처리
    # 평균값을 소수점 6자리까지 출력
    print("{0:.6f}".format(average))

if __name__ == "__main__":
    main()

코드 설명:

1. 입력 처리:
   • input = sys.stdin.read().split():
     • 모든 입력 데이터를 한 번에 읽고, 공백을 기준으로 나눠 리스트로 저장합니다.
   • ptr:
     • 입력 리스트에서 현재 읽고 있는 위치를 추적합니다.
   • N, A, X:
     • N은 A 리스트의 길이를 나타내고, A는 N개의 정수 리스트, X는 서로소를 검사할 대상 정수입니다.
2. 서로소 검사 및 합산:
   • math.gcd(a, X) == 1:
     • 리스트 A의 각 요소 a와 X의 최대공약수를 계산하여, 1이면 a와 X가 서로소라는 것을 의미합니다.
   • total과 count:
     • 서로소인 수들의 합(total)과 개수(count)를 추적하여 평균 계산에 사용합니다.
3. 평균 계산 및 출력:
   • average = total / count if count > 0 else 0:
     • 만약 서로소인 수가 하나도 없으면 count가 0이 되어 0으로 나눌 수 없으므로, 그 경우 average를 0으로 처리합니다.
   • print("{0:.6f}".format(average)):
     • 평균을 소수점 여섯 자리까지 포맷팅하여 출력합니다.

---

풀이 전략:

1. 입력 데이터 처리:
   • 모든 입력을 한 번에 받아 처리하는 방식입니다. 이렇게 하면 입력 처리가 빠르고 간편해집니다.
   • sys.stdin.read().split()을 사용해 공백을 기준으로 입력을 나눕니다.
   • 이를 통해, 입력의 첫 번째 요소를 N으로, 그 다음 N개의 요소를 리스트 A로, 마지막 요소를 X로 정의합니다.
2. 서로소 조건 검사:
   • **서로소(코프라임)**란 두 수의 최대공약수(GCD)가 1인 경우를 의미합니다.
   • 이 문제에서는 리스트 A의 각 요소 a와 X의 최대공약수(math.gcd(a, X))를 계산하여, 1이면 서로소로 간주합니다.
   • math.gcd 함수는 유클리드 알고리즘을 사용해 효율적으로 최대공약수를 계산할 수 있습니다.
3. 조건을 만족하는 요소들의 합과 개수 계산:
   • total: X와 서로소인 수들의 합을 저장.
   • count: X와 서로소인 수의 개수를 저장.
   • 리스트 A를 순회하며, 각 요소 a에 대해 math.gcd(a, X) == 1인 경우 total에 a를 더하고, count를 1 증가시킵니다.
   • 이 과정은 시간 복잡도가 O(N)이며, math.gcd는 각 요소에 대해 상수 시간(O(log(min(a, X)))) 내에 처리됩니다.
4. 평균 계산:
   • 서로소인 수가 하나 이상 존재할 경우, 평균을 total / count로 계산합니다.
   • 만약 서로소인 수가 없으면(count == 0), 이를 처리해 0으로 나누는 에러를 방지해야 하므로, average = 0으로 처리합니다.
5. 출력:
   • 결과값인 평균을 소수점 6자리까지 포맷팅해 출력합니다. 이는 문제에서 요구한 형식에 맞추기 위함입니다.
   • print("{0:.6f}".format(average))를 사용해 소수점 이하 6자리까지 표현합니다.

시간 및 공간 복잡도 분석:

• 시간 복잡도:
  • 리스트 A 순회: O(N)
  • 각 요소에 대해 math.gcd 계산: O(log(min(a, X)))
  • 따라서, 전체 시간 복잡도는 O(N * log(min(a, X)))입니다.
• 공간 복잡도:
  • 입력 크기와 리스트 A 저장에 필요한 공간이 O(N)입니다.
  • 추가로 사용하는 변수(total, count, average)는 상수 공간을 사용하므로, 전체 공간 복잡도는 O(N)입니다.

최적화 요소:

• 이 문제에서 시간 복잡도는 리스트 크기 N에 비례하는 성능을 요구하기 때문에, O(N)으로 처리하는 방법이 최선입니다.
• math.gcd를 사용해 최대공약수를 직접 계산하는 방법도 유효합니다. math.gcd는 유클리드 알고리즘을 기반으로 동작하므로 효율적입니다.

728x90

---

코드 면접시 알아야 할 주요 개념

1. 최대공약수(GCD)와 서로소(Coprime)

• 개념:
  • 두 수의 **최대공약수(GCD, Greatest Common Divisor)**는 두 수가 공통으로 가지는 약수 중 가장 큰 값입니다.
  • 두 수 a와 b의 최대공약수가 1이라면, a와 b는 서로소 관계(Coprime)라고 합니다.
• 코드에서 사용:
  • math.gcd(a, X) == 1을 통해 a와 X가 서로소인지 검사합니다.
• 면접에서 강조할 포인트:
  • 최대공약수 계산에 사용되는 유클리드 알고리즘의 시간 복잡도는 O(log(min(a, X)))이며, 이는 매우 효율적인 방법입니다.
  • 서로소 개념은 수학적 문제뿐 아니라 암호학(예: RSA 암호화)에서도 중요한 역할을 합니다.

2. 입력 처리 및 시간 복잡도 관리

• 개념:
  • 대량의 입력을 효율적으로 처리하는 방법은 코딩 면접에서 중요한 스킬입니다.
  • 특히, 문제에서 주어진 입력이 한 번에 처리될 때는 sys.stdin.read()와 같이 데이터를 한 번에 읽고 나누는 방법이 효율적입니다.
• 코드에서 사용:
  • sys.stdin.read().split()을 사용해 한 번에 입력 데이터를 읽어오고, 이를 리스트로 처리하여 성능을 최적화했습니다.
• 면접에서 강조할 포인트:
  • 입력 크기가 매우 큰 경우, 여러 번의 input() 호출보다는 sys.stdin.read()와 같은 방법이 속도 면에서 우수합니다.
  • 이 코드에서는 N과 A 리스트, X를 처리하기 위해 입력을 단순화했습니다.

3. 리스트 순회와 조건에 따른 누적 합산

• 개념:
  • 리스트를 순회하며 조건을 만족하는 원소들을 찾아 누적하여 합산하고 개수를 세는 방식은 매우 일반적인 패턴입니다.
  • 이 패턴은 필터링을 통해 데이터에서 필요한 값만 추출하는 데 유용합니다.
• 코드에서 사용:
  • for a in A 루프를 통해 리스트 A의 각 요소에 대해 math.gcd 조건을 검사하고, 조건을 만족하는 경우 total과 count를 업데이트합니다.
• 면접에서 강조할 포인트:
  • 이 루프의 시간 복잡도는 O(N)입니다. 즉, 리스트의 길이에 비례하여 성능이 결정되므로 입력 크기에 따라 처리 시간이 선형적으로 증가합니다.
  • 리스트 순회와 조건 검사, 누적 합산은 다양한 문제에서 자주 등장하는 패턴이며, 이를 효율적으로 작성하는 것이 중요합니다.

4. 예외 처리 (Zero Division Handling)

• 개념:
  • 코드에서 발생할 수 있는 예외 상황을 미리 처리하는 것은 중요한 실전 코딩 스킬입니다.
  • 특히 평균을 계산할 때, 분모가 0이 되는 상황을 적절하게 처리해야 합니다.
• 코드에서 사용:
  • average = total / count if count > 0 else 0를 통해 count가 0인 경우를 대비했습니다.
• 면접에서 강조할 포인트:
  • 이러한 예외 처리를 통해 런타임 에러를 방지할 수 있으며, 이 문제에서는 count가 0일 때의 처리를 고려해 안전한 코드를 작성했습니다.
  • 면접관에게 "분모가 0일 경우를 고려하여 예외 처리를 포함했습니다."라는 설명을 덧붙이면 좋습니다.

5. 출력 형식 조정 및 소수점 처리

• 개념:
  • 출력 결과를 소수점 이하 몇 자리까지 맞추라는 문제는 자주 등장합니다. 이는 언어별로 지원하는 포맷팅 기능을 사용해 쉽게 처리할 수 있습니다.
• 코드에서 사용:
  • print("{0:.6f}".format(average))를 사용하여 소수점 6자리까지 맞추어 출력합니다.
• 면접에서 강조할 포인트:
  • 문제의 요구 사항에 맞추어 출력 형식을 조정하는 것은 중요한 부분입니다.
  • 파이썬에서는 문자열 포맷팅을 통해 간단하게 해결할 수 있으며, 면접 중 이 부분을 간결하게 처리하는 방법을 설명하면 좋습니다.

6. 시간 복잡도 및 공간 복잡도 분석

• 개념:
  • 면접에서는 작성한 코드의 시간 복잡도와 공간 복잡도를 분석하는 것이 매우 중요합니다.
  • 시간 복잡도는 프로그램이 실행되는 데 걸리는 시간의 상한을 의미하고, 공간 복잡도는 프로그램이 사용하는 메모리의 양을 의미합니다.
• 코드에서 사용:
  • 리스트 A의 길이가 N일 때, for 루프를 통해 리스트를 한 번 순회하므로 시간 복잡도는 O(N)입니다.
  • 추가로 math.gcd 호출이 각 순회에서 발생하므로, 이는 O(log(min(a, X)))의 시간 복잡도를 가집니다.
  • 전체적인 시간 복잡도: O(N * log(min(a, X))).
  • 공간 복잡도: 입력 크기 O(N)을 고려한 O(N).
• 면접에서 강조할 포인트:
  • 코드의 시간 복잡도와 공간 복잡도를 분석하고 설명할 수 있는 능력은 중요한 평가 기준입니다.
  • 면접관에게 문제에서 요구하는 효율성을 고려하여 이 코드가 O(N)의 시간 복잡도로 효율적임을 설명할 수 있어야 합니다.