척척석사의 코딩기록

 

어디서부터 어떤 말을 꺼내면 좋을지? 싶은 느낌이다.

 

그럴때는 대개 내 경험에 대해서 말을 하면 되는데, 먼저 취직을 해야겠다고 생각했던 것은 23년 가을정도였던 것 같다.

1년하고도 조금 더 시간이 흐른 시점에서 글을 쓰고 있는 것이 웃기다면 웃기겠다.

 

첫 취업활동은 한국/일본을 병행하게 되었다. 한국에서의 취직 활동은 안타깝게도 잘 진행되지 않았고,  일본쪽에서 좀 더 좋은 포지션을 제안 받았다. 한국에서의 포지션은 내가 3월 졸업이다보니 입사시기가 애매하다는 점이 있었고, 이를 위안삼기로 했다.

 

일본에서는 도쿄가스라고 하는 회사에서, DX 인재풀을 충원하기 위한 전형을 새롭게 만들었는데, 해당 포지션에 운이 좋게 붙었다.

총 합격자가 12명이었던 것을 보면, 정말 운이 좋았던 것이 아니었을까 싶다.

 

당시 면접관들의 피드백에 의하면 면접때 평가가 좋았다는 것은 해당 기업의 컬쳐핏과 정말 잘 맞았던 것 같다.

 

이후 4월부터 2달간 계약직으로 잠시 일하면서, 사회생활이라는 것을 느끼게 되었고, 수직적인 상황을 상정했지만 상당히 수평적인 관계였고, 스타트업의 분위기를 느낄 수 있었던 좋은 경험으로 남길 수 있었다.

 

내가 막내였음에도 불구하고 많은 분들이 잘 챙겨주셨고, 부족한 점이 많았지만 보듬어주셨던 부분이 긍정적으로 남았다. 가끔씩 연락을 주고 받으며 안부를 확인하고 있다.

 

하지만 사정이 생기게 되면서 일본으로 가는 것을 단념하게 되었다. 24년의 여름인 7~8월 경이었던 것 같다.

이때부터 한국에서 취업을 본격적으로 준비하게 되었다. 눈에 보이고 있는 모든 공고에 넣게 되었다. 정말 하루 종일 자소서와 포트폴리오에 매진했고, 치열하고 열심히 살았던 적이 없지 않았을까 싶을 정도로 열심히 살았다.

 

그 결과, 9월말 IBM의 Application Developer 포지션으로 채용이 되었다. 구직공고를 확인했던 LinkedIn에는 체험형인턴이라고 작성되어있던 것으로 기억한다. 

 

면접 과정은 정말 매끄러웠고, 실무자, 임원분들까지 포함해서 정말 나이스하다는 인상을 받았다. 실무진 면접 중 마지막에 팀장님이 '힘들어도 이겨낼 수 있겠냐. 처음부터 컴퓨터 공학을 전공한 친구들과 경쟁해서 이길 수 있겠느냐' 라고 말씀하셨던 것이 기억에 남는다. 그분을 결국 회사에서 뵙지는 못했지만, 가장 인상 깊었던 분이었다.

 

인턴을 그만두고 나서, 다음 직장을 정말 열심히 찾았던 것 같다. 사실 인턴으로 있을때도 열심히 찾아봤다.

자소설닷컴, 원티드, 인디스워크, 사람인, 캐치 등 정말 모든 사이트를 뒤지면서 나한테 맞는 것 같은 포지션을 필사적으로 찾아봤다.

 

스타트업의 경우에는 생각보다 엄청나게 서류조차 통과하지 못한 경우가 많았다. 

그래도 보통 면접을 보면 한번에 다 붙었는데, 딱 한군데 떨어진 곳이 있는데. 그곳은 퀀트 포지션이었다.

막연한 자신감으로 지원했었는데, 테크 리더 & 대표 면접에서 떨어지게 되었다. 

