꾸준히 개발하기

https://www.acmicpc.net/problem/2981

맞왜틀을 외치면서 풀이를 참고했다. 틀렸었다^^

일단 수학적으로 규칙을 좀 찾아야 된다. 

4개의 수를 기준으로 일단 생각해보자.

a = M * a` + r

b = M * b` + r

c = M * c` + r

d = M * d` + r

인 경우 r을 없애보면 다음과 같다.

(a-b) = M * (a`-b`)

(c-d) = M * (c`-d`)

즉 입력받는 숫자들의 차이들의 최대공약수를 구해주면 그게 바로 M이다. 

해당 M의 약수를 1 제외하고 모두 출력해주면 문제가 원하는 답이 된다.

자, 여기서^^... 약수도 그냥 출력하면 안된다. 그냥 출력하다보면 최대 입력 가능한 숫자의 범위(1,000,000,000)가 워낙 커서 시간초과가 난다. 따라서 골드바흐 문제 풀때 for문 1개로 다 처리해줬던 것처럼 다 살펴보지 말자!

예를 들어, 10의 약수는 다음과 같다 (1, 2, 5, 10) 그러면 1*10, 2*5 두 쌍으로 연산을 줄일 수 있다. 즉, 제곱근까지만 살펴본 뒤 그 수로 나눈 몫까지 함께 넣어주면 절반까지만 보면 된다!

혹시 모를 중복을 제거해주기 위해 set 자료형으로 한번 변환한 뒤, 오름차순 출력을 위해 list로 바꾼 뒤 sort하여 출력해주었다. 잊지말고 최종 숫자인 M도 출력해주자~!

코드는 다음과 같다.

import math
import sys

input = sys.stdin.readline

n = int(input())

nums = sorted([int(input()) for _ in range(n)])

gaps = []
for i in range(1, len(nums)):
    gaps.append(abs(nums[i] - nums[i - 1]))

answer = math.gcd(*gaps)

answer_list = []
i = 2

