척척석사의 코딩기록

 

이제 입사 후 거의 한달이 지나가는 것 같다. 다음주로서 딱 입사 한달차

 

적다면 적고, 많다면 많은 일들이 일어났다. 채용을 진행하면서 여러 사람들을 만나보거나, 계약서 정리 등 정말 이전과 다른 커리어패스를 걷고 있음에 신기함을 느끼면서도, 업무에 있어 즐거움도 많이 느끼는 것 같다.

 

새로운 일이라고 하는 것이 어려운 것도 있겠지만 하나씩 해결해나가다 보면 언젠가는 멋지게 일을 끝내버린 내 모습을 *생각해보면 열심히 하게 되는 것 같다. 

*사실 생각해보지는 않으나, 일이 다 끝난 뒤에 뒤돌아보면 뿌듯했다.

 

얼마 전, 정규직 채용의 최종 면접이 있었는데, 모 지원자가 내게 "덕분에 마지막까지 긴장 안하고 잘 했던 것 같습니다" 라는 말을 하며 귀가 했던 것이 기억에 남는다. 사실 긴장을 풀어주려고 엄청난 노력을 하지는 않았다. 그저 오는 이들에게 웃는 얼굴로 마주치려고 했고, 회사의 좋은 이미지를 제공하고자 했다.

 

불과 몇달전까지 나 역시도 지원자였고, 간절함이 있었기 때문에 상당히 복잡한 심정으로 그들을 마주했던 것 같다. **나보다 한참 나이가 많은 이들이 깍듯이 대하는 모습이라던지, 그러한 상황이 익숙하지도 않았거니와 부담스러웠기 때문이다. 
**하지만 그것이 매너라는 것을 알게 되니 자연스럽게 기분이 풀렸다. 나 역시도 연하인분들에게 존댓말을 하며 매너와 좋은 스탠스를 유지하려고 하다보니, 이것 또한 자연스러운 것이구나라고 생각하게된다.

 

그리고 나는 어쩌면 그들에게 내 과거의 모습을 투영해서 봤던 것일지도 모르겠다. 정장을 입고 쭈뼛쭈뼛 들어오는 모습, 화장실에서 넥타이를 열심히 다시 매는 모습 등 과거의 내가 보였을지도. 그래도 많은 면접을 거치면서 여유라는 것이 생겼을지는 모르겠지만, 그럼에도 불구하고 면접은 항상 긴장됐던 것 같다. 새로운 사람을 만나는 자리이기도 하니, 더욱 신경이 쓰일 수 밖에.

 

면접자들에게 나는 어떠한 모습으로 보였을까? 동그란 안경을 쓴 리셉션? 웃고 있는 사람? 아니면 바쁘게 움직이고 있는 막내? 

 

어떠한 시선으로 그들이 나를 보고 있었을지는 모르겠지만, 결국 좋은 인상으로 남았으면 한다. 그들이 회사를 판단하기 이전에 나를 판단하게 된다. 나 역시 그들을 인상으로 평가할 수 있겠지만, 나 역시 평가대상이 될 수 있다는 것을 항상 유념해야할 것 같다. 특히 정보화시대, 정보는 항상 기록되기 때문에, 조심해서 나쁠 것이 없다는 스탠스가 되어버리는 것 같은.

 

직무 특성 상 사내 사람들을 많이 만나는 것 뿐만 아니라 사외 사람들도 많이 마주치고 있다보니, 둥글게 둥글게 대하게 되는 것 같다. 결국은 좋은 방식으로. 마무리하는 것이 좋지 않을까 라는 생각을 하게 된다. 어쩌면 그 사람이 두번 다시 못 볼 사람이더라도. 물론 한편으로는 그들을 진심으로 응원했다. 결국 같이 일할 사람들을 뽑는 과정이기도 하니, 그 사람들을 앞으로 계속 볼 예정이니까. 잘 되었으면 좋겠다고 생각했다. 

 

세상 살이가 좁다고들 한다. 결국 어떻게든 건너건너 알게 되고, 다시 돌게 된다고들 한다. 

6단계 법칙 이론이라는 것도 있지 않는가. 결국 6명을 거치면 모든 이들을 다 알 수 있다는 이론.

모든 이들에게 친절하게 대한다는 것이 얼마나 어려운 것인지 알고 있다. 내 기분이나 표현을 절제하는 것이 필수적이겠다.

가끔 내 감정이 표정에 나와버리긴 하지만, 잘 숨기려고 노력해야겠지. 

 

하여튼, 회사 일은 그랬었다. 앞으로도 잘 성장하길. 아무리 힘들어도 잘 극복할 수 있길. 항상 그래왔던 것처럼.

 

잠깐 여담 같은 느낌으로 사적인 이야기를 조금 써보면,

 

 

얼마전에 인스타에서 주운 귀여운 고양이 사진.

사진이 너무 귀여워서 어딘가의 프로필 사진으로 쓰고싶은데 아직까지 쓸 곳이 없다. 잘 보관해둬야겠다 ....

 

 

아는 동생과 간 을지로의 언오디너리. 

화이트데이 때 갔다고 저렇게 귀여운 곰돌이를 ... 

 

풍기 파스타와 치킨스테이크는 정말 기억에 남았던. 특히 치킨스테이크 소스에 유즈코쇼가 들어갔다고했는데 그게 너무 마음에 들었던 것 같다. 살짝 매콤함과 크리미한 것이 조합이 좋았다. 

 

풍기 파스타는 조금 더 익혔으면 좋았을지도. 소스은 정말 훌륭했음.

 

모처럼 을지로까지 와줬는데, 청계천이라도 좀 걸으면 어떨까 싶었...는데 시간이 생각보다 너무 늦어지게 되어서 충분히 걷지는 못하고 들어가게 된 것이 아쉬웠다. 

 

11시쯤 되니 명동입구, 남대문세무서쪽 버스정류장에는 정말 무서울정도로 사람이 늘어서 있었다. 무난히 탈 수 있을거라 생각하고 안일하게 버스 정류장까지 뛰지 않았던 나 자신 정말 후회해.

 

 

 

강남 멘야시노기의 아부라소바. 챠슈가 조금 아쉬웠던 것 빼고는 정말 너무 마음에 들었다.

다음에는 츠케멘 같은 것을 도전하고 싶을지도? 원래는 돈코츠가 가장 유명하다고 하는데, 톤코츠...의 본고장에서 6년간 살았던 사람으로서 아직은 도전할 마음이 생기지는 않는 ... 기분이다.

 

주말의 강남은 정말 웃겼던 것 같다. 온갖 즐거운 경험을 해봤다. MUJI도 간만에 열심히 돌아봤고, 마음에 드는 ***멀티퍼퓸도 발견하고. 라인 프렌즈도 가보고. 옆에 있던 카카오프렌즈는 어느새 사라져있고 노티드만 덩그러니 남아있는 것이 마음이 살짝 아팠던.

***금목서향이 생각보다 많이 취향이었던 것을 알게 되었다. 

 

같이 어울려줬던 친구와 12시반쯤 만났는데, 어느새 4시 반이 넘어가고 있어서 놀랐던 것 같다. 가끔 시간을 같이 보냈을 때 녹듯이 빨리 사라지는 사람들이 있는 것 같다. 그런 사람들을 만날 수 있었던 것에 감사해야겠다.

 

 

자, 다음주도 힘내서 달려봅시다.

 

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

 

그럴때는 대개 내 경험에 대해서 말을 하면 되는데, 먼저 취직을 해야겠다고 생각했던 것은 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)