오랜만에 CSS 스타일링을 할때 항상 'how to center a div' 부터 검색하곤 합니다. 그만큼 UI를 배치함에 있어서 정렬은 자유자재로 다루어야 하는 스킬입니다. 오늘은 요소를 배치하고 정렬하는 display와 그 외 속성에 대해 다루어 보았습니다.

display 속성

display는 자신과 자식들의 레이아웃을 설정하는 속성입니다. 기본적으로 display는 외부와 내부를 설정하는 값들이 따로 그룹이 되어있고, 둘을 같이 설정할 수 있습니다.

외부

자신이 어떤 박스 모델로 다루어질지 설정합니다. block과 inline, 그리고 둘을 합쳐놓은 inline-block 세가지 값이 있습니다.

block

block의 특징은 다음과 같습니다.

1. block 모델은 한줄을 통으로 차지합니다. 때문에 전후로 어떤 요소가 있던간에 줄바꿈을 하고, 결국 자신의 줄에는 자신만 오게 됩니다.
2. 너비와 높이를 조정할 수 있습니다. 디폴트 값으로는 자신의 줄 방향으로는 최대로 확장하고, 반대 방향으로는 자식들이 차지하는 최소 길이 만큼만 차지합니다.

box1에는 width와 height를 모두 100px, box2에는 height만 100px, box3에는 width만 100px, 을 적용한 모습입니다.

inline

inline의 특징은 다음과 같습니다.

1. inline 모델은 자신의 영역만 차지합니다. 때문에 inline 모델인 요소끼리 같이 나열하면 나란히 붙는걸 볼 수 있습니다.
2. 너비와 높이를 조정할 수 없습니다. 너비와 높이를 지정하더라도 무시됩니다.

box1, box2, box3 모두 inline을 적용한 모습입니다.

inline-block

inline-block은 inline과 block의 특징이 섞여 있습니다.

1. inline-block 모델은 자신의 영역만 차지합니다. 때문에 inline-block 모델인 요소끼리 같이 나열하면 나란히 붙는걸 볼 수 있습니다.
2. 너비와 높이를 조정할 수 있습니다. 디폴트 값으로는 자식들이 차지하는 최소 길이만 차지합니다.

box1에는 width와 height를 모두 100px, box2에는 height만 100px, box3에는 width만 100px, 을 적용한 모습입니다.

내부

자신의 자식들이 어떤 레이아웃으로 관리될지 설정합니다. flow, flex, table, grid 등의 값이 있습니다.

외부와 내부 설정 모두 display 속성에서 다루어지기 때문에, 다음과 같이 display 속성에서 동시에 모두 설정이 가능합니다.

display: block flex /* 외부로는 block, 내부로는 flex로 설정 */
display: inline grid /* 외부로는 inline, 내부로는 grid로 설정 */

아래에서 flex 에 대해 더 자세히 다루도록 하겠습니다.

flex

내부의 자식을 flex-box모델로 관리합니다. flex-box 모델의 특징은 다음과 같습니다.

자식 요소들의 block화

내부의 요소들의 display 외부 속성이 block이 됩니다. 내부 요소에 명시적으로 display에 inline이나, inline-block을 설정하더라도 block 취급 됩니다.

flex 속성을 통한 사이즈 조절

내부의 요소들이 flex 속성을 통해 유동적인 사이즈 조절이 가능합니다. flex 속성을 지닌 요소들끼리 flex 값 만큼 공간을 나눠 갖게 됩니다.

box1에는 flex 없이 width만 50px, box2에는 flex에 2, box3에는 flex에 1, 을 적용한 모습입니다. 전체 width에서, box1의 50px을 제외한 나머지 공간을 box2와 box3가 각각 2 : 1 비율로 차지한것을 확인할 수 있습니다.

flex-direction 속성을 통한 방향 설정

flex-direction 속성을 활용하면, 자식 요소들이 어떤 방향으로 나열될 지 설정할 수 있습니다.

column과 row 가 있으며, 각각 세로와 가로를 의미합니다. 디폴트 값은 row입니다. -reverse를 붙이면 역방향으로 전개가 가능합니다.

display: row

display: row-reverse

display: column

display: column-reverse

justify-content와 align-items 속성을 활용한 정렬

flex-box 모델 내부의 요소들은 justify-content와 align-items 속성을 이용해 정렬이 가능합니다.

