[백준] 수학_15650, 1037, 2981, 1789, 2407, 15663, 15657, 2824

N과 M (2)

• 코드

n, m = map(int, input().split())

answer = []

def dfs(idx, temp):
    if len(temp) == m:
        answer.append(temp)
        return

    for i in range(idx, n):  
        dfs(i+1,temp+[i+1])

dfs(0, [])
for i in answer:
    print(" ".join(str(s) for s in i))

• 풀이를 생각해낸 과정
  • 재귀 함수를 이용하여 조합 구현
  • n = 4, m=3이라고 할 때,
    • step1) dfs(0,[]) → dfs(1,[1]) → dfs(2,[1,2]) → dfs(3, [1,2,3])
    • step2) m값과 temp 의 길이가 같아지면 즉 원하는 개수 모두 뽑으면 해당 탐색 끝, dfs(2,[1,2]) 에서 dfs(4,[1,2,4]) 호출
    • step3) dfs(2,[1,2]) 탐색 끝, dfs(1,[1])에서 dfs(1,[1,3]) 호출 후 해당 과정 반복
    • step4) dfs(0,[])에서 dfs(2,[2]) 호출 후 해당 과정 반복
    • point) temp의 길이와 m 값이 같다면 answer 리스트에 해당 리스트 값 추가

약수

• 코드

n = int(input())
temp = list(map(int,input().split()))

print(min(temp)*max(temp))

• 풀이를 생각해낸 과정
  • 32비트 부호있는 정수 = int
  • 약수의 곱은 대칭성을 띄기 때문에 입력 받은 진짜 약수에서 가장 작은 수와 가장 큰 수를 곱해서 계산한다.
• 시간복잡도 계산
  • min, max - O(N)

검문

• 코드

import math

def Gcd(a,b):
    if a < b:
        a, b = b, a
    while a > 0:
        b, a = a, b%a
    return b

n = int(input())
arr = [int(input()) for i in range(n)]
arr.sort()

new = [] # arr[i+1] - arr[i] 값 저장
result = [] # 최대공약수의 약수 값 저장

for i in range(len(arr)-1):
    new.append(arr[i+1]-arr[i])

gcd = new[0]

for i in range(1,len(new)):
    gcd = Gcd(new[i],gcd)

for i in range(2,int(math.sqrt(gcd))+1):
    if gcd % i == 0:
        result.append(i)
        result.append(gcd//i)
        
result.append(gcd) #2부터 확인하여 1과 대응되는 자기 자신 추가
result = sorted(list(set(result))) # 중복 제거 ex) 4의 약수 1,2,4 면 2가 중복해서 들어간다.
print(" ".join(map(str,result))) # print(*result)

• 풀이를 생각해낸 과정
  • 반복문을 돌면서 나누어지는지 확인하는 경우로 생각 → 시간 초과
  • 수학 공식을 활용하여 풀기
  A = M * a + RC = M * c + RA - B = M ( a - b )이런 식이 나온다.M은 A-B, B-C의 공약수이다 즉 최대공약수를 구하면 된다.
• 즉,
• B - C = M ( b - c )
• 여기서 R을 제거하면
• B = M * b + R
• 시간복잡도 계산
  • O(N)

수들의 합

• 코드

import math
n = int(input())

s = 0 # 1~k 의 합을 저장하는 변수
k = 1
while s <= n:
    s += k
    if s > n:
        break
    k += 1
print(k-1)

• 풀이를 생각해낸 과정
  • 1부터 1씩 증가시키면서 n을 만들어가는 것이 최대 개수를 보장한다.
• 시간복잡도 계산
  • O(n), O(루트N)

  O(n)제곱근 시간 알고리즘(Square root algorithm)은 O(log n) 보다 느리지만, O(n)보다는 빠르다.
  
  

  • 1~ n 까지의 합이 n*(n+1) / 2 이므로 while 문의 반복이 최대 2n의 제곱근 만큼 반복된다.

조합

• 코드

n,m = map(int,input().split())

dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i-1] * i

print(dp[n] // (dp[m] * dp[n-m]))

• 풀이를 생각해낸 과정
  • 팩토리얼을 dp로 푸는 방법을 이용
    • 재귀함수를 사용하면 중복 연산 발생
  • 정수 형으로 바꿔서 출력했는데 오답 처리, 그대로 출력하는 것이 정답
• 시간복잡도 계산
  • O(N)

N과 M (9)

• 시간 초과
• 코드

n, m = map(int, input().split())
num = list(map(int,input().split()))

num.sort()

result = []
def choice(i, temp):
    if len(temp) == m:
        if temp not in result:
            print(" ".join(map(str,temp)))
            
        result.append(temp)
        return
    for j in range(n):
        if j!= i:
            choice(j,temp+[num[j]])

for i in range(len(num)):
    choice(i,[num[i]])

• 풀이를 생각해낸 과정
  1. 중복 상관없이 담고 출력할 때 제외하기
  2. 담을 때 중복 고려해서 담기
• 시간복잡도 계산

N과 M (8)

• 코드

n, m = map(int, input().split())
arr = list(map(int,input().split()))

arr.sort()

def sequence(n, temp):
    if len(temp) == m:
        print(' '.join(map(str,temp)))
        return
    
    for i in range(n,len(arr)): #인덱스로 접근하여 중복 방지, n : 탐색 중인 인덱스
        sequence(i,temp+[arr[i]])
        

sequence(0,[])
#(0,[]) -> (0,[1])  
#                 -> (0,[1,1]) -> (0,[1,7]) -> (0,[1,8]) ->(0,[1,9])
#       -> (1,[]) -> (1,[7]) 
#                              -> (1,[7,7]) -> (1,[7,8])

• 풀이를 생각해낸 과정
  • 백트래킹, sequence 함수에서 자신부터 탐색을 시작하게 설정하여 자기 자신을 포함시키고 중복 수열을 방지하도록 구현
• 시간복잡도 계산
  • O(N)

최대공약수

• 코드

#14:21 ~ 14:37
n = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))

def mul(temp):
    k = 1
    for i in temp:
        k*=i
    return k

def gcd(a,b):
    if a<b:
        a, b = b, a
    while a>0:
        b, a = a, b%a
    return b

result = str(gcd(mul(a),mul(b)))
if len(result) >9:
    print(result[-9:])
else:
    print(result)

• 풀이를 생각해낸 과정
  • 곱셈 과정 함수화, 유클리드 호제법 함수화
  • 최대 공약수 결과 문자열로 바꿔 9자리가 넘어가는 경우 슬라이싱
• 시간복잡도 계산
  • O(N)