# 약수 구하는 while문 (통과)
while i <= (answer ** (1 / 2)) + 1:
    if answer % i == 0:
        answer_list.append(i)
        if i != (answer // i):
            answer_list.append(answer // i)
    i += 1

# 약수 구하는 for문 (시간초과)
# for i in range(2, int(answer ** 1/2)+1):
#     if answer % i == 0:
#         answer_list.append(i)
#         if i != (answer // i):
#             answer_list.append(answer//i)

for i in sorted(list(set(answer_list))):
    print(i, end=" ")

print(answer)

자,,, 저 코드에서 while문 for문의 차이가 뭔지 바로 보이는가..^^ 바로 거듭제곱과 나눗셈 연산자의 우선순위를 고려하지 않고 짰더니 처참하게 틀린 코드다. 나눗셈보다 거듭제곱이 연산자 우선순위가 높다...! 꼭 괄호를 생활화하자!

그리고 여러 줄을 입력받는 경우 속도가 더 빠른 sys 라이브러리를 사용하도록 코드도 바꿔보았다. 이제 input() 바로 쓰지 말고 sys.stdin.readline 기능을 활용하자

한 일주일 있다가 다시 풀어보자 잊지말고..!^^ 제목에다가 박아둬야겠다. 다시 제대로 푼 날 게시물을 수정해야겠다

소수판별 알고리즘과 시간초과의 늪의 반복이었던 문제... 계속 풀었던 골드바흐 파티션 문제 중 아마 시간이 제일 짧게 주어졌던 문제였던 듯 하다. 물론 그거 고려 안하고 무작정 들박했다가 처참한 시간 초과의 늪에 빠졌다.

처음에는 최대 MAX 값만큼 안 돌리고 테스트케이스 내에서 max값까지만 에라토스테네스의 체를 이용하는 것도 고려해봤는데 여전히 시간초과가 나더라. 생각해보면 max값까지 돌리나 백만까지 돌리나 시간은 크게 차이가 없었다. 그러면 이제 따져볼건 골드바흐 파티션을 구하는 과정에서 불필요한 for문이 있다는 거였다. 아무리 생각해도 for문을 2개를 돌려야될 것 같다고 생각하면서 break문 열심히 넣어줘도 계속 시간초과가 났다.

for문을 1개로 줄여야 통과될 것 같은데, 하면서 보다가 답을 찾아냈다.

-> 굳이 for문을 2개 돌릴 필요 없이, 앞에서부터 보는거 + 뒤에서부터 보는거 는 for문 1개로 충분했다!

흐뭇하게 .. 시간초과의 늪에서 벗어났다. 코드는 다음과 같다.

def getPrimes(MAXCASE):
    erato = [True] * (MAXCASE + 1)
    erato[0], erato[1] = False, False

    for i in range(2, int(MAXCASE ** 0.5) + 1):
        if erato[i] == True:
            for j in range(i + i, MAXCASE + 1, i):
                erato[j] = False
    return erato


erato = getPrimes(1000001)
t = int(input())

for _ in range(t):
    num = int(input())
    cnt = 0
    for i in range(2, num // 2 + 1):
        if erato[i] and erato[num - i]:
            cnt += 1
    print(cnt)

굳이 에라토스테네스의 체를 함수로 선언해준 이유는... 입력받은 숫자 중 max값까지만 소수판별을 하려고 했었다 원래는 ^.T 중첩 for문을 줄여야 시간복잡도를 확 줄일 수 있다고 또다시 몸으로 깨달은 문제였다. 

1초 뒤에 D만큼 움직여야 하고 모든 동생에게 닿을 수 있는 D의 최댓값을 구해야 되는 문제다.

즉, n개의 수 <-> 정수 s 차이의 최대공약수를 구해주면 되는 문제다.

편하게 파이썬의 math.gcd() 함수를 사용했다. gcd() 함수를 자세히 보니 다음과 같이 애스터리스트(*)표시가 있었다.

따라서 거리 차이 리스트를 '*' 표시를 붙여서 함수에 넘겨준 뒤 그 값을 출력하면 되는 문제였다. 파이썬 최고 .. 물론 이 방법이 아니면 유클리드 호제법으로 계속 수를 반복적으로 gcd구해주면 되겠다. 이번에는 파이썬 애스터리스트 문법을 배웠다는 거에 의의를 두고 라이브러리르 쓰겠다 ㅎㅎ

코드는 다음과 같다.

import math

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

data = list(map(int, input().split()))
gaps = []

for v in data:
    gaps.append(abs(s - v))

print(math.gcd(*gaps))

매우 간단한 문제긴 한데 놓쳤던 부분이 있어서 시간 소요가 꽤 있었다. 기억을 위해 기록한다!

조합 공식은 위 그림과 같다. 조합은 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음)

팩토리얼을 구현하는 방법이 여러가지가 있으나 재귀함수 구현에 좀 시간이 걸렸다. 부끄럽다... 일단 재귀함수 ... 후 ... return문이 있어야 함수를 빠져나간다... 재귀 억지로라도 계속 손에 익히자 ㅠㅠ! 재귀로 팩토리얼을 구해도 되고 반복문으로 해도 된다.

그러고 나서 나눗셈을 해줘야 하는데 파이썬에서 '/' 과 '//' 연산자 차이를 이제야 다시 알았다.

'/' : 나눗셈 결과를 float형으로 반환

'//' : 나눗셈 결과를 int형으로 반환

그래서 /로 연산해준뒤 형변환하면 틀렸다고 나온다. 뭐 뒤의 자리를 까고 그러다가 그랬겠지..? 어차피 저 결과는 무조건 정수가 나올 수 밖에 없으니까 int형으로 리턴하는 '//' 연산자를 쓰는게 맞겠다.

코드는 다음과 같다.

n, m = map(int, input().split())
def recur_f(n):
    if n == 1:
        return 1
    else:
        return n * recur_f(n - 1)

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial(n) // ((factorial(m) * factorial(n - m))))

백트래킹 복습 겸 같은 문제 다른 유형을 풀어봤다.

사실 로직 자체는 그냥 N과 M 문제와 똑같다. 다만 여기에서 이제 수열이 오름차순 정렬이 되어서 출력이 되어야 한다는 조건만 하나 붙어 있을 뿐! 그래서 sorted() 함수를 사용해서 정렬해준 뒤 그 결과가 answer에 없으면 넣어주는 코드를 추가했다.

아 그리고 숫자로 이루어진 리스트의 경우 바로 join해주면 int형이라 에러가 난다. 각각의 요소를 str으로 바꿔주는 map함수 잊지말고 적용해주자~!

코드는 다음과 같다.

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


result = []

answer = []


def back():
    if len(result) == m:
        tmp = sorted(result)
        if tmp not in answer:
            answer.append(tmp)
        return

    for i in range(1, n + 1):
        if i not in result:
            result.append(i)
            back()
            result.pop()


back()

for i in answer:
    print(" ".join(map(str, i)))

소수 판별 알고리즘 중 에라토스테네스의 체 방식을 알고 있어야 시간 초과가 안 나는 문제다. 물론 나는 에라토스테네스의 체 방식을 매번 입력받을 때마다 하고 반복문도 많이 써서 시간초과만 우다다 받았다 ^^ 

시간초과를 막는 중요한 포인트가 2개였다...

1. 에라토스테네스의 체를 범위 내의 모든 숫자에 한해서 1번만 돌리기
2. 최대한 반복문 줄이기

최대 입력 가능한 숫자 범위가 1000000이니까 그 안을 일단 다 소수를 판별해버린다! 가능한 소수를 미리 다 계산한 뒤 또 범위 내에서 새로운 리스트를 만들지 말고, 반복문 안에서 True, False값을 체크해서 보기만 해야 시간 초과가 안 난다.

시간초과가 이렇게 머리를 아프게 하는지 간만에 느껴본 문제...^^ 같은 골드바흐 문제는 꽤 금방 시간초과를 잡아서 기가 살아있었는데 1시간 내내 계속 시간 줄이다 보니까 기가 쪼그라들었다... 그래도 풀긴 푼거니까... 어디서 시간초과가 나는지 잘 살펴보는 능력도 정말 중요하구나, 또 느낀다.

파이썬 코드는 다음과 같다.

erato = [True] * 1000001
erato[0], erato[1] = False, False
for i in range(2, 1001):
    if erato[i]:
        for j in range(i + i, 1000001, i):
            erato[j] = False

while True:
    n = int(input())
    wrongFlag = True
    if n == 0:
        break

    for i in range(3, n):
        if erato[i] == True:
            if erato[n - i] == True:
                wrongFlag = False
                print(n, "=", i, "+", n - i)
                break
    if wrongFlag:
        print("Goldbach's conjecture is wrong.")

눈물의 코드... (쓸 필요도 없었고 시간초과만 유발했던 녀석들이다)

# n 미만의 수 중 홀수인 소수 리스트 리턴
def getPrimeNums(n):
    return [i for i in range(n) if erato[i] == True and i % 2 != 0]


def getGoldB(target, nums):
    middleIdx = -1
    for i in range(len(nums)):
        if nums[i] > int(target / 2):
            break
        middleIdx = i

    for i in range(middleIdx + 1):
        for j in range(len(nums) - 1, middleIdx, -1):
            if nums[i] + nums[j] < target:
                break
            if nums[i] + nums[j] == target:
                return [nums[i], nums[j]]
    return False

나름 시간 좀 줄여보겠다고 다른 골드바흐 문제에서 시간초과 잡아줬던, 중간값 구해서 어찌저찌 해봤는데 역시나 시간초과였다. 그냥 T/F 값 판단해서 바로바로 계산하는게 제일 빠르구만

https://www.acmicpc.net/problem/2609

이번 기회에 파이썬에서 사용 가능한 최대공약수(gcd), 최소공배수(lcm) 구하는 방법을 다 정리해보았다.

가장 베이직한 방법

최대공약수 : 숫자 x,y 중 더 작은 숫자부터 1까지 -1 해가며 x%i == 0 and y%i == 0인 숫자 찾기

최소공배수 : 숫자 x,y 중 더 큰 숫자부터 (x*y)까지 +1 해가며 i%x == 0 and i%y == 0인 숫자 찾기

유클리드 호제법

x,y의 gcd는 y와 r의 gcd와 같다. ( x%y = r)

즉 계속해서 x의 자리에 y값을 대입하고, y에는 x%y 값인 r을 대입하면 x%y == 0 인 순간의 y값이 바로 gcd이다.

최소공배수는 x*y를 위에서 구한 gcd로 나눠주면 된다.

라이브러리 활용

이게 사실 제일 편하다..^^ 파이썬의 math 라이브러리는 인자를 심지어 여러개 받을 수 있는 최대공약수, 최소공배수를 구해주는 함수를 제공한다.

math 라이브러리를 import 해주고 math.gcd( 인자, 인자, ... ) math.lcm( 인자, 인자 ,... ) 해주면 된다.

코드는 다음과 같다.

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

# 가장 베이직한 방법
def getGCD_basic(x, y):
    for i in range(min(x, y), 0, -1):
        if x % i == 0 and y % i == 0:
            return i


def getLCM_basic(x, y):
    for i in range(max(x, y), (x * y) + 1):
        if i % x == 0 and i % y == 0:
            return i


# 유클리드 호제법
def getGCD_euclid(x, y):
    while y:
        x, y = y, x % y
    return x


def getLCM_euclid(x, y):
    return (x * y) // getGCD_euclid(x, y)


# 파이썬 라이브러리 활용
import math

print(math.gcd(n, m))
print(math.lcm(n, m))

유클리드 호제법은 정말... 정말 오랜만에 다시 들여다봤다...^^ 수학을 열심히 했던 학생이었는데 이렇게까지 싸그리 까먹을 수 있다니 슬프다. 안 좋은 일이나 빨리 까먹지 이런 수학적 지식만 홀라당 다 까먹어 버렸다.

10.7부터 week1을 달리고 있다.

https://www.acmicpc.net/workbook/view/8997

백준 15649 N과 M (1)

N과 M문제는 자다가도 풀 수 있어야 한다고 해서 순열로 풀었다가 눈물 좍좍 흘리면서 백트래킹을 뿌셨다.

백트래킹은 불필요한 경우를 탐색하지 않는다. 즉 특정 조건에서는 탐색을 그만하고 뒤로 되돌아가는(back) 성질을 가지고 있다. 따라서 DFS로 무작정 들이박으면 시간초과가 나는 상황에 유용하게 쓰이겠다.

숫자 1~N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제이다.

따라서 1) 수열의 길이가 M을 넘으면 안됨 2) 배열 내에 중복 X 두 가지 조건을 만족하는 숫자 뽑기를 진행하면 된다.