둘의 차이는 어느 방향으로 정렬할 지에 있습니다. justify-content는 요소의 나열 방향, 그리고 align-items는 요소 나열 방향의 수직방향을 컨트롤 합니다.

justify-content

justify-content에 오는 대표적인 값은 다음과 같습니다.

start     요소들을 첫 부분에 맞춰 정렬

center     요소들을 중앙에 맞춰 정렬

end     요소들을 끝 부분에 맞춰 정렬

space-between     요소들 사이사이에 공간을 넣되, 양 끝에는 공간을 남기지 않게 정렬

space-evenly     요소들 사이사이에 공간을 넣고, 양 끝에도 동일한 사이즈의 공간을 넣게 정렬

space-around     요소들 사이사이에 공간을 넣고, 양 끝에는 절반 사이즈의 공간을 넣게 정렬

justify-content : start	justify-content : center	justify-content : end
justify-content : space-between	justify-content : space-evenly	justify-content : space-around

align-items

align-items에 오는 대표적인 값은 다음과 같습니다.

start     요소들을 첫 부분에 맞춰 정렬

center     요소들을 중앙에 맞춰 정렬

end     요소들을 끝 부분에 맞춰 정렬

align-items : start

align-items : center

align-items : end

justify-content와 align-items의 예시를 비교해보면, flex의 나열방향이 가로임에 따라 justify-content는 가로 정렬을 컨트롤 하고, align-items는 세로 정렬을 컨트롤 하는 것을 볼 수 있습니다. Flutter에 익숙하신 분들은 justify-content를 MainAxisAlignment로, align-items를 CrossAxisAlignment로 외우시면 좋을 것 같습니다.

✏️ 정리

display로 할 수 있는 것은 이 보다도 훨씬 많지만, 이 특징들을 가장 많이 사용했던 것 같습니다. 요소들의 레이아웃과 정렬이 UI를 나타내는데 중요한 만큼 두고두고 꺼내 봐야겠습니다.

🔗 링크

MDN : display MDN : flexible box layout

날짜를 입력으로 주고 해당 날짜를 이용해 연산을 요구하는 문제들이 종종 있습니다. 저는 최근에 이 문제 (solved.ac 2022)에서 만났는데요, 이 문제를 해결하며 공부했던 파이썬의 datetime 모듈에 대해 필요한 부분들만 정리해보았습니다.

📜 코드

모듈

파이썬에서는 날짜와 시간을 자유롭게 다룰 수 있도록 datetime 모듈을 제공합니다. datetime 모듈만 있으면 웬만한 파싱과 연산은 처리할 수 있습니다.

datetime 클래스 datetime 내에서도 날짜와 시간을 다루기 위해 전용 클래스를 하나 두고 있습니다. 모듈과 이름이 동일해서 헷갈릴 수 있으니 주의해야합니다.

timedelta 클래스 클래스 이름 그대로 시간의 변화를 나타냅니다. datetime에서 시간을 더하고 빼는 연산을 지원하기 위해 존재합니다.

문자열로 된 날짜 파싱

datetime.datetime 클래스에 직접 년, 월, 일 등을 넣어 초기화할 수 있지만, 문자열을 바로 파싱해서도 초기화 할 수 있습니다.

다음과 같은 문자열을 datetime.datetime 객체로 만든다고 가정해봅시다.

dateString = "2024-06-30 18:01:52"

datetime.datetime 객체의 strptime 메서드를 사용하면 초기화할 수 있습니다.

dateString = "2024-06-30 18:01:52"

import datetime
date = datetime.datetime.strptime(dateString, "%Y-%m-%d %H:%M:%S")

첫 번째 인자로는 파싱할 문자열을, 두 번째 인자로 해당 문자열의 형식을 넣어주면 됩니다. 문자열 형식의 형식 지정자 외에 공백이나, -, : 등의 기호등을 모두 맞춰줘야 하는건 물론입니다. 형식지정자는 다음과 같습니다.

날짜 간 연산하기1 - 날짜를 UNIX시간으로 다루기

datetime.datetime 객체끼리는 직접적인 연산을 할 수 없습니다.

예를 들어, 다음의 두 datetime.datetime 객체의 차이를 구하고 싶다고 가정해봅시다.

import datetime
date1 = datetime.datetime.strptime("2024-06-30 18:01:52", "%Y-%m-%d %H:%M:%S")
date2 = datetime.datetime.strptime("2024-06-28 15:32:34", "%Y-%m-%d %H:%M:%S")

