22.08.16 TIL

옵주비·2022년 8월 16일
0

오늘은 10시 넘어서 눈이 떠졌다. 알람이 8시부터 울렸지만, 진짜 일어나기가 너무나도 힘들었다. 주말에 오랜만에 농구 경기를 뛰었더니 갑자기 어제부터 몸살이 났는지... 그래도 오늘은 진짜 공부해야 한다는 생각으로 겨우 일어났다 🥵

기술면접 준비

내일 저녁에 협력사 면접이 있어서, 오늘은 면접 관련하여 공부를 하는 시간을 갖기로 계획했다. 해당 협력사에서는 다음과 같이 반드시 알아야 할 지식을 채용 사이트에 명시해두어서, 이 내용들을 공부하였다. 오늘은 식사 및 휴식을 제외하곤 총 10시간 정도를 공부한 것 같은데, 딱 10번인 CRDT까지 공부해볼 수 있었다. 거의 문제당 평균적으로 1시간씩 투자한 셈이다.

아무래도 CRDT가 무엇이냐고 물었을 때, 단순히 'Conflict-Free-Replicated Data Types의 준말로, 동시 편집 기술의 일종입니다'라고 대답하고 끝낼 건 아니다 보니.... CRDT 이전에 사용된 기술인 OT는 어떤 단점이 있었고, 그 단점을 CRDT에선 어떻게 극복했으며, CRDT가 갖는 단점은 무엇이 있는지 등등을 타고 내려가며 공부하다 보니 시간이 꽤 걸렸다. 면접을 위해서 공부하고 있긴 하지만, 꽤나 흥미로운 내용이 많다. AMD, Intel CPU 비교는 이전에 컴퓨터를 구매할 때 이것저것 찾아보다가 본 적이 있고, BASE64는 최근에 프로젝트 때 QR코드를 암호화할 때 사용했고....... 이런 식으로 이전에 실생활에서 혹은 프로젝트 때 접했던 것들이 많아서인지, 재밌게 공부했다.

내일 면접 전까지 공부해야 할 양이 많아서 일단 내일까진 열심히 공부하고, 이후에 TIL에선 하나씩 정리해보는 시간을 가져볼까 한다. 글로 작성하면서 내 이해가 더 높아질 것 같기도 하고 !

알고리즘

백준 - 분해합

오늘 풀어본 문제는 백준의 분해합이라는 문제이다. 원래는 '문자열 폭발'이라는 문제를 풀 차례였는데, 보니까 2주차 때 정글에서 주간 코딩테스트로 풀었던 문제이다. 풀이가 머릿 속으로 떠오르는 바람에, 그냥 그 다음 문제를 풀었다. 문제를 딱 보고, 일단 브루트포스 방식으로 풀어보았다. 어떤 숫자의 가장 작은 생성자가 존재한다면, 최소한 자기 자신보다는 작아야 한다. 왜냐하면, 자기 자신을 생성자로 가지는 자연수는 존재하지 않기 때문이다. 정수로 생각해보면 0은 가능하겠다만....

어쨌든 1부터 자기자신-1까지의 범위에서 탐색하다가, 만약 그 숫자의 분해합이 N이 된된다면 그 숫자가 바로 가장 작은 생성자라는 논리로 코드를 작성해보았다.

# 최초 풀이
from sys import stdin
input = stdin.readline
N = int(input())

def generator(n):
    for i in range(1,n):
        now = i
        for j in str(now):
            now += int(j)
        if now == n:
            return i
    return 0

print(generator(N))

바로 정답이 나오기는 하는데, 풀이 속도가 1280ms가 나온다. 그래서 더 나은 방법은 없을까 고민하던 중, 탐색의 시작을 반드시 1부터 할 필요가 없다는 생각이 들었다. 가령 6자리의 숫자 N이 999,999이고, 그에 대한 대한 생성자 M을 찾는다면 굳이 1부터 탐색할 필요가 없을 것이다. 딱 봐도 무조건 6자리 숫자가 되어야 할 것이다. 뿐만 아니라, M의 분해합이 N이 되기 위해서는 아무리 작아도 N에서 자릿수 * 9를 뺀 숫자보다 작아질 수 없다. 따라서 999,999 - 9x6 = 999,945 부터 탐색해도 충분하다.

이러한 논리를 바탕으로 개선된 코드를 작성해보았다.

# 개선된 풀이
from sys import stdin
input = stdin.readline
N = input().strip()

def getGenerator(n):
    digits = len(n)
    target = int(n)
    mini = target - 9 * digits
    start = mini if mini > 1 else 1
    for now in range(start,target):
        if now + sum([int(x) for x in str(now)]) == target:
            return now
    return 0

M = getGenerator(N)
print(M)

이렇게 개선한 코드를 제출했더니, 68ms 로 시간이 대폭 단축되었다. 시작하는 숫자만 조정해주었을 뿐인데, 소요시간이 거의 95% 단축된 셈이다. 달다 😋

0개의 댓글