foreverWon 님의 블로그

1. PROBLEMhttps://www.acmicpc.net/problem/7806문제두 수의 최대공약수는 두 수를 나머지 없이 나눌 수 있는 가장 큰 자연수로 정의한다. 예를 들어, 8과 12의 최대공약수는 GCD(8,12)로 나타내고, 그 값은 4이다. 4는 8과 12를 나눌 수 있는 가장 큰 정수이기 때문이다. (8과 12의 공약수는 1, 2, 4가 있다)자연수의 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. 예를 들어, 5의 팩토리얼은 5!로 나타내고 1*2*3*4*5 = 120이다. (0!은 1로 정한다)두 수 n과 k가 주어졌을 때, n!과 k의 최대공약수를 구하는 프로그램을 작성하시오. 예를 들어, n = 3, k = 10이라면, GCD(n!,k) = GCD(3!,10) = G..

1. 입출력 최소화sys.stdin.readline 사용불필요한 출력 최소화출력 모아서 한 번에 출력2. 시간 복잡도 줄이기O(n^2) -> O(nlog n) 또는 O(n)으로 줄이기중복 연산 제거수학적 공식이나 패턴 활용3. 자료구조 변경리스트 대신 set, dict 사용메모리 낭비 줄이기4. 문제 특화 최적화큰 수 직접 계산 피하기(팩토리얼, 거듭 제곱 등)소인수분해, 모듈러 연산 등 수학적 성질 활용

1. PROBLEM문제양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 출력각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.2. SOLUTION#1.import sys from math import gcdinput = sys.stdin.readlineT = int(input())for _ in range(T): arr = list(map(int, input().split())) N = arr[0] # 배열 크기 nums = arr[1:] # 실제 숫자 리스트 total..

1. PROBLEM문제 설명두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.제한 사항두 수는 1이상 1000000이하의 자연수입니다.입출력 예nmreturn312[3, 12]25[1, 10]자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.https://school.programmers.co.kr/learn/courses/30/lessons/12940 프로그래머스SW개발자를 위한 평가, 교육의 Total So..