무작정 이런 식으로 빼면 datetime.datetime 끼리는 연산이 불가능하다고 오류가 발생합니다.

print(date1 - date2) # 오류 

그래서 datetime.datetime끼리 연산하기 위해서는 UNIX 시간으로의 변환이 필요합니다.

datetime.datetime 객체의 timestamp 메서드를 활용하면 해당 datetime.datetime 객체가 unix 시간으로 얼마인지 알 수 있습니다.

import datetime
date1 = datetime.datetime.strptime("2024-06-30 18:01:52", "%Y-%m-%d %H:%M:%S")
date2 = datetime.datetime.strptime("2024-06-28 15:32:34", "%Y-%m-%d %H:%M:%S")

date1unix = date1.timestamp()
date2unix = date2.timestamp()

print(date1unix - date2unix)

이를 실행해보면 181758.0 을 얻을 수 있고, 이는 두 시간이 181758초 만큼 차이가 난다는 것을 알 수 있습니다.

날짜 간 연산하기2 - timedelta 객체 사용하기

위의 방식은 날짜와 날짜사이가 얼마나 차이나는지는 쉽게 알 수 있지만, 특정 날짜에 며칠, 혹은 몇시간 뒤는 얼마인지는 연산하기 복잡합니다.

물론 datetime.datetime 의 fromtimestamp() 메서드를 활용하면 UNIX 시간을 datetime.datetime 객체로 변환해주어 가능합니다.

import datetime

#현재 시간 받아오기
curTime = datetime.datetime.now()

#79시간 뒤의 unix 시간 구하기
nextTimeUnix = curTime.timestamp() + 79 * 60 * 60

#datetime으로 변환
nextTime = datetime.datetime.fromtimestamp(nextTimeUnix)

print(nextTime)

하지만 UNIX 시간으로 변환을 하고, 다시 datetime으로 변환하는 것이 뭔가 비효율적인 것 같죠.

datetime.timedelta 객체에는 weeks부터 seconds까지 날짜와 관련된 파라미터를 넣어 초기화할 수 있습니다. 이렇게 생성한 datetime.timedelta 객체는 datetime.datetime 객체에 더하거나 뺄 수 있습니다.

import datetime

#현재 시간 받아오기
curTime = datetime.datetime.now()

#79시간을 timedelta로 나타내기
timeDiff = datetime.timedelta(hours=79)

#79시간 뒤 구하기
nextTime = curTime + timeDiff

print(nextTime)

✏️ 마무리

파이썬의 datetime 모듈에 대해 아주 간단하게 정리해봤는데요, 이 모듈 하나만 있으면 알고리즘 문제들에 나오는 시간 관련된 부분들은 잘 처리할 수 있는 듯 합니다.

이 문제는 ${nCr}$ 을 구하라는 문제입니다. 다만 n과 r의 범위가 1,000,000 까지라 깡으로 계산하기에는 숫자가 어마어마하게 크다는 문제가 있죠.

물론 1,000,000,007로 나눈 나머지를 구하라고 하지만, ${nCr}$을 구하는 과정에서 나눗셈이 들어가서 선뜻 모듈러 연산을 중간 중간에 끼워 넣기에는 쉽지 않습니다.

이를 해결하기 위해 페르마의 소정리를 이용해 나눗셈을 곱셈으로 바꾸어 계산합니다.

🪡 로직

$nCr$

먼저, $nCr$ 부터 살펴봅시다.

분쟈의 $n!$ 의 일부와 분모의 $(n-k)!$ 를 날리면 결과적으로 ${ (n - k + 1) * (n - k + 2) * ... *(n)}$ 에다가 $k!$을 나눠주면 됩니다.

페르마의 소정리

문제는 ${ (n - k + 1) * (n - k + 2) * ... *(n)}$ 이 어마어마하게 클 수 있어 중간중간에 모듈러 연산을 하며 계산을 이어나가줘야 하지만, 모듈러 연산을 한 분자에 $k!$로 나누면 결과가 바뀌어 함부로 중간 중간에 모듈러 연산을 할 수 없죠.

이를 해결하기 위해 페르마의 소정리를 이용합니다. 페르마의 소정리에 대한 자세한 내용은 이전 포스팅을 참고하세요.