ex. N = 4, M = 3

1. 첫번째 숫자로 1,2,3,4 중 가장 작은 숫자인 1을 선택한다. -> for 문으로 순차 증가
2. 두번째 숫자로 2,3,4 중 가장 작은 숫자인 2를 선택한다. -> 선택 과정에서 배열 안에 존재하는지 체크하여 중복 제거
3. 세번째 숫자로 3,4 중 가장 작은 숫자인 3을 선택한다.
4. 수열의 길이가 M(3)이 되었으므로 다시 단계 3로 돌아간다. -> 재귀 탈출
5. 세번째 숫자로 4를 고른다. 
6. 수열의 길이가 M(3)이 되었으므로 단계 2로 돌아간다.
7. 두번째 숫자로 다음 작은 숫자인 3를 선택한다.
8. 세번째 숫자로 2,3,4 중 2를 선택한다. -> 추후 여기에서 다시 숫자를 고를 때 3은 이미 배열안에 존재하므로 X
9. ... 반복

즉 위의 과정을 코드로 구현하면 다음과 같다. 

n, m = map(int, input().split())
result = []

def backTracking():
    # 수열의 길이가 m이면 출력해주고 전단계로 돌아가기 (재귀 탈출)
    if len(result) == m:
        print(" ".join(map(str, result)))  # "구분자".join(리스트)
        return
    # 1 ~ n 까지 체크
    for i in range(1, n + 1):
        # 중복 체크
        if i not in result:
            result.append(i)
            backTracking()
            # return 문으로 돌아온 경우 실행되는 부분
            result.pop()  # n=4, m=3일때 1,2,3이 들어온 경우 3을 없앰으로써 전단계로 돌아감


backTracking()

백트래킹 어렵다. 재귀라서 더 어렵게 느끼는 것 같기도 하고...! 익숙해질때까지 킵고잉이다 정말

출력 관련해서 문자열 다룰 때 자주 쓰이는 함수 join도 짚고 가보자.

"구분자".join(리스트) 형태로 사용하며 join 함수는 매개변수로 들어온 리스트에 있는 요소 하나 하나를 합쳐서 하나의 문자열로 바꿔 반환하는 함수이다. "구분자"를 값과 값 사이에 넣어서 하나의 문자열로 합쳐준다!

파이썬이 문자열 다룰 때 깡패인 언어인 만큼 join함수에도 익숙해지자. 자주 써야된다~!