높은 스트레스 강도에서도 버틸 수 있어야한다는 점이 안이하게 지원하게 되었던 내 자신을 돌아보게 된 계기가 되었다.

 

아차, 이야기가 조금 돌아가게 되었다. 하여튼, 다양한 곳에 지원을 하게 되다가, 현재 합격하게 된 곳에 지원하게 된 계기는 다음의 3가지였다.

 

훌륭한 처우, 일본계, 업계의 성장 가능성

 

이렇게 3개가 핵심적이었던 것 같다.

일본 생활이 워낙 길었다보니 일본에서의 생활에 염증이 날 수도 있겠지만은, 나는 굉장히 좋은 경험이라고 느꼈기때문에 일본계열에서 일할 수 있다면 좋겠다 생각한것들이 영향을 준 것 같다.

 

내가 생각해왔던 부분을 면접에서도 실제로 많이 물어보셨다. 왜 일본계? 유학 계기? 어떻게 생각하는지? 이런 것들을 확실히 검증하려고하셨던 것 같다.

 

여기까지가 내가 걸어왔던 발자취가 될 것 같다. 순간 순간의 기분 묘사는 필요할 때 추가해야겠다.

오늘은 밀러 - 라빈 , 폴라드 - 로의 하루가 될 것 같은 느낌.

골드 5였던 문제였고, 주의해야할 점이 상당히 많았던 문제.

 

아래는 밀러-라빈 / 폴라드-로때 작성한 코드

import sys
import random
from collections import defaultdict
import math

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def power(x, y, p):
    res = 1
    x = x % p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x * x) % p
    return res

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

def miller_rabin(n, a):
    r = 0
    d = n - 1
    while d % 2 == 0:
        r += 1
        d = d // 2

    x = power(a, d, n)
    if x == 1 or x == n - 1:
        return True

    for i in range(r - 1):
        x = power(x, 2, n)
        if x == n - 1:
            return True
    return False

def is_prime(n):
    alist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    for a in alist:
        if n == a:
            return True
        if not miller_rabin(n, a):
            return False
    return True