결과적으로, ${(((n - k + 1) * (n - k + 2) * ... *(n)) * (k!)^{1,000,000,007 - 2})\ \ mod\ \ 1,000,000,007}$ 를 구하면 됩니다.

하나의 식으로 적어놔서 괜히 어려워 보일 수 있지만,

n - k + 1 부터 n까지 곱하고, 거기에 k!의 1,000,000,005 거듭제곱을 곱하면 됩니다. 이 중간중간에 1,000,000,007으로 모듈려 연산도 해주고요.

🧵 코드

분자 계산하기

먼저 분자를 계산해줍니다.

numerator = 1
for i in range(N - R + 1, N + 1, 1):
  numerator = (numerator * i) % p

$N-R+1$부터 $N$까지 곱해주며 중간 중간에 p로 모듈러 해줬습니다. 간단하죠?

분모 계산하기

다음은 분모를 계산해줍니다.

denominator = 1
for i in range(1, R + 1):
  denominator = (denominator * i) % p

분모는 그냥 $k!$ 입니다. 역시 중간 중간에 p로 모듈러 해줬습니다. 더 간단하죠?

분모의 역원 구하기

분모의 p-2 거듭제곱을 구해줍니다.

invol = p-2
result = 1

while invol > 0:
  if invol % 2 == 1:
    result = (result * denominator) % p
  denominator = (denominator * denominator) % p
  invol = invol // 2

invol을 2로 나눠줘가고, 동시에 denominator을 제곱해줘가며 현재 거듭제곱을 곱해야할 때 result에 곱해주는 방식입니다. 이전 포스팅을 살짝 변형했습니다.

최종

이제 입력받고, 마지막에 분자와 분모의 역원을 곱해주기만 하면 됩니다.

N, R = map(int, input().split())

p = 1000000007

#분자 계산하기
numerator = 1
for i in range(N - R + 1, N + 1, 1):
  numerator = (numerator * i) % p

#분모 계산하기
denominator = 1
for i in range(1, R + 1):
  denominator = (denominator * i) % p

#분모의 p-2 거듭제곱 구하기
invol = p-2
result = 1
while invol > 0:
  if invol % 2 == 1:
    result = (result * denominator) % p
  denominator = (denominator * denominator) % p
  invol = invol // 2

print((numerator * result) % p)

끝!

🐈‍⬛ 번외

사실 이 문제에 대해 공부하다가 발견한건데... 파이썬에선 $a^b \ mod \ p$ 를 열심히 비트연산해가며 거듭제곱 할 필요가 없더라구요...?

pow 함수의 세번째 인자를 넣으면 해당 인자로 모듈러 연산을 해준다고 합니다. 그리고 내부적으로 $a^b$를 구할때도 무식하게 $a$를 $b$번 곱하지 않는 듯 해요.

한마디로 요약하면, 분모의 p-2 거듭제곱을 구할 때

...
result = pow(denominator, p-2, p)
...

로 간략하게 줄일 수 있습니다. 앞으로는 자주 써먹어야겠어요😊

🔗참고

[알고리즘] 모듈러 연산과 나눗셈 [알고리즘] 분할정복으로 거듭제곱 빠르게 하기

a를 n번 거듭제곱 하려면 n-1번의 연산을 수행해야 합니다. a에 a를 곱하고, 그 결과에 a를 곱하고, 계속 해나가다보면 곱셈연산이 n-1번 이루어지겠지요. 그런데 만약 어마어마하게 큰 숫자의 거듭제곱을 해야한다면 어떨까요?

분할정복을 이용하면 O(n)의 시간 복잡도를 O(log n) 까지 줄일 수 있습니다.

🪡 이론

이론은 연산 과정을 분리하고, 중복되는 결과들을 저장해놓고, 저장된 것이 있다면 꺼내쓰는 것입니다.

거듭 제곱 연산 분할

거듭제곱의 연산과정을 살펴보겠습니다.

$3^{100}$을 한다고 가정해보겠습니다.

사실 3의 100거듭제곱은 이렇게도 생각할 수 있습니다. $3^{100} = 3^{50} * 3^{50}$

계속해서 분리할 수 있겠죠? $3^{100} = 3^{50} * 3^{50} = 3^{25} * 3^{25} * 3^{25} * 3^{25}$

