728x90
반응형
문제 살펴보기!!
문제 링크 : 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()
코드 설명:
- 입력 처리:
- input = sys.stdin.read().split():
- 모든 입력 데이터를 한 번에 읽고, 공백을 기준으로 나눠 리스트로 저장합니다.
- ptr:
- 입력 리스트에서 현재 읽고 있는 위치를 추적합니다.
- N, A, X:
- N은 A 리스트의 길이를 나타내고, A는 N개의 정수 리스트, X는 서로소를 검사할 대상 정수입니다.
- input = sys.stdin.read().split():
- 서로소 검사 및 합산:
- math.gcd(a, X) == 1:
- 리스트 A의 각 요소 a와 X의 최대공약수를 계산하여, 1이면 a와 X가 서로소라는 것을 의미합니다.
- total과 count:
- 서로소인 수들의 합(total)과 개수(count)를 추적하여 평균 계산에 사용합니다.
- math.gcd(a, X) == 1:
- 평균 계산 및 출력:
- average = total / count if count > 0 else 0:
- 만약 서로소인 수가 하나도 없으면 count가 0이 되어 0으로 나눌 수 없으므로, 그 경우 average를 0으로 처리합니다.
- print("{0:.6f}".format(average)):
- 평균을 소수점 여섯 자리까지 포맷팅하여 출력합니다.
- average = total / count if count > 0 else 0:
풀이 전략:
- 입력 데이터 처리:
- 모든 입력을 한 번에 받아 처리하는 방식입니다. 이렇게 하면 입력 처리가 빠르고 간편해집니다.
- sys.stdin.read().split()을 사용해 공백을 기준으로 입력을 나눕니다.
- 이를 통해, 입력의 첫 번째 요소를 N으로, 그 다음 N개의 요소를 리스트 A로, 마지막 요소를 X로 정의합니다.
- 서로소 조건 검사:
- **서로소(코프라임)**란 두 수의 최대공약수(GCD)가 1인 경우를 의미합니다.
- 이 문제에서는 리스트 A의 각 요소 a와 X의 최대공약수(math.gcd(a, X))를 계산하여, 1이면 서로소로 간주합니다.
- math.gcd 함수는 유클리드 알고리즘을 사용해 효율적으로 최대공약수를 계산할 수 있습니다.
- 조건을 만족하는 요소들의 합과 개수 계산:
- total: X와 서로소인 수들의 합을 저장.
- count: X와 서로소인 수의 개수를 저장.
- 리스트 A를 순회하며, 각 요소 a에 대해 math.gcd(a, X) == 1인 경우 total에 a를 더하고, count를 1 증가시킵니다.
- 이 과정은 시간 복잡도가 O(N)이며, math.gcd는 각 요소에 대해 상수 시간(O(log(min(a, X)))) 내에 처리됩니다.
- 평균 계산:
- 서로소인 수가 하나 이상 존재할 경우, 평균을 total / count로 계산합니다.
- 만약 서로소인 수가 없으면(count == 0), 이를 처리해 0으로 나누는 에러를 방지해야 하므로, average = 0으로 처리합니다.
- 출력:
- 결과값인 평균을 소수점 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)의 시간 복잡도로 효율적임을 설명할 수 있어야 합니다.
728x90
반응형
'알고리즘' 카테고리의 다른 글
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2960 에라토스테네스의 체 편(python) (0) | 2024.10.16 |
---|---|
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-9613 GCD 합 편 (python) (0) | 2024.10.15 |
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-4134 다음 소수 편 (python) (0) | 2024.10.11 |
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-5347 LCM 편 (python) (0) | 2024.10.09 |
백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-3584 가장 가까운 공통 조상 편 (python) (0) | 2024.10.08 |