def pollardRho(n):
    if is_prime(n):
        return n

    if n == 1:
        return 1

    if n % 2 == 0:
        return 2

    x = random.randrange(2, n)
    y = x
    c = random.randrange(1, n)
    d = 1
    while d == 1:
        x = ((x ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        d = gcd(abs(x - y), n)
        if d == n:
            return pollardRho(n)
    if is_prime(d):
        return d
    else:
        return pollardRho(d)

 

 

 

아래 부분이 해당 알고리즘을 활용한 본 문제의 실제 코드가 되겠다.

 

while True:
    x = int(input())
    if x == 0:
        break

    prime = defaultdict(int)
    y = abs(x)
    while y > 1:
        divisor = pollardRho(y)
        prime[divisor] += 1
        y = y // divisor

    degree = list(set(prime.values()))
    degree_gcd = math.gcd(*degree)

    for deg in degree:
        deg //= degree_gcd

    if x < 0:
        if degree_gcd % 2 == 0:
            while degree_gcd % 2 == 0:
                degree_gcd //= 2
    
    print(degree_gcd)

import sys
import random
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def power(x, y, p):
    res = 1
    x = x % p
    while y > 0:
        if y & 1:
            res = (res * x) % p
        y = y >> 1
        x = (x * x) % p
    return res

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

def miller_rabin(n, a):
    r = 0
    d = n - 1
    while d % 2 == 0:
        r += 1
        d = d // 2

    x = power(a, d, n)
    if x == 1 or x == n - 1:
        return True

    for i in range(r - 1):
        x = power(x, 2, n)
        if x == n - 1:
            return True
    return False


def is_prime(n):
    alist = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    if n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    for a in alist:
        if n == a:
            return True
        if not miller_rabin(n, a):
            return False
    return True


def pollardRho(n):
    if is_prime(n):
        return n
    if n == 1:
        return 1
    if n % 2 == 0:
        return 2
    x = random.randrange(2, n)
    y = x
    c = random.randrange(1, n)
    d = 1
    while d == 1:
        x = ((x ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        y = ((y ** 2 % n) + c + n) % n
        d = gcd(abs(x - y), n)
        if d == n:
            return pollardRho(n)
    if is_prime(d):
        return d
    else:
        return pollardRho(d)

def jud_prime(p): #단순히 소수 측정만 하는 것
    divisor_prime = []
    while p > 1:
        divisor = pollardRho(p)
        divisor_prime.append(divisor)
        p //= divisor

    if len(divisor_prime) == 1: #소수인 경우
        return True
    else:
        return False

def f(a, n, p):
    if n == 1:
        return a % p
    if n % 2 == 0:
        return (f(a, n // 2, p) ** 2) % p
    else:
        return (a * (f(a,n // 2, p) ** 2)) % p

def solution(p, a):
    # p가 소수라면, 문제의 조건을 만족하지 않으므로, no를 반환
    if jud_prime(p) == True:
        return 'no'

    # p가 소수가 아니라면?
    if f(a, p, p) == a:
        return 'yes'
    else:
        return 'no'

while True:
    p, a = map(int,input().split())
    if p == 0 and a == 0:
        break

    print(solution(p, a))

 

 

폴라드- 로 / 밀러 - 라빈을 활용한 소인수분해 및 소수 판정

그리고 분할정복을 활용한 코드

1. 군(Group)과 환(Ring)

1.1 군(Group)

군(Group)은 어떤 집합 G에 단 하나의 이항 연산(⋆)이 정의되어 있고, 다음 네 가지 공리를 만족하는 대수적 구조입니다.

1. 닫힘성
   임의의 두 원소 a, b가 G에 속하면, 연산 결과 a ⋆ b도 G에 속해야 합니다.
   a, b ∈ G &Rightarrow a ⋆ b ∈ G
2. 결합법칙
   임의의 a, b, c ∈ G에 대해, $$(a ⋆ b) ⋆ c = a ⋆ (b ⋆ c).$$
3. 항등원(identity)의 존재
   G 안에는 모든 원소와 연산했을 때 자기 자신을 돌려주는 항등원 e가 존재합니다. $$a ⋆ e = e ⋆ a = a \quad \forall a ∈ G.$$
4. 역원(inverse)의 존재
   각 원소 a에 대해, a와 연산해서 항등원 e를 만들어주는 원소 a^-1이 존재합니다. $$a ⋆ a^{-1} = a^{-1} ⋆ a = e.$$

예시:
정수의 집합 ℤ와 덧셈 연산(+)을 고려하면, 항등원은 0이고, 각 정수 a의 역원은 -a입니다. 따라서 (ℤ, +)는 군(Group)이 됩니다.

---

1.2 환(Ring)

환(Ring)은 두 가지 이항 연산(일반적으로 덧셈과 곱셈)을 가진 대수 구조로서, 다음 성질들을 만족해야 합니다.

1. 덧셈에 대해 아벨 군
   
   • 덧셈은 닫혀 있습니다 (a + b가 항상 집합 내 원소).
   • 결합법칙: $$(a + b) + c = a + (b + c).$$
   • 교환법칙: $$a + b = b + a.$$
   • 항등원(보통 0)과 각 원소의 덧셈 역원(음수)이 존재합니다.
2. 곱셈에 대한 조건
   
   • 곱셈 연산도 닫혀 있습니다 (ab가 항상 집합 내 원소).
   • 항등원(일반적으로 1)이 존재합니다.
   • 결합법칙: $$(ab)c = a(bc).$$
   • 분배법칙: $$a(b+c) = ab + ac,\quad (a+b)c = ac + bc.$$

주의: 곱셈에 대한 역원(나눗셈)이 모든 0이 아닌 원소에 대해 존재할 필요는 없습니다. 만약 모든 0이 아닌 원소가 곱셈 역원을 가지면 나눗셈 환(Division Ring), 그리고 곱셈이 가환이라면 체(Field), 비가환이면 스큐 필드(Skew Field)라고 합니다.

예시:
정수 ℤ, 유리수 ℚ, 실수 ℝ, 복소수 ℂ 등은 모두 덧셈과 곱셈에 대해 환(Ring)의 성질을 만족합니다. 그중 ℤ는 모든 원소가 곱셈 역원을 갖지 못하므로(예: 2의 역원은 정수가 아님) 체가 아니지만, ℚ, ℝ, ℂ 등은 0이 아닌 모든 원소에 곱셈 역원이 존재하므로 체(Field)입니다.

---

2. 사원수(Quaternion)

2.1 사원수의 정의

사원수(Quaternion)는 다음과 같은 형태로 표현되는 4차원 수입니다.

$$ q = a + b\,i + c\,j + d\,k \quad (a, b, c, d ∈ \mathbb{R}). $$

여기서 i, j, k는 서로 독립적인 허수 단위로서 다음 곱셈 규칙을 가집니다.

$$ i^2 = j^2 = k^2 = ijk = -1, $$ $$ ij = k, \quad ji = -k,\quad jk = i,\quad kj = -i,\quad ki = j,\quad ik = -j. $$

이러한 사원수 전체의 집합을 ℍ라고 하면, 덧셈과 곱셈에 대해 환(Ring)의 성질을 만족하기 때문에 이를 “사원수환(Quaternion Ring)”이라고 부릅니다.

---

2.2 사원수에서의 기본 연산

사원수 $$ q_1 = a_1 + b_1\,i + c_1\,j + d_1\,k,\quad q_2 = a_2 + b_2\,i + c_2\,j + d_2\,k $$ 가 주어졌을 때, 주요 연산들은 다음과 같습니다.

1. 덧셈
   $$q_1 + q_2 = (a_1 + a_2) \;+\; (b_1 + b_2)\,i \;+\; (c_1 + c_2)\,j \;+\; (d_1 + d_2)\,k.$$
2. 곱셈 (비가환성)
   $$q_1 q_2 = (a_1 a_2 - b_1 b_2 - c_1 c_2 - d_1 d_2) + (a_1 b_2 + b_1 a_2 + c_1 d_2 - d_1 c_2)\,i$$ $$\quad + (a_1 c_2 - b_1 d_2 + c_1 a_2 + d_1 b_2)\,j + (a_1 d_2 + b_1 c_2 - c_1 b_2 + d_1 a_2)\,k.$$

   일반적으로 $$q_1 q_2 \neq q_2 q_1$$ 가 성립하므로, 사원수 곱셈은 교환법칙이 성립하지 않는 예시입니다.

3. 노름(Norm), 켤레(Conjugate)
   

   노름(Norm)은

   $$\|q\| = \sqrt{a^2 + b^2 + c^2 + d^2},$$

   켤레(Conjugate)는

   $$\bar{q} = a - b\,i - c\,j - d\,k.$$

   만약 $$\|q\| \neq 0$$ 이라면(즉, $$q \neq 0$$), $$q$$의 곱셈에 대한 역원은 다음과 같이 주어집니다.

   $$q^{-1} = \frac{\bar{q}}{\|q\|^2}.$$

   이는 $$q \bar{q} = \bar{q} q = \|q\|^2$$ 이기 때문인데, 실제로 $$q \bar{q}$$ 를 전개하면 $$q \bar{q} = a^2 + b^2 + c^2 + d^2 = \|q\|^2$$ 임을 확인할 수 있습니다.

---

3. 사원수군(Quaternion Group) \(Q_8\)

사원수의 특정 부분집합으로, 원소가 8개 뿐인 Quaternion Group \(Q_8 = \{\pm 1,\;\pm i,\;\pm j,\;\pm k\}\) 가 있습니다.

이 집합은 곱셈 연산(·) 하나만 정의해도 군(Group)이 되는데, 다음 관계들을 만족하기 때문입니다.

$$ i^2 = j^2 = k^2 = ijk = -1. $$

---

4. 행렬 표현과 기하학적 해석

4.1 3차원 회전과의 관계

길이가 1인 단위 사원수 \(q\)를 $$ q = \cos\bigl(\tfrac{\theta}{2}\bigr) \;+\; \sin\bigl(\tfrac{\theta}{2}\bigr)\,(u_x\,i + u_y\,j + u_z\,k) $$ 라 하겠습니다. 여기서 \(\theta\)는 회전각, \((u_x, u_y, u_z)\)는 단위벡터(회전축)입니다. 즉, \(u_x^2 + u_y^2 + u_z^2 = 1\).

(1) 3차원 벡터 v를 순수 사원수(실수부가 0)로 생각하면, 단위 사원수 q와 그 켤레 \(\bar{q} = \cos(\tfrac{\theta}{2}) - \sin(\tfrac{\theta}{2})(u_x\,i + u_y\,j + u_z\,k)\)를 사용하여 아래처럼 v를 회전시킬 수 있습니다.

$$ \mathbf{v}' = q \,\mathbf{v}\,\bar{q}. $$

(2) 이렇게 하나의 회전을 두 번, 세 번, 총 \(n\) 번 반복 적용하면,

$$ \mathbf{v}^{(n)} = q^n \,\mathbf{v}\,(\bar{q})^n, $$

이 됩니다. 실제로 q를 $$\cos(\tfrac{\theta}{2}) + \sin(\tfrac{\theta}{2})(u_x\,i + u_y\,j + u_z\,k)$$ 라고 하면, $$q^n$$ 은 $$ q^n = \cos\bigl(\tfrac{n\theta}{2}\bigr) \;+\; \sin\bigl(\tfrac{n\theta}{2}\bigr)\,(u_x\,i + u_y\,j + u_z\,k), $$ 꼴로 표현되어, 축은 동일하고 회전각만 \(n\theta\)가 됨을 알 수 있습니다.

---

4.2 행렬 표현

단위 사원수 \(q = w + x\,i + y\,j + z\,k\)에 해당하는 3차원 회전은, 아래와 같은 3×3 정규직교행렬 \(R(q)\)로도 나타낼 수 있습니다.

$$ R(q) = \begin{pmatrix} 1 - 2(y^2 + z^2) & 2(xy - wz) & 2(xz + wy) \\ 2(xy + wz) & 1 - 2(x^2 + z^2) & 2(yz - wx) \\ 2(xz - wy) & 2(yz + wx) & 1 - 2(x^2 + y^2) \end{pmatrix}, $$

여기서 \(w = \cos\bigl(\tfrac{\theta}{2}\bigr)\), \((x,y,z) = \sin\bigl(\tfrac{\theta}{2}\bigr)\,(u_x,u_y,u_z)\)입니다. 따라서 3차원 벡터 \(\mathbf{v}\)의 회전 결과는 \(\mathbf{v}' = R(q)\,\mathbf{v}\)로도 동일하게 표현됩니다.

---

 

면접을 보러 다녀오는 길에 상당히 여러가지 생각이 들었던 하루였고, 글로 남기고 싶어서.

점심은 미성옥. 설렁탕 특 14,000원

날도 추워졌고, 갑자기 국물이 떠올라서 설렁탕을 찾던 도중 면접장 주변에 괜찮다는 집이 있어서 바로 가봤다.

풍미도 좋았고, 김치도 마음에 들었다. 생각보다 소면이 많아서 양이 아주 부족하지는 않았던 것 같다.

원래 국물이 있어도 끝까지 다 안 마시는 편이지만 간만에 국물까지 거의 다 먹었던 국이었다.

명동 주변 갈 일이 있다면 한번씩은 가지 않을까 싶은 느낌?

 

 

 

면접이 끝나고, 망원역에 가게 되었는데 우연치 않게 들렀던 구스커피앤바 (coffee & bar)

이곳의 시그니처라고 불리는 음료수였는데, 놀랍게도 위스키향이 나는 아인슈페너

논알콜이라는게 핵심

 

한번 딱 마시고, 어 뭐야 이거. 싶었던 것이 ㅎㅎ 내가 술을 시켰던가? 싶은 착각까지 들 정도였네요

가격은 8,000원으로 조금 있는 편이지만, 굉장히 독특하고 재밌는 경험을 할 수 있습니다.

그냥 원두 자체도 좋은 것 같았어요. 

 

 

 

 

매장 내부는 굉장히 차분한 느낌

여성분들이 많이 오시고, 조용조용하게 이야기 나누기에 적절한 환경 같아 보입니다.

 

 

 

마지막으로 오늘의 하이라이트인 망원의 신상 라멘집, 류진 입니다.

12월 26일, 처음으로 카레시루나시 라멘을 개시하는 날이었습니다.

제가 도착했을때는 이미 2개의 그룹이 있어서 '한 텀에 겨우겨우 들어가겠는데?' 싶었는데

5시 반에 다시 와보니 제 앞의 2그룹이 안오셨더라고요. 그래서 제일 먼저 들어갈 수 있었습니다.

새로 생긴 곳이라고 해서 궁금하기도 했었고, 또 사장님이 일본인이라고 하셔서, 더욱이 가보고 싶었습니다.

 

주문했던 카레시루나시 (12,000원 + 1,500원 = 13,500원)

 

한정메뉴 첫 개시입니다. 운이 좋게 제가 12/26부터 시작하는 한정메뉴의 첫 시식자가 되었습니다.

 

숙주, 마늘, 세아부라, 마요네즈 등의 양을 물어보십니다. 

저는 숙주 조금, 마늘이랑 세아부라 많이로 부탁드렸습니다.

 

훌륭했습니다. 카레와의 밸런스도 좋고, 기존 활용하시던 소스와의 궁합이 잘 어울립니다.

챠슈 또한 목살을 사용해서 그런지 뻑뻑하지도 않고 정말 맛있었어요.

보통 시루나시보다는 좀 더 퓨전계열로 즐기기에 너무나 좋았습니다.

숙주 또한 너무 익혀지지 않아 아삭거림이 살아있었고, 면 또한 잘 익혀져있으며 기존 소스가 잘 배어있습니다.

 

 

처음에 주문하는데, 카레시루나시를 어떻게 주문해야하는지 잘 몰라서 일본어로 여쭤보는데

시루나시 (12,000원)을 주문하고 치즈 (1,500원)을 카레로 부탁드린다고 스태프한테 말해달라고 하시더라고요.

이런 부분을 일본어로 얘기했었는데요, 자리에 앉아보니 사장님께서 어떻게 일본어 그렇게 잘하시냐고 물어보셨습니다.

그래서 대학교랑 대학원 후쿠오카에서 다녔고, 6년정도 일본 살았다 말씀드렸었네요. 

 

그러면서 오늘 처음 오시는거 아니냐. 첫 한정메뉴 주문 감사드린다. 

이런 말씀을 하시더라고요. 이런 부분에서 좋게 느껴졌어요. 

 

저는 후쿠오카에서만 6년을 살았다. 혹시 출신이 어디시냐 여쭤봤더니 오사카라고 하시더라고요.

오사카가 한국보다는 따뜻하지 않냐 라고 전달드리는 과정에서 앞쪽 부분이 들리지 않으셨는지,

뜨겁다고 말씀하시더라고요.

 

그래서 제가 다시 말씀드리니까 ㅋㅋㅋ 오사카가 아니라 자기 말씀하는줄 알았다며.

라멘에 대한 열정 하나만큼은 일본에서 가장 뜨거운 사람이구나 싶었습니다.

 

먼 타지 생활을 겪어봤던 사람으로, 외국 생활이 결코 쉬운것이 아님에도 불구하고 도전하는 자세가 너무나 멋있습니다.

항상 응원하고, 다음에는 가장 맛있다고 말씀하신 오리지널 먹으러 가보고 싶습니다.

 

 

주어진 문제는 위와 같다.

이 문제를 풀면서 중요한 점이 2가지 있는데, 이것을 생각해보자.

 

첫번째로, $R(n,m)$을 계산함에 있어 $if m > n$ then $R(n,m) = 0$ 이라는 점이겠다.

두번째로, 문제에서 주어진 식인 $R(n+1, m+1) = (R(n,m) \cdot R(n,m +1) + 1) / R(n-1, m)$

 

여기서, $R(n,m)$가 사실은 다음과 같은 모양을 하고 있다고 가정해보자. 

$$ R(n, m) = (n - m) \cdot m + 1$$

 

이러한 식을 세웠다면 먼저 검증해야할 것이 있다. 소위 말하는 수학적 귀납법이 되겠다.

i) 초기 조건에서 성립하는지?

ii) 임의의 상황에서도 성립하는지?

 

초기조건인 $n = 0, m = 0$에서는 자명하게 성립하는 것을 알 수 있다.

그렇다면 임의의 $n, m$에 대해서는 어떨까?

 

여기서는 일반성을 잃지 않고, $n-1 >= m$ 이라고 가정하자.  만약, $n - 1 < m$이라는 것은, $n < m + 1$ 꼴인데,

첫번째 조건에서 $m > n$이라면 $R(n,m) = 0$이라는 것을 알 수 있고, 해당 되는 케이스는 $n = m$ 뿐인데, 이건 1로 자명하기 때문.

 

그렇다면, 식을 실제로 검증해보자. $$\frac{1 + R(n,m) \cdot R(n,m +1)}{R(n-1, m)}  = \frac{1 + ((n - m)m + 1) \cdot ((n-m-1) \cdot (m+1) + 1)} {(n-1-m)\cdot m  + 1} $$

 

여기서, 분모인 $(n-1-m)\cdot m  + 1$를 $X$로 치환하게 되면, 분자의 부분은 다음과 같이 나타낼 수 있다

\[
\begin{aligned}
    &((n - m)m + 1) \cdot ((n-m-1) \cdot (m+1) + 1) \\
    &= (X + m)(X + n - m - 1) + 1 \\
    &= X^2 + (n - 1)X + m(n-m-1) + 1 \\
    &= X^2 + (n - 1)X + (X-1) + 1 \\
    &= X^2 + nX.
\end{aligned}
\]

그러므로, $$\frac{X^2 + nX}{X} = X + n =n(m+1) -m (m+1) + 1 = (n-m) (m+1) + 1 = R(n+1, m+1)$$

이렇게 나타내어지는 것을 알 수 있겠다.

 

위의 과정을 통해, 수학적 귀납법이 허용된다는 것을 알았으니, 해답 코드는 다음과 같이 간단하게 쓰일 수 있겠다.

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range (T):
    n, m = map(int,input().split())
    print((n-m) * m + 1)

 

 

 

 

 

 

 

도중까지 읽다가, 아 이거 위상정렬이군

 

하고 있었는데, 가능하면 쉬운 문제부터 풀어야한다는 점이 상당히 핵심적

그럼에도 불구하고 어렵지 않은 이유는, 

 

topological sorting에서 indegree가 0이 되는 것들을 우선적으로 넣고, 그 이후에 node를 방문하며 하나씩 간선을 제거해나가는 (indegree를 1씩 줄이는 방식)을 취하는 것인데 이 부분에서 Indegree가 0 이 되는 것을 heap에다가 넣어두면 되겠다.

 

Heap은 항상 최솟값을 뱉어내기 때문에, 3번 조건인 쉬운 문제부터 풀어야 한다를 풀기 최적화되어있는 알고리즘이겠다.

반대로, 어려운 문제부터 풀어야한다라면, 최대힙 (즉, 마이너스를 붙여서 저장하는 것)부터 활용하면 되겠다.

 

아래는 답안 코드

import sys
import heapq

N, M = map(int,input().split())
indegree = [0 for _ in range (N+1)]
path = [[] for _ in range (N+1)]

for _ in range (M):
    a,b = map(int,input().split())
    indegree[b] += 1
    path[a].append(b)
    
prior_solving = []
for i in range (1, N+1):
    if indegree[i] == 0:
        heapq.heappush(prior_solving,i)

answer = []
while prior_solving:
    x = heapq.heappop(prior_solving)
    answer.append(x)
    
    for y in path[x]:
        indegree[y] -= 1
        if indegree[y] == 0:
            heapq.heappush(prior_solving,y)
            
print(*answer)

 

이전에 풀었던 예쁜 수 였던가? 굉장히 유사했던 것 같다.

결국은 Dynamic Programming이 얼만큼 이전 정보를 유용하게 활용할 것인지? 를 묻는 상황이므로,

이 부분을 잘 컨트롤 할 필요가 있겠다.

 

 

이 문제 같은 경우에는, 2가지 스텝으로 나눠서 풀면 된다.

 

첫번째로, 사면체로서 가능한 패턴인 숫자들을 구해주는 것이 되겠다.

이를 구하기 위해서는 각 step의 삼각형을 구성하기에는 몇개의 대포알이 필요한지 알아낼 필요가 있겠다.

 

이는 생각보다 쉽다. $n$번째 단의 삼각형을 만드는 것에 필요한 대포알은 $n(n + 1) / 2$개이라는 것을 쉽게 알 수 있다.

1, 3, 6, 10... 이런 Typical한 패턴을 주는 것에 유의하자.

 

그렇다면 사면체는 어떠한가? 1~n번째 단을 만드는데 필요한 대포알을 전부 합치면 되겠다.

수식으로 나타내게 된다면, 

$$\sum_{i =1}^n \frac{n(n + 1)}{2}  = \frac{1}{2} \sum_{i=1}^n n(n+1) = \frac{1}{2} (\sum_{i=1}^n n^2  + \sum_{i=1}^n n)$$

$$ = \frac{n(n+1)(2n +1)} {12} + \frac{n(n+1)}{4} = \frac{n(n + 1)(2n+1) + 3n(n+1)}{12} $$

$$= \frac{2n(n+1)(n+2)}{12} = \frac{n(n+1)(n+2)}{6}$$

이런 식으로 나올수는 있겠지만 .... 사실은 프로그래밍 안에서는 그냥 리스트 2개 만들어서 하는 편이 훨씬 낫다 ...

 

두번째 단계는, 결국 최소 step을 구하고자 하는 상황이므로, dp 리스트를 만들어 두고, 하나씩 추가하는 방식으로 진행하면 좋겠다.

비슷한 유형으로, 예쁜수가 있겠다. (https://pjw9777.tistory.com/102)

 

import sys
input = sys.stdin.readline

N = int(input())
bullet, bullet_sum = [1], [1]
cnt = 2

while bullet_sum[-1] <= N:
    bullet.append((cnt * (cnt + 1)) // 2)
    bullet_sum.append(bullet_sum[-1] + bullet[-1])
    cnt += 1

dp = [N for _ in range (0, N + 1)]

for i in range (0, len(bullet_sum)-1):
    dp[bullet_sum[i]] = 1
    for j in range (bullet_sum[i] + 1, N + 1):
        dp[j] = min(dp[j - bullet_sum[i]] + 1, dp[j])

print(dp[-1])

 

 

 

 

처음에는 그냥 python으로 풀었는데, 이후 Pypy로 푸니 어마무시하게 줄어들은 것을 확인할 수 있었다.

대신 메모리는 많이 잡아 먹었지만 .....