여기서 $3^{100}$ 을 계산하는 것과 $3^{25} * 3^{25} * 3^{25} * 3^{25}$을 계산하는 과정에 들어가는 연산 횟수를 생각해봅시다. $3^{100}$을 계산하는데는 3에 3을 99번 곱하므로 99번의 곱셈연산이 필요합니다. $3^{25} * 3^{25} * 3^{25} * 3^{25}$을 계산하는데는 3을 24번 곱하는것과, 그 결과끼리 4 거듭제곱이 일어나므로 총 27번의 곱셈연산이라고 볼 수 있습니다.

두 번 분할 했더니 99회에서 27회로 줄었습니다.

이렇게 더 작은 단위로 나누면 연산 횟수가 월등히 줄어드는 것을 볼 수있습니다.

거듭 제곱 연산 분할 _ 파이썬 코드

이 과정을 파이썬 코드로 작성하면 다음과 같습니다.

a = 3

##거듭제곱 결과를 저장해놓은 테이블. 미리 기저인 3의 0 거듭 제곱과 1 거듭 제곱을 채워 놓음
involutionTable = {0 : 1, 1 : a}

def involution(n):

    #계산된 결과가 있으면 끌어다 쓰기
    if n in involutionTable:
        return involutionTable[n]

    #계산된 결과가 없으므로 계산하기 (분할정복)
    involutionTable[n] = involution(n // 2) * involution(n - n // 2)

    return involutionTable[n]

print(involution(100))

계산 결과를 저장하고 꺼내쓰는 점에서 dp 스킬이 들어갔습니다.

조금 더 빠르게?

분할을 바꾸면 연산 횟수를 더 줄일 수 있습니다. 분할된 지수가 2의 거듭 제곱이 되도록 하는 것입니다.

$3^{100}$으로 예시를 들어보면, $3^{100} = 3^{64} * 3^{32} * 3^{4}$ 이렇게 분할하는 것입니다.

이렇게 분할하는 이유는 거듭제곱 결과를 저장해놓는 테이블을 쉽게 채우는데 있습니다. 위의 방식으로는 어떤 계산결과가 필요할지 몰라 딕셔너리로 선언을 해놓은 후 매번 찾고 없으면 계산해 입력하는것을 볼 수 있습니다. 하지만 2의 거듭 제곱의 지수로만 이루어진 테이블을 만들어 놓고, 해당 지수들을 조합해 전체 결과를 계산하는 방식으로 한다면, 테이블을 만드는데 소요되는 연산이 logn 밖에 걸리지 않습니다.

조금 더 빠르게? _ 파이썬 코드

코드로 살펴보겠습니다.

a = 3

#거듭제곱 계산결과 테이블 채우기
involutionTable = [a]
for i in range(1, 10):
    involutionTable.append(involutionTable[i - 1] * involutionTable[i - 1])

def involution(n):

    ##비트 연산을 이용해 결과 계산
    result = 1
    i = 0
    while n > 0:
        if n % 2 == 1:
            result *= involutionTable[i]
        n //= 2
        i += 1

    return result

print(involution(100))

여기서 $involutionTable[i] = 3^{2^{i}}$ 입니다. $3^{1}, 3^{2}, 3^{4}, 3^{8}, ...$ 이렇게 만들어놓고, n을 비트연산 해가며 필요한 3의 거듭제곱을 조합해 전체 결과를 만드는 방식입니다.

이 방식을 이용하면 재귀함수도 하지 않아도 되고, 연산량도 줄어 좋습니다.

🧵 적용

거듭제곱에서 분할정복을 이용하여 빠르게 진행하는 방식은 당연하게도 모든 거듭제곱 연산에 적용이 가능합니다. 대표적으로 행렬의 거듭제곱을 하는데 많이 쓰입니다. 행렬은 곱하는데만 기본적으로 $n^3$ 의 시간복잡도를 가지고 있으니 다른 곳에서라도 연산량을 줄일 필요가 있겠죠.

알고리즘 문제들을 풀다보면 경우의 수를 찾는 DP문제, 큰 수 구하기 등 여러 부분에서 해의 값을 어떤 큰 소수로 나눈 나머지 로 구해달라는 상황을 마주할 수 있습니다.

대부분 이런 경우에서는 답을 구해놓고 모듈러 연산을 하는 것이 아닌, 해를 구해가는 과정 중간 중간에 모듈러 연산을 처리하는 것을 볼 수 있습니다.

하지만 해를 구해가는 과정에 나눗셈이 들어가게 되면 마음대로 모듈러 연산을 할 수 없습니다. 이럴 때는 어떻게 해야 할까요?

🪡 이론

모듈러 연산

정수를 어떤 주어진 수에 대한 나머지에 대하여 정의하는 것을 모듈러 연산이라고 하죠.

해를 구하는 중간 중간에 모듈러 연산을 처리해도 답이 같은 이유는 정수를 합하고 곱하고 뺄 때, 모듈러 연산을 전에 처리하는 것과 후에 처리하는 것이 같기 때문입니다.

합, 차, 곱에서 모듈러 연산

합, 차, 곱에서 모듈러 연산을 전에 처리하는 것과 후에 처리하는 것이 같다는 것을 파이썬 코드로 살펴보면 다음과 같습니다.

a = 13
b = 17

p = 11

## 합
(a + b) % p == ((a % p) + (b % p)) % p    # True

## 차
(a - b) % p == ((a % p) - (b % p)) % p    # True

## 곱
(a * b) % p == ((a % p) * (b % p)) % p    # True

a와 b를 연산하고 모듈러 취하는 것과, 모듈러 취하고 난 후 연산 하는 것이 값이 같다는 것을 확인할 수 있습니다.

나눗셈에서 모듈러 연산

그렇다면 나눗셈은 어떨까요?

a = 13
b = 17

p = 11

## 나눗셈
(a / b) % p == ((a % p) / (b % p)) % p    # False

나눗셈은 성립하지 않는 다는 것을 확인할 수 있습니다.

모듈러에서 나눗셈을 하려면 다른 방식이 필요합니다.

항등원과 역원

기본적인 개념은 나눗셈을 곱셈으로 치환하여 생각하는 것입니다. 이를 위해서는 항등원과 역원의 개념을 알아야 합니다.

먼저 항등원에 대해 알아보겠습니다. 항등원은 어떠한 연산에 대해 값에 연산을 해도 동일한 값이 나오는 숫자입니다.

값 (연산) 항등원 = 값

이 성립한다는 뜻이죠.

예를 들어보겠습니다.

덧셈 연산에 대한 항등원은
A + 항등원 = A
을 만족하는 값이므로 0입니다.

곱셈 연산에 대한 항등원은
A * 항등원 = A
을 만족하는 값이므로 1입니다.

이 개념을 가지고 역원에 대해 알아보겠습니다.

역원은, 연산해서 항등원이 나오는 수인데요, 예를 들어보겠습니다.

3의 덧셈 연산에 대한 역원은
3에 덧셈 연산을 해서 0(덧셈 연산에서 항등원)이 나오는 수이므로
-3입니다.

2의 곱셈 연산에 대한 역원은
2에 곱셈 연산을 해서 1(곱셈 연산에서 항등원)이 나오는 수이므로
0.5입니다.

여기서부터 핵심입니다. a를 b로 나눈다는 것은 a에 (곱셈에 대한 b의 역원)을 곱하는 것과 같습니다. 간단하게 증명해보겠습니다.

b * (곱셈에 대한 b의 역원) = 1
이 성립합니다.
양변에 b를 나누면
(곱셈에 대한 b의 역원) = 1 / b
가 성립합니다.

a / b 를 a * 1 / b 로 생각하고,
1 / b 는 (곱셈에 대한 b의 역원)와 같으므로,
a / b 는 a * (곱셈에 대한 b의 역원)와 같습니다.

사실 생각해보면, 당연한 말입니다. 5로 나눈다는 것은 1 / 5 (곱셈에 대한 5의 역원)를 곱한다는 것과 같은 말이니까요.

여기서 문제는, 모듈러 연산에서 곱셈에 대한 값의 역원을 구하는 일입니다. 일반적인 곱셈에서의 역원을 구할 때 처럼 역수를 취하면, 결국 나누는 것과 같으므로, 다른 방식으로 역원을 구할 필요가 있습니다.

페르마의 소정리

그렇다면, 모듈러 연산에서 곱셈에 대한 값의 역원을 구해보겠습니다.

이를 위해서는 페르마의 소정리를 알고 가야합니다.

이중에서

a = 13    #p의 배수가 아닌 수
p = 11    #소수

## 페르마의 소정리
(a ** (p - 1)) % p == 1    # True

이 식을 꼭 알고 가야합니다.

• p는 임의의 소수이고, a는 p의 배수가 아닌 수라고 가정하겠습니다.
• a에 p-1 거듭제곱을 한 후 p에 대해 모듈러 연산을 하면 1이 나옵니다.

1은 곱셈에서 항등원 이므로, 다음과 같이 역원을 유도해낼 수 있습니다.

(a * (a의 역원)) % p == 1                ...(1)

페르마의 소정리에 의하면,
(a ** (p - 1)) % p == 1 이므로,
a의 p - 1 거듭제곱에서 a를 하나 꺼냅니다.
그러면 다음과 같은 식이 성립합니다.

(a * a ** (p - 2)) % p == 1                ...(2)

(1)과 (2)에 의해,
a의 역원은 a ** (p - 2)라는 것을 알 수 있습니다.

• 모듈러 연산에서 곱의 역원은 a의 p - 2 거듭제곱입니다.

모듈러 연산에서 나눗셈 대체하기

위의 식들을 합치면 나눗셈에서 모듈러 연산을 다음과 같이 변환할 수 있습니다.

a = 26
b = 13

p = 11

## 나눗셈
(a / b) % p == ((a % p) * ((b ** (p - 2)) % p)) % p    # True

위 식이 성립하려면, a 가 b로 나누어 떨어져야 합니다. 우변은 곱과 모듈러 연산으로만 이루어져 있을테니 결과가 정수일테고, 따라서 좌변도 정수여야 위 식이 성립하겠죠.

🧵 적용

이 방식의 핵심은 페르마의 소정리를 이용해 나눗셈을 곱셈으로 치환하는 것입니다. 나눗셈에서는 중간 중간에 모듈러 연산시 결과가 달라지지만, 곱셈에서는 같으니까요.

나눗셈의 결과가 정수임을 알지만, 값들이 너무 커서 한번에 연산이 불가능할 때, 페르마의 소정리를 이용해 나눗셈을 곱셈으로 대체하고, 계산 중간 중간에 모듈러 연산을 처리하며 계산량을 줄이는 방식입니다.

자세한 적용 예시는 다음에 문제풀이로 돌아오도록 하겠습니다😊

🔗 링크

• 위키백과 모듈러 연산 항등원 역원 페르마의 소정리

인도 LG 인턴십에서 Flutter로 앱 개발을 하며 원형 슬라이더 컴포넌트를 만들었습니다. 목표로 하는 UI를 정확히 구현하기 위해 이리저리 찾다가 CustomPaint를 활용해서 여러 도형들을 배치하는 구현 방법을 발견했습니다. 개인적으로 CSS에 비하면 Flutter가 디자인을 구현하는 데는 더 어렵다고 생각하고 있었는데, 그런 면에서 CustomPaint는 참신했습니다.

☕ 상황

조명을 밝기를 제어하는 360도 원형 슬라이더를 구현하고, 중앙에 조명 아이콘과 on/off 버튼도 배치해야 했습니다. 그 외에도 inner shadow 등의 디테일과 컴포넌트 내부에 요소들이 많았기에 여러 부분들로 쪼개어 차근차근 구현했습니다.

🎯 구현 목표

1. 테두리의 원형 슬라이더
    12시 방향부터 핸들이 지나온 부분은 노란색, 지나가지 않은 부분은 흰색으로 표시
    inner shadow 넣기

2. 중앙의 Angular 그라데이션
    슬라이더의 핸들이 위치한 부분을 기준으로 Angular 그라데이션 넣기

3. 중앙의 아이콘 및 on/off 버튼
    부가적으로 아이콘과 on/off 토글 버튼 넣기

👨‍💻기술

Flutter

LG인도 인턴을 진행하며 만난 멘토분이 여러 웹 사이트들을 많이 추천 해주셨습니다. 그 중 하나가 quicktype.io 인데, 프로젝트를 진행하며 모델 클래스 코드를 통일 시키는데 많은 도움을 받았습니다. 많은 기능들을 사용해보지는 않았지만, 이런 사이트도 있다는 걸 공유해보고자 해요.

🚩 웹사이트 소개

quicktype.io 는 모델 클래스를 만들어주는 사이트입니다. JSON형식으로 된 인스턴스 예시만 하나 던져주면 알아서 해당 인스턴스를 만들 클래스 코드를 작성해줍니다. 한마디로 인스턴스 → 클래스 변환 툴이라고 말할 수 있습니다.

🎈 튜토리얼

시작

사이트 들어가자마자 우측 상단에     버튼을 누르면 시작할 수 있습니다.

언어 설정

우측의 탭을 보면 클래스를 생성할 때의 여러 설정들을 확인할 수 있습니다. 그중 가장 먼저 어떤 언어로 생성할지 설정해 줍니다. 저는 Flutter 프로젝트에 사용했어서 dart로 설정해줄게요.

클래스 인스턴스 작성

클래스 코드를 만들기 위해 JSON 형식으로 된 클래스의 인스턴스를 입력받습니다. JSON으로 입력받으므로 서버측에서 주는 response를 이용하면 좋겠죠? 저는 다음과 같이 햄버거와 관련된 인스턴스를 예시로 작성해봤습니다.

{
  "hamburger" : "cheese burger",
  "combo" : true,
  "price" : 6500,
  "discount" : 0.1
}

클래스 코드 생성

이제 작성한 인스턴스를 좌측에 붙여넣기만 하면 우측에 클래스 코드가 바뀌는것을 확인할 수 있습니다. 클래스 명은 좌측 상단에 Name을 수정하면 지정해줄 수 있습니다. 저는 Order로 해봤습니다.

🍔 기능

생성자 및 파싱관련 함수

코드를 확인해보면 파싱과 관련된 함수들이 자동으로 생성돼있는 것을 확인할 수 있습니다.

제가 생성한 코드에는 JSON 문자열을 입력받아 Order 객체를 리턴해주는 orderFromJson 함수와 fromJson 함수, Order 객체를 입력받아 JSON 문자열을 리턴해주는 orderToJson 함수와 toJson 함수가 있습니다.

타입 추론

입력으로 넣었던 데이터의 타입이 자동으로 추론돼있는 것을 확인할 수 있습니다.

문자열, 정수, 실수, 불리언 모두 넣어 테스트 해본 결과, 맞게 추론돼있습니다.

리스트 처리

그렇다면 입력을 리스트로 주면 어떻게 될까요?

Order 인스턴스를 여러개 만들어 리스트로 전달해보겠습니다.

[
  {
    "hamburger" : "cheese burger",
    "combo" : true,
    "price" : 6500,
    "discount" : 0.2
  },
  {
    "hamburger" : "chicken sandwich",
    "combo" : false,
    "price" : 7800,
    "discount" : 0.1
  },
  {
    "hamburger" : "burger",
    "combo" : true,
    "price" : 5500,
    "discount" : 0
  }
]

결과는 리스트가 필드로 들어가지 않고, 파싱 관련 메서드만 리스트로 리턴하게 바뀝니다.

객체 처리

입력을 복잡한 객체의 형태로 주었을때는 그에 맞게 여러 클래스의 코드를 작성해주는 것을 볼 수 있습니다.

입력으로 주문리스트의 객체를 전달해 보겠습니다.

{
  "count": 3,
  "orders": [
    {
      "hamburger" : "cheese burger",
      "combo" : true,
      "price" : 6500,
      "discount" : 0.2
    },
    {
      "hamburger" : "chicken sandwich",
      "combo" : false,
      "price" : 7800,
      "discount" : 0.1
    },
    {
      "hamburger" : "burger",
      "combo" : true,
      "price" : 5500,
      "discount" : 0
    }
  ]
}

orders로 주어진 객체의 리스트를 독단적인 class로 잘 생성했고, 심지어 필드명이 복수형(orders) 임에도 불구하고 자동으로 단수형(order)으로 클래스 명을 설정한 것을 볼 수 있습니다.

우측 패널

그 외에도 우측 패널을 보면 여러 옵션들이 있는 것을 확인할 수 있습니다. 언어별로 세세하게 옵션이 다른것을 확인할 수 있습니다. 다트 같은 경우에서도 Flutter의 copyWith 생성자를 만들어주는 옵션도 있고, 프로퍼티들을 옵셔널로 지정하거나 final로 지정하는 등의 옵션도 있습니다.

✏️ 정리

개발 속도를 향상시켜주고 코드를 통일시켜준다는 면에서 여러모로 유용한 사이트입니다. 어쩌면 관련돼서 라이브러리가 나올지도 모르겠네요.

저는 특히 dart를 사용하면서 json 파싱하는 부분에 애를 많이 먹었었고, 지금도 파싱 관련해서 좀 더 이해하기 쉬운 코드를 작성하도록 고민을 많이하는데, 도움이 많이 되는 것 같아요.

🔗 링크

quicktype.io