공부정리

 django에는 django admin이라는 굉장히 편리한 기능이 있다.  지금까지 우리가 쉘에서 해온 작업들을 django admin을 사용하면 훨씬 편하게 수행할 수 있다.

1. 슈퍼유저

 django admin을 사용하기 위해 슈퍼유저를 생성할 필요가 있다.  createsuperuser 명령어로 슈퍼유저를 생성한다.

python manage.py createsuperuser

필자의 경우 이미 만들어둔 슈퍼유저가 있기에 같은이름을 사용하려고 하니 이미 존재하는 이름이라며 에러가 발생한다.  다른 이름을 입력한 뒤 이메일, 패스워드를 설정해준다. 패스워드가 충분히 강력한지 검사하여 너무 취약한 패스워드를 사용할 경우 위와 같이 경고메시지가 뜨지만 무시하고 진행할 수도 있다.

삭제의 경우 django shell 에서 django.contrib.auth.models 의 User 모델에서 유저명과 슈퍼유저 여부를 조건으로 삭제할 슈퍼유저 데이터를 가져온 뒤 delete()를 실행해주면 된다. 이전에 Question, Answer 데이터를 삭제할 때와 같은 방식이다.

2. django admin 접속

 이제 로컬 서버를 구동한 뒤 http://localhost:8000/admin/ 에 접속한다.

python manage.py runserver

접속하면 위와 같이 로그인 화면을 볼 수 있다.  방금 생성한 슈퍼유저 계정으로 로그인을 해보자

로그인을 하면 위와 같이 사용자와 그룹의 데이터를 추가, 변경, 조회 가능한 것을 볼 수있다.  

3. django admin 을 사용한 모델 관리

 여기서부터가 django admin의 진면목이다.  pybo\admin.py 를 수정하여 django admin에 더 많을 기능을 추가할 수 있다.

pybo\admin.py 를 위와 같이 수정해준다.  pybo\models.py에 정의해둔 Question과 Answer 클래스를 import 한 뒤 admin.stie에 등록한다는 의미이다. 수정한 뒤 다시한번 admin 페이지에 접속해보자

방금 전까지는 그룹, 사용자 모델만을 관리할 수 있던 admin 페이지에서 이제는 PYBO의 모델들도 관리할 수 있게되었다. 

추가를 클릭하면 GUI 환경에서 편리하게 데이터를 생성할 수도 있다.

이번에는 데이터를 검색하기 위해 admin.py를 한번 더 수정해본다.

pybo\admin.py 를 위와 같이 수정한 뒤 다시한번 관리자 페이지에 접속한다.

Question의 데이터 리스트 위에 검색창이 추가된 것을 볼 수 있다.  'subject' 항목으로 검색할 수 있도록 하였기 때문에 질문의 제목으로 검색이 가능하다.

시험삼아 Model로 검색해보니 Model이 포함된 질문 하나만이 필터링 되는 것을 볼 수 있다.

django admin은 이 밖에도 편리한 기능들을 무수히 많이 제공하니 잘 알아둘 필요가 있다.  django admin에 대한 자세한 내용은 공식문서(https://docs.djangoproject.com/en/3.0/ref/contrib/admin/)를 참고하도록 하자.

 분할 정복(Divide and Conquer)은 큰 문제를 작은 문제로 쪼개서 처리하는것으로 보다 효율적으로 문제를 해결하는 방식이다.  문제를 작게 쪼갠 후 쪼개진 문제들을 또 다시 작게 쪼개는 형태로 이루어지기 때문에 보통 재귀를 사용하여 구현하게 된다.  알고리즘 문제풀이에 굉장히 자주 사용되는 기법이기 때문에 관련 문제들을 풀어보며 잘 정리해보기로 한다.

1. 종이의 개수(https://www.acmicpc.net/problem/1780)

 n*n 행렬로 표현되는 종이가 한가지 색으로 이루어져있다면 종이를 그대로 사용, 그렇지 않다면 같은크기로 9등분하고 각 종이들에 대해 같은 작업을 반복한다고 할 때, 작업이 끝난 후 색깔별 종이의 갯수를 구하는 문제.  전형적인 분할 정복 문제의 유형이다.  문제에서 이미 해야할 일을 모두 알려줬기 때문에 재귀를 사용하여 그대로 구현하기만 하면 해결 가능하다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol1780():
    n = int(input())
    paper = [list(map(int, input().split())) for _ in range(n)]
    res = [0, 0, 0]

    def check(r, c, s):
        color = paper[r][c]
        # 1칸짜리 종이라면 해당 종이 색의 카운트를 1 증가 후 종이의 색을 반환
        if s == 1:
            res[color + 1] += 1
            return color

        g = s // 3
        cut = False
        # 종이를 9등분하여 재귀호출
        for i in range(r, r + s, g):
            for j in range(c, c + s, g):
                if check(i, j, g) != color:
                    cut = True

        # 쪼갠 종이들이 모두 같은 색이 아니었다면 2 반환
        if cut:
            return 2

        # 모두 같은 색이었다면 중복으로 더해진 갯수를 빼준 뒤 색(-1, 0, 1) 반환
        res[color + 1] -= 8
        return color

    check(0, 0, n)
    return '\n'.join(map(str, res))

 이 문제처럼 분할 정복을 어떻게 적용해야할지 대놓고 알려주는 문제의 경우 그것을 구현하는 것은 그리 어려운 일이 아니지만 분할 정복 문제의 경우 조금 잘못구현하면 시간초과가 발생할 정도로 시간제한이 빡빡한 경우가 많기때문에(특히 파이썬으로 푼다면 더욱) 구현의 연습자체도 어느정도 해둘 필요가 있다.  예를들어 위 코드에서도 문제대로면 종이가 모두 같은색인지 검증한 뒤 종이를 잘라야하지만 실제로 그렇게 했다간 K크기로 잘라진 종이마다 K^2 만큼의 시간을 추가로 사용하게 된다. 그렇기에 조각난 종이들이 반환한 결과를 보고 나눌 필요가 없었다면 나누지 않은 것으로 결과를 수정하는 방식을 취하였다.

2. 곱셈(https://www.acmicpc.net/problem/1629)

 자연수 a, b, c가 주어졌을 때 a의 b제곱을 c로 나눈 나머지를 구하는 매우 간단한 문제이다. 다만 a, b, c의 크기가 상당히 크고 제한시간도 짧기 때문에 단순히 a ** b % c 를 했다간 당연하게도 시간초과가 발생한다.  이 문제도 분할 정복 기법을 사용하여 중복연산을 줄이고 빠르게 해결 가능하다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol1629():
    a, b, mod = map(int, input().split())

    def pow(a, b):
        nonlocal mod
        # b가 1일경우 a를 반환
        if b == 1:
            return a % mod

        # a의 b//2 제곱의 제곱을 구한 뒤 % mod
        res = pow(a, b // 2) ** 2 % mod

        # 만약 b가 홀수라면 a를 한번 더 곱한 뒤 % mod
        if b % 2:
            res = (res * a) % mod

        return res

    return pow(a, b)

 이런 문제들은 1번의 문제처럼 분할정복을 어떻게 적용할지를 대놓고 알려주지 않는다.  물론 이 문제의 경우 한눈에 어떻게 적용해야할지 보이는 수준의 간단한 문제지만 어려운 문제일수록 분할정복으로 접근해야한다는 생각을 하고 어떻게 분할정복 기법을 적용해야할지 아이디어를 떠올리기가 쉽지않다.  

3. 행렬 제곱(https://www.acmicpc.net/problem/10830)

 2번 문제가 자연수의 제곱을 빠르게 구하는 것이었다면 이번에는 행렬의 제곱을 빠르게 구하는 문제이다.  당연하게도 분할정복 기법을 적용하는 아이디어는 2번 문제와 거의 동일하다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
mod = 1000


def sol10830():
    n, b = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(n)]
    
    # 행렬의 b제곱을 구한다
    mat = matsq(mat, b)
    
    # b가 1일 경우 matmul 함수를 거치지않아 각 원소에 나머지연산이 적용되지 않을 수 있음
    for i in range(n):
        for j in range(n):
            mat[i][j] %= mod
            
    return '\n'.join([' '.join(map(str, mat[i])) for i in range(n)])
   

# 행렬의 거듭제곱
def matsq(m, x):
	# x가 1이라면 m 반환
    if x == 1:
        return m
        
    # m^(x//2)의 제곱을 구한 뒤 x가 홀수라면 m을 한번 더 곱해준다
    res = matsq(m, x//2)
    res = matmul(res, res)
    if x % 2:
        res = matmul(res, m)
    return res
    

#행렬의 곱셈
def matmul(a, b):
    res = [[0] * len(a) for _ in range(len(b[0]))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(b)):
                res[i][j] += (a[i][k] * b[k][j])
            # 각 원소를 계산한 뒤 나머지연산 
            res[i][j] %= mod
    return res

행렬의 곱셈이나 거듭제곱은 다른 문제에도 종종 활용될 수 있어 기억해두면 도움이 될 수 있다.

4. 피보나치 수 6(https://www.acmicpc.net/problem/11444)

 피보나치 수열의 n번째 수를 구하는 문제이다.  동적계획법을 사용한 방법의 경우 O(N)의 시간으로 피보나치 수를 구할 수 있지만, 이 문제의 경우 n이 최대 1,000,000,000,000,000,000까지 올라갈 수 있기 때문에 더 빠른 알고리즘이 필요하다.  하지만 3번의 행렬의 거듭제곱을 활용하면 더 빠르게 피보나치 수를 구할 수 있다. 피보나치 수열의 점화식인 F(N) = F(N-1) + F(N-2)를 행렬의 형태로 나타내면 아래와 같은 형태가 된다

즉, 1 * 2 행렬의 초기값을 (F(0), F(1)) 로 잡고 2 * 2 행렬 ((0, 1), (1, 1)) 의 N-1 제곱을 곱해준 뒤 행렬의 두 번째 값을 취하면 F(N)을 구할 수 있다. 물론 N이 0 또는 1인 경우는 예외적으로 처리를 해둘 필요가 있다. 이 방식은 분할 정복 기법을 적용한 행렬의 거듭제곱이 O(logN)의 시간복잡도를 가지기 때문에 O(logN)의 시간으로 피보나치 수를 구할 수 있다. 이를 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.read
mod = 1000000007


def sol11444():
    n = int(input())
    # n이 1 이하일 경우 자기자신을 반환 
    # F(0) = 0, F(1) = 1
    if n <= 1:
        return n
        
    # 초기 피보나치 행렬 (0, 1)에 ((0, 1), (1, 1))의 n-1 제곱을 곱해준다
    f = [[0, 1]]
    o = [[0, 1], [1, 1]]
    f = matmul(f, matsq(o, n - 1))

	# 계산이 끝난 후 피보나치 행렬의 두 번째 요소가 n번째 피보나치 수가 된다.
    return f[0][1]


# 행렬의 곱셈
def matmul(a, b):
    r, c, m = len(a), len(b[0]), len(b)
    res = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            for k in range(m):
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod
    return res


# 행렬의 거듭제곱
def matsq(m, x):
    if x == 1:
        return m
    res = matsq(m, x // 2)
    res = matmul(res, res)
    if x % 2:
        res = matmul(res, m)
    return res


if __name__ == '__main__':
    print(sol11444())

 큐(Queue)는 마지막에 삽입한 데이터가 가장 먼저 제거되는 스택과는 달리 먼저 삽입된 데이터가 먼저 제거되는 선입선출(FIFO)식 자료구조이다.  이름 그대로 대기열의 구현에 사용되며 네트워크상에서 패킷의 전송이나 OS의 스케줄링 등에서도 큐가 사용된다.  큐가 사용되는 대표적인 문제는 BFS 문제이며 그 외에도 큐의 성질을 활용해야하는 문제나 큐의 변형 자료구조인 데크(Deque)나 우선순위 큐(Priority Queue) 등을 활용한 문제들도 있다.  이번에는  큐와 데크를 활용하여 해결할 수 있는 문제 두 가지를 알아본다.

1. 프린터 큐 (https://www.acmicpc.net/problem/1966)

 문서마다 중요도가 주어지고 큐에서 가장우선도가 높은 문서들은 모두 큐의 맨 뒤로 보내며 처음으로 만난 최고 우선도의 문서를 제거하여 출력하는 프린터 큐를 구현하는 문제.  중요도가 중복되지 않는다면 정렬로 끝날 간단한 문제지만 같은 우선도를 가진 문서가 존재할 수 있기 때문에 큐를 활용하여 해결해야한다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol1966():
    res = []
    # 테스트케이스 루프
    for _ in range(int(input())):
        n, m = map(int, input().split())
        
        # 문서의 중요도와 초기 인덱스를 묶어서 리스트형태로 저장
        docs = list(zip(map(int, input().split()), range(n)))
        
        # 프린트 시작
        for i in range(1, n+1):
        	# 가장 우선도가 높은 문서중 가장 앞에 있는 문서를 출력
            # 문서의 초기인덱스가 m과 같다면 res에 답을 append하고 다음 테스트케이스로
            p = max(docs, key=lambda x:x[0])
            if p[1] == m:
                res.append(i)
                break
               
            # 실제로는 출력할 문서가 나올때까지 모든 문서를 하나하나 큐의 맨 뒤로 보내야하지만
            # 빠르고 간결하게 처리하기 위해 리스트 슬라이싱을 사용하여 같은 결과를 낸다.
            # 출력할 문서를 기준으로 좌우를 슬라이싱한뒤 순서를 바꾸어 이어붙인다.
            pi = docs.index(p)
            docs = docs[pi+1:] + docs[:pi]
            
    return '\n'.join(map(str, res))


if __name__ == '__main__':
    print(sol1966())

2. AC (https://www.acmicpc.net/problem/5430)

 R은 배열을 뒤집는 연산, D는 배열의 첫 번째 숫자를 버리는 연산이라고 정의할 때, 초기 배열과 연산순서가 주어지면 모든 연산을 수행한 뒤 배열의 상태를 출력하는 문제.  배열을 실제로 뒤집는 방식으로는 당연하게도 시간초과가 발생한다.  배열을 뒤집는다는 것이 곧 D 연산으로 버릴 숫자의 위치가 첫 번째와 마지막 사이에서 바뀌는 것이란걸 알면 양방향 큐인 데크를 활용하여 간단하게 해결 가능하다.  이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol5430():
    res = []
    for t in range(int(input())):
        cmd = input().rstrip()
        n = int(input())
        
        # D 연산의 횟수
        d = cmd.count('D')
        
        seq = input()
        
        # D 연산의 횟수가 수열의 크기보다 크면 에러
        if d > n:
            res.append('error')
        # 같다면 빈 배열
        elif d == n:
            res.append('[]')
            
        else:
            seq = list(seq[1:-2].split(','))
            # 두번 연속 뒤집기는 의미가 없음
            cmd = cmd.replace('RR', '')

            # 앞에 나온 R의 횟수가 짝수면 앞에서 버리기, 홀수면 뒤에서 버리기
            cmd = list(map(len, cmd.split('R')))
            seq = seq[sum(cmd[0::2]):n - sum(cmd[1::2])]
            if len(cmd) % 2 == 0:
                seq.reverse()
            res.append('[' + ','.join(seq) + ']')
    return '\n'.join(res)


if __name__ == '__main__':
    print(sol5430())

무의미한 뒤집기 연산을 제거하고 D연산의 횟수와 수열의 크기만으로 해결 가능한 케이스를 빠르게 처리하여 남는 것들만 실제로 연산들을 수행한다.  연속뒤집기를 제거하고나서 split('R')을 해주면 짝수번째 명령의 길이는 앞에서 버리는 D연산의 횟수, 홀수번째 명령의 길이는 뒤에서 버리는 D연산의 횟수가 된다. 이를 이용하면 일일히 뒤집기와 pop을 실행할 필요도없다.  실제로 데크를 사용하더라도 시간초과는 발생하지 않지만 이 방법을 사용하면 시간을 많이 단축할 수 있다.  물론 동작 원리는 결국 데크를 사용하는 것과 동일하다.

 스택(Stack)은 데이터를 아래에서 쌓아올리듯 삽입하고 맨 위에서 하나씩 꺼내는 후입선출(LIFO)식 자료구조이다.  매우 단순한 구조를 가지고있지만 OS의 인터럽트나 프로그램에서 함수의 호출 등 이전상태를 보존하고 다음단계를 진행한 뒤 돌아오는 형태의 많은 작업들에 활용되고있으며 그 특성을 이용하여 풀 수 있는 알고리즘 문제들도 있다.  이번에는 스택을 활용한 문제 3개를 정리해본다.

1. 균형잡힌 세상(https://www.acmicpc.net/problem/4949)

  소괄호와 대괄호, 영문알파벳, 공백으로 이루어진 문자열이 주어졌을 때, 문자열의 괄호가 모두 정상적으로 쌍을 이루고있는지 확인하는 문제.  괄호쌍을 확인하는 문제는 전형적인 스택 활용 문제중 하나이다.  여는 괄호는 스택에 push하고, 닫는 괄호가 나오면 쌍을 이룰 여는 괄호가 스택에 남아있는지 확인하여 pop 한다. 도중에 닫는 괄호와 쌍을 이룰 여는 괄호가 스택에 남아있지 않거나 모든 작업을 마친 후 여는 괄호가 스택에 남아있다면 괄호쌍이 맞지 않는 문자열임을 알 수 있다.  이 문제를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol4949():
    open = {'(', '['}
    close = {')', ']'}
    type = {'(': 0, ')': 0, '[': 1, ']': 1}
    
    def pair_check(s):
        st = []
        for c in s:
        	# 여는 괄호일 경우 스택에 type 값(소괄호, 대괄호 구분)을 push
            if c in open:
                st.append(type[c])
                
            # 닫는 괄호일 경우 스택탑에 같은 타입값이 존재하는지 확인
            elif c in close:
            	# 없을 경우 'no' 반환
                if not st or st[-1] != type[c]:
                    st = [-1]
                    return 'no'
                # 있을 경우 스택 pop
                st.pop()
                
        # 모든 작업 종료 후 스택이 비어있지 않다면 'no' 반환
        if st:
            return 'no'
            
        # 그렇지 않다면 'yes' 반환
        return 'yes'

    return '\n'.join(map(pair_check, input().splitlines()[:-1]))


if __name__ == '__main__':
    print(sol4949())

2. 스택 수열(https://www.acmicpc.net/problem/1874)

  특정 수열을 만들기 위한 스택의 삽입, 삭제 연산 순서를 구하는 문제이다. 간단한 문제지만 스택의 동작을 이해하는데 어느정도 도움이 된다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol1874():
    n, *seq = map(int, input().split())
    i = 1		# 스택에 삽입될 수
    st = []		# 스택
    res = []	# 연산 순서
    
    # 만들어야할 수열을 순회
    for num in seq:
    	# 해당 숫자가 스택에 들어갈 때 까지 push
        while i <= num:
            st.append(i)
            res.append('+')
            i += 1
           
        # 스택 탑의 값이 num과 같지 않다면 'NO' 반환
        if not st or st[-1] != num:
            return 'NO'
            
        # pop
        st.pop()
        res.append('-')
    return '\n'.join(res)


if __name__ == '__main__':
    print(sol1874())

3. 오큰수(https://www.acmicpc.net/problem/17298)

 주어진 수열의 각 수마다 자신보다 오른쪽에 있으면서 자신보다 큰 수중 가장 왼쪽에 있는 수를 찾는 문제이다.

단순히 자신보다 오른쪽부터 자신보다 큰 값이 나올때까지 선형탐색을 할 경우 O(N^2) 수준의 복잡도를 보이기 때문에 수열의 크기 N이 최대 100만까지 커질 수 있는 이 문제는 해결할 수 없다.  하지만 스택을 활용하면 간단하게 해결 가능한 문제이다.  수열의 수들을 스택에 순차적으로 push하되, push 전에 스택 탑이 자신보다 작은 수가 아닐 때까지 pop한 뒤 자신이 pop한 수의 오큰수가 되도록하면 모든 수의 오큰수를 구할 수 있다. 이 방법으로 문제를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol17298():
    n, *seq = map(int, input().split())
    # 오큰수를 찾지 못한경우 -1을 출력해야하기 때문에 디폴트값을 -1로 초기화
    res = [-1] * n
    
    # 수열의 수들을 순회
    st = []
    for i in range(n):
    	# 자신보다 작은 수가 스택 탑인 동안 pop,  pop한 수의 오큰수는 자신이 된다.
        while st and st[-1][0] < seq[i]:
            res[st.pop()[1]] = seq[i]
         
        # 스택에 수열에서의 인덱스와 함께 push
        st.append((seq[i], i))
        
    return ' '.join(map(str, res))


if __name__ == '__main__':
    print(sol17298())

 스택은 DFS 등에도 사용 가능한 자료구조이지만 이런 경우 보통 실제로 스택을 사용하기보다는 함수의 재귀호출 형태로 구현하게 되기 때문에 그부분은 따로 다루지 않기로한다.

 순서를 고려하지 않고 n개의 물건중 k개를 고르는 경우의 수(조합)를 이항 계수라 한다.  코딩테스트에 이항계수를 구하라는 문제가 나오지는 않겠지만 이항계수를 구해야 해결 가능한 문제가 나올 수는 있기 때문에 이항계수를 구하는 방법들에 대해 한번 따로 정리를 해두기로 한다.

1. 이항계수의 수식에 따른 방법

 이항계수를 nCk 를 구하는 수식은 nCk = n!/(k! * (n-k)!)  이다.  n과 k가 입력됐을 때 단순히 이 수식대로 계산하더라도 상당히 빠른 속도로 이항계수를 구할 수 있다.  주의할 점이라면 C나 Java 등의 변수의 자료형에 따른 정수 표현의 한계가 있는 언어의 경우 숫자가 빠르게 커지면서 오버플로우가 발생할 수 있다는 점이다.  그 때문에 이항계수를 구해야하는 문제들은 보통 매우 큰 소수로 모듈러연산을 한 결과를 요구한다.  

이 방식으로 이항계수 문제(https://www.acmicpc.net/problem/11050)를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol11050():
    n, k = map(int, input().split())
    deno = nume = 1
    for i in range(1, k+1):
        deno *= (n-i+1)
        nume *= i
    return deno//nume


if __name__ == '__main__':
    print(sol11050())

2. 동적계획법을 사용한 방법

 이항계수 nCk 는 n개중 k개를 고르는 경우의 수이며 이는 임의의 한개를 고르지 않았다고 가정하고 n-1개중 다시 k개를 고르는 경우의 수와 한개를 이미 골랐다고 가정하고 n-1개중 나머지 k-1개를 고르는 경우의 수를 더한 것과 같다.

즉, nCk = n-1Ck + n-1Ck-1 이라는 점화식이 성립한다.  이 점화식을 기반으로 동적계획법을 사용하면 O(N^2)의 시간/공간 복잡도로 이항계수를 구할 수 있다.  1번 방법에 비해 빠르지는 않지만 중간중간 모듈러연산을 적용하여 오버플로우가 발생할 위험을 조기에 방지할 수 있다.

이 방식으로 이항계수 문제(https://www.acmicpc.net/problem/11051)를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol11051():
    n, k = map(int, input().split())
    c = [[0] * (n+1) for _ in range(n+1)]
    for i in range(n+1):
        c[i][0] = c[i][i] = 1
       
    for i in range(1, n+1):
        for j in range(1, i+1):
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % 10007
    return c[n][k]


if __name__ == '__main__':
    print(sol11051())

3. 페르마의 소정리를 이용한 방법

 여기서부터는 조금 복잡하다.  여기서도 마찬가지로 1번 방법에서 사용한 이항계수를 구하기 위한 수식에 페르마의 소정리를 적용하여 풀어나간다. 페르마의 소정리란 p가 소수일 때,  a^p 와 a 는 p로 나눈 나머지가 서로 같다는 정리이다. 수식의 전개는 아래와 같다.

nCk % p

= (n!/(k! * (n-k)!)) % p 

= (n! * (k! * (n-k)!) ^ -1) % p

= ((n! % p) * ((k! * (n-k)!)^-1) % p) % p

페르마의 소정리 a^p ≡ a (mod p) 에서 양 변에 a^-2를 곱해주면  a^(p-2) ≡ a^-1 (mod p) 이 된다.

∴ ((n! % p) * ((k! * (n-k)!)^-1) % p) % p

= ((n! % p) * ((k! * (n-k)!)^(p-2) % p) % p

= (n! * (k! * (n-k)!)^(p-2)) % p

즉, n! 과 (k! * (n-k)!)^(p-2)를 곱한 뒤 p의 나머지를 취하면 이항계수에 p의 나머지를 취한 것과 같은 값이 나온다.

※ 여기서 하나 더 문제가 있는데, p는 상당히 큰 소수인 경우가 대부분이기 때문에 이 방법을 사용하려면

   거듭제곱을 빠르게 구하는 법도 알아둘 필요가 있다.  n의 k제곱은 n의 k//2제곱의 제곱을 구한 뒤,

   k가 홀수일 경우 n을 한번 더 곱해준 값과 같다.

   ∴ n^k = (n^(k//2)) ^ 2 * n^(k%2) 

   이 방식을 재귀적으로 적용하여 n^k 를 구하면 시간복잡도가 O(K) 에서 O(logK)로 격감한다.

이 방식을 사용하여 이항 계수 문제(https://www.acmicpc.net/problem/11401)를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
mod = 1000000007


def sol11401():
    n, k = map(int, input().split())
    if k > n//2:
        k = n-k
    A = fact(n)
    B = pow(fact(k) * fact(n - k), mod - 2)
    return A * B % mod


def pow(a, b):
    if b == 0:
        return 1
    res = pow(a, b // 2) ** 2 % mod
    if b % 2 == 1:
        res = (res * a) % mod
    return res
   
  
def fact(n):
    res = 1
    for i in range(1, n+1):
        res = (res * i) % mod
    return res


if __name__ == '__main__':
    print(sol11401())

위 코드에서는 설명한 수식을 그대로 구현하기 위해 위와같이 코드를 작성했지만 사실 n!, (k! * (n-k)!)^(p-2) 를 구하기보다는 n! / (n-k)! 과 (k!)^(p-2)를 구하는 편이 훨씬 빠르게 문제를 해결할 수 있다.  그 방식으로 작성한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
mod = 1000000007


def sol11401():
    n, k = map(int, input().split())
    if k > n//2:
        k = n-k
    A = fact(n-k+1, n)
    B = pow(fact(1, k), mod - 2)
    return A * B % mod


def pow(a, b):
    if b == 0:
        return 1
    res = pow(a, b // 2) ** 2 % mod
    if b % 2:
        return res * a % mod
    return res
   
  
def fact(a, b):
    res = 1
    for i in range(a, b+1):
        res = (res * i) % mod
    return res


if __name__ == '__main__':
    print(sol11401())

 드디어 모델을 사용하기 위한 준비가 끝났다. 이제 django 쉘을 실행하여 직접 모델의 인스턴스를 생성하고 데이터베이스에 저장, 조회하는 작업을 해보자.

1. django shell

 아래 명령어를 실행하여 django 쉘을 실행할 수 있다.  장고 쉘은 python 인터프리터와 유사한 환경이며 실제로 파이썬 문법도 사용가능하다. 

python manage.py shell

2. Question 생성

pybo\models.py 에 정의된 Question 과 Answer 모델(클래스), timezone 모듈을 import 한 뒤  Question 모델의 인스턴스를 하나 만들어본다. timezone 은 생성시간을 넣어주기 위해 사용하였다.  q.save()를 실행하면 데이터베이스의 Question 모델 인스턴스 리스트에 추가된다. 이 때, q.id 를 출력해보면 어떤 숫자가 나오는데, 이 id는 인스턴스가 생성될 때 마다 자동으로 생성/부여되는 고유키이다.  필자의 경우 기존에 3개의 Question 인스턴스가 저장된 상태이기에 새로 생성한 질문의 id는 4가 되었다. 

3. Question 조회

이제 생성한 Question 모델을 조회해 볼 차례이다.  Question.objects.all() 을 실행하면 위와 같이 저장된 Question 모델의 인스턴스들을 쿼리셋 객체의 형태로 반환한다. 각 오브젝트 옆에 (숫자)가 붙어있는데, 이는 각 인스턴스의 id번호를 의미한다. 여기에 표시되는 부분은 모델을 정의한 pybo\models.py 를 수정하여 바꿀 수도 있다.

모델을 정의한 클래스에 __str__ 메소드를 구현해줄 경우, 그 클래스의 인스턴스를 문자열화 할 때의 결과를 컨트롤 할수 있다. 위와같이 자신의 제목을 반환하도록 메소드를 구현해보자.

그 후에 다시 Question의 오브젝트들을 조회해보면 id대신 그 질문의 제목이 표시되는 것을 확인할 수 있다. 모델에 새로운 메소드를 추가할 경우에는 makemigrations와 migrate를 수행할 필요 없이 django shell만을 재실행하면 적용이 된다. migrate가 필요한 경우는 모델의 속성이 변경된 경우 뿐이다.

이제 Question 중 원하는 것만을 조회하는 방법을 알아보자.

조건에 맞는 오브젝트를 조회하기 위한 방법으로 filter를 사용하는 방법과 get을 사용하는 방법 두 가지가 있다.  위에서 보다시피 filter를 사용한 경우엔 쿼리셋이, get을 사용한 경우엔 단순히 Question 오브젝트 하나가 반환되었다.  이는 filter는 조건에 맞는 모든 오브젝트들을 반환하고, get은 조건에 맞는 단 하나의 오브젝트만을 반환하기 때문이다.  그렇기 때문에 get으로 조회하려면 조건이 될 속성은 오브젝트마다 유일한 값이어야한다. 

필터의 경우 사용법만 알면 굉장히 다양한 조건으로 데이터를 추려낼 수 있다. 필터의 자세한 사용법은 장고 공식문서(https://docs.djangoproject.com/en/3.0/topics/db/queries/)를 참고하는 것이 좋다.

4. Question 수정/삭제

다음은 이미 저장된 데이터의 수정이다.  위와 같이 수정하려는 데이터를 가져온 뒤 수정하려는 속성 값을 변경, save()를 다시한번 실행해주면 수정된 데이터가 반영된다.  save()까지 실행해주지 않으면 변경사항은 적용되지 않는다.

삭제는 더욱 간단하다. 수정과 마찬가지로 Question에서 삭제할 데이터를 가져온 뒤 delete()를 실행해주면 데이터는 삭제된다.

5. Answer의 작성/조회

Answer 모델의 데이터를 작성하는 것도 Question과 같은 방식으로 진행한다.  다만 Answer의 경우 생성을 위해 Question이 필요하기 때문에 먼저 매칭될 Question 데이터를 하나 가져온 뒤 작성한다.

조회 또한 같은 방식으로 하면 된다.  Answer 데이터에는 question 속성이 연결되어있기 때문에 어느 질문에 대한 답인지도 확인 가능하다.  그렇다면 Question 데이터를 가지고있을 때 그에 대한 Answer 데이터들을 조회하는 것도 가능할까?

Answer에 Foreign Key 로 Question 모델이 연결되어있기 때문에 Question 데이터에서 answer_set을 사용하여 연결된 Answer 데이터들에 접근할 수 있다.  이는 django에서 기본적으로 지원하는 기능이기에 사용자가 별도로 신경써야할 부분은 없다.  Foreign Key로 연결된 데이터에서 연결모델명_set 은 자주 사용되는 기능이니 반드시 기억해둘 필요가 있다.

 django 에서는 데이터베이스를 활용하기 위해 ORM(Object Relational Mapping)과 모델(Model)을 사용한다.  ORM 방식을 사용하면 데이터의 모델과 데이터베이스의 데이터를 매핑, 자동으로 SQL문을 생성하는 것으로 사용자가 직접 쿼리문을 작성하지 않아도 데이터의 저장과 조회가 가능하다.  SQL문이 아니라 사용하는 언어의 메소드와 클래스 등을 통해 데이터베이스를 조작할 수 있기 때문에 사용도 편하고 코드의 가독성도 높아진다. 이러한 특성상 DBMS의 교체가 이루어지더라도 프로그램적인 리스크가 매우 적으며 쿼리문을 잘못 작성하여 성능상의 심각한 불이익이 생기는 경우도 줄어든다.  이번에는 django에서 모델과 ORM을 사용하여 데이터베이스를 활용하는 방법을 알아본다.

1. Migration

 config\settings.py 를 열어보면 위와같은 내용이 있다. 그중 붉은 테두리 안의 내용은 django 프로젝트를 생성하면 자동으로 설치되는 앱(app)들의 목록이다.  이 중 admin, auth, contenttypes, sessions 앱들은 데이터베이스가 필요한 앱이기 때문에 migration을 필요로 한다.  django 에서 migration 이란 모델의 변경 내역을 DB에 적용시키는 것을 의미한다.

모델이 추가/변경 된 후 migration을 실행할 때 마다 migrations 디렉토리에 migration 파일이 생성되고, 이는 그 migration이 발생한 시점의 모델의 구조에 대한 정보를 담고있다.  즉, 모델 구조의 버전관리 시스템이라고 볼 수 있다.

config\settings.py 를 좀더 살펴보면 위와같이 데이터베이스에 대한 내용도 있다.  디폴트 엔진은 파이썬에 내장된 SQLite용 모듈인 sqlite3으로 되어있는 것을 확인할 수 있다.  SQLite는 개발용 혹은 소규모 프로젝트용으로 사용되는 가벼운 파일기반 DB이다. 개발중에는 SQLite를 사용하여 빠르게 개발하고 실제 운영할때는 규모있는 DB로 전환하는 것이 일반적인 개발 패턴이라고 한다.  이 부분을 수정하면 사용할 데이터베이스를 변경하거나 패스워드를 설정하는 등이 가능하지만 개발단계이기에 아직은 디폴트로 사용하기로한다. 

이제 migrate를 실행하여 현재 데이터베이스를 사용하는 앱들을 위한 테이블을 만든다.

python manage.py migrate

 정상적으로 실행됐다면 Applying ~ 으로 시작하는 결과가 여러줄 출력될 것이다.  필자의 경우 이미 실행한 상태이기 때문에 migration이 발생하지 않았다.

2. 모델 작성

 이제 직접 모델을 만들어볼 시간이다.  먼저 pybo\models.py 에 모델 클래스를 정의한다.

Question 모델은 제목을 나타낼 최대길이 200자의 문자열필드와 내용을 나타낼 텍스트필드, 작성 일시를 나타낼 날짜/시간 필드를 가지며, Answer 모델은 외래키로 Question 모델을 가지며 Question이 삭제될 경우 함께 삭제되고 내용을 나타낼 텍스트 필드와 작성 일시를 나타낼 날짜/시간 필드를 가진다.  모델의 정의에 사용 가능한 다른 필드들에 대한 정보는 django 공식문서(https://docs.djangoproject.com/en/3.0/ref/models/fields/#field-types)에서 확인 가능하다.

다음은 데이터베이스 작업을 하기 위해 config\settings.py 파일에서 INSTALLED_APPS 리스트에 pybo.apps.PyboConfig 를 추가해준다.  이렇게 앱을 등록해줘야 데이터베이스 관련 작업을 할 수 있다.

모델을 작성하고 앱도 등록했으니 이제 pybo를 위한 테이블을 만들 차례이다.  모델이 새로 작성되거나 변경된 경우에는 migrate을 실행하기 전에 makemigrations 명령을 수행할 필요가 있다.

python manage.py makemigrations
python manage.py migrate

makemigrations의 경우 모델에 변경사항이 있을 때 실행하면 변경사항의 로그가 출력된다. migrate의 경우 위에서 설명했듯이 Applying~ 으로 시작되는 migration이 적용됐음을 알리는 로그가 출력된다.  필자의 경우 이미 끝나있는 상태이기에 변경사항이 없다는 메시지가 출력되었다.

 django 개발환경 구축이 끝났으니 이제 본격적으로 게시판(Jump to Django 에서는 pybo라고 명명)을 만들어나가며 django의 기능들을 익혀나가기로 한다.  이번에는 url과 view에 대해 알아본다.

1. 앱(app)의 생성

 이전 파트에서는 django의 프로젝트를 생성하여 서버를 구동하고 사이트에 접속하여 초기화면이 나오는 것을 확인하였다.  이제 우리가 원하는 화면을 띄우기 위한 작업을 할 차례이다.  이를 위해서는 app을 생성할 필요가 있다.  

django-admin startapp pybo

django-admin(django관리자) 명령어를 사용하여 앱을 생성한 뒤 생성된 앱(디렉토리)으로 이동하여 내용물을 확인해보면 위와같은 파일들이 생성된 것을 확인할 수 있다. (forms.py 따로 추가한 파일이기에 처음에는 존재하지 않는다.)

2. config\urls.py,  pybo\views.py 파일의 수정

 이제 서버를 구동한 뒤 http://localhost:8000/pybo 로 접속하면 우리가 원하는 화면이 나오도록 해야한다. 

config\urls.py 파일을 열어 다음과 같이 수정한다.

이와같이 수정하면 localhost:8000/pybo/ 가 요청되었을 때 pybo\views.py 에 정의된 index 메소드를 실행하게된다.

다음은 pybo\views.py에 가서 실행될 index 메소드를 정의한다.  여기서는 단순히 문자열 하나를 출력하는 수준의 기능만을 구현한다.

이제 사이트에 접속해보면 Hello Pybo가 출력되는 것을 확인할 수 있다.

3. url의 분리

 프로젝트 전체의 url 매핑 파일인 config\urls.py에서 위와 같이 매핑을 추가하면 pybo 앱의 기능이 추가될 때마다 config\urls.py를 수정해야 하는데, 이는 별로 좋은 방식이 아니다.  pybo 앱의 내부에도 urls.py 파일이 있는데, 여기에 pybo/ 이후의 매핑을 추가한 뒤 config\urls.py 에서는 pybo/ 로 시작하는 url의 매핑에 pybo의 urls.py를 사용하도록 하는 것이 바람직하다. 

위와 같이 django.urls.include 를 import 한 뒤 pybo/ 의 매핑에 pybo\views.py의 인덱스 메소드 대신 include('pybo.urls') 를 넘겨준다.  이제 pybo/ 로 시작하는 url의 매핑은 pybo\urls.py에 정의된 내용을 토대로 이루어지기 때문에 pybo에 기능을 추가하더라도 config\urls.py 를 수정할 일은 없어졌다.

다음은 pybo\urls.py 를 위와 같이 수정해준다.  실행했을때의 결과는 전과 달라진게 없지만 pybo의 기능추가를 위해 config\urls.py 파일을 수정할 필요가 없어졌기에 구조적으로는 더욱 깔끔해졌다.

4. Django 설치 및 프로젝트 생성

드디어 Django를 설치하고 프로젝트를 생성할 시간이다.  위와 같이 프로젝트들을 저장할 projects 디렉토리를 생성하고 디렉토리에 진입한 후 이전에 미리 생성해둔 가상환경에 진입해준다.

C:\venvs\mysite\Scripts\activate

 가상환경에 진입한 상태에서 이번에 진행하게될 프로젝트인 mysite의 디렉토리를 생성한 후 디렉토리에 진입한다.

이후 pip 모듈을 사용하여 django를 설치한다.

pip install django

위와같이 pip 버전이 최신이 아니라는 경고문구가 뜰 경우 업그레이드를 해준다.

python -m pip install --upgrade pip

이제 django-admin(장고 관리자)를 실행하여 프로젝트를 생성한다. 

django-admin startproject config .

mysite 디렉토리 내부를 확인해보면 config 디렉토리와 manage.py 가 생성된 것을 확인할 수 있다.  생성된 디렉토리는 프로젝트의 설정파일 등이 생성되어 담겨있으며 manage.py 는 django로 개발한 서버를 구동하기 위한 파일이다.  명령문의 마지막에 붙은 . 은 현재 디렉토리에서 프로젝트를 시작한다는 의미이다.

 여기까지 오면 서버를 구동시킬 수 있다.  물론 아직 배포단계가 아닌 개발단계이기에 로컬호스트(127.0.0.1)로만 접속 가능한 상태이다.  브라우저의 url창에 localhost:8000 또는 127.0.0.1:8000 을 입력하여 서버에 접속하면 위와 같은 화면을 볼 수 있다. 서버를 종료하고 싶으면 명령 프롬프트에서 Ctrl+C 를 입력하여 종료시킬 수 있다.

5. 가상환경에 쉽게 진입하기 위한 설정

 가상환경에 진입하기 위해 매번 C:\venvs\mysite\Scripts\activate 를 실행해주는 것은 매우 번거로운 일이다. 이를 해결하기 위해 간단한 설정을 해두기로 한다.

먼저 가상환경들을 모아둔 venvs 디렉토리로 이동한 뒤 mysite.cmd 파일을 생성한다.  미리 설치해둔 vim을 사용하여 쉽게 생성할 수 있다.

vi mysite.cmd

cmd 파일은 작성한 명령어를 순차적으로 실행해주는 배치파일이다.  실행시 .cmd를 생략하고 파일명으로만 실행 가능하기 때문에 간단한 쉘 명령어를 만든다는 느낌으로 작성 가능하다. 위 와같이 작성할 경우 C:\projects\mysite 디렉토리로 이동하여 가상환경에 진입하라는 의미가 된다.  @echo off 는 실행한 명령어를 프롬프트에 출력하지 않겠다는 의미이다.

이제 이 배치파일을 어느 경로에서든 이름만으로 실행 가능하도록 하기 위해 환경변수의 PATH에 추가한다. 

window+r 을 눌러 실행 창을 연 다음 "고급" 탭에서 환경변수로 들어간다.  

그 다음 사용자 변수에서 Path를 선택한 뒤 편집을 클릭한다.

새로 만들기 버튼을 누르고 mysite.cmd가 존재하는 디렉토리인 C:\venvs를 추가해준 뒤 확인을 클릭, 환경 변수 창에서 한번 더 확인을 클릭하면 환경변수의 등록이 완료되었다.  이제 어느 디렉토리에서나 mysite를 실행하는것으로 바로 가상환경에 진입 가능하게 되었다.

6. PyCharm의 설치 및 django 개발환경 세팅

 이제 django로 보다 편하게 개발하기 위해 Python IDE인 PyCharm을 설치하고 개발환경을 세팅한다.

PyCharm의 설치는 공식 다운로드 페이지(https://www.jetbrains.com/ko-kr/pycharm/download/#section=windows) 에서 Community 버전(Professional 버전은 유료)을 다운로드 받아 설치를 진행하면 된다.  별도로 손댈 것 없이 next 만 클릭해도 설치가 완료된다.

설치가 완료되면 위와같은 화면을 볼 수 있다.  open 을 클릭하여 우리가 생성했던 django 프로젝트 디렉토리인 C:\projects\mysite 를 선택하면 PyCharm의 프로젝트 화면이 열린다. (위 스크린샷은 다른 경로에 만든 프로젝트이기에 경로가 조금 다르다.)

이제 Python 인터프리터를 잡아주기 위해 File > Settings 로 들어간다.

Project: mysite의 Project Interpreter 탭에서 우측 상단의 톱니바퀴 모양 버튼을 클릭한 뒤 Add 를 클릭한다.

미리 만들어둔 가상환경을 사용하기 위해 Existing environment 에 체크한 뒤 Interpreter 경로를 가상환경을 생성한 경로의 python.exe 파일의 경로로 설정해준다. ok를 누르면 인터프리터의 설정이 완료되고 이제 PyCharm이 우리가 생성한 가상환경 내의 Python 인터프리터를 인식한다.  이것으로 django 로 웹 서버를 개발하기 위한 준비가 모두 갖춰졌다.

7. 언어/시간 변경

 필수적인 사항은 아니지만 프로젝트의 config 디렉토리 내에 있는 settings.py 를 조금 수정하여 언어와 시간을 수정할 수 있다.  setting.py의 내용 중 LANGUAGE_CODE = 'en-us'  ,  TIME_ZONE = 'UTC' 라는 부분이 있다.

이 부분을 LANGUAGE_CODE = 'ko-kr'  ,  TIME_ZONE = 'Asia/Seoul' 로 바꿔준 뒤 다시 서버를 구동하여 접속해보자

python manage.py runserver

영어였던 초기화면이 한글로 변경된 것을 확인할 수 있다.

 나머지에 관한 문제일 경우 모듈러 연산의 성질에 대해 알고있으면 쉽게 해결 가능한 문제들이 많다.

이번에는 모듈러 연산의 성질을 활용하여 문제를 해결해본다.

1. 모듈러연산의 덧셈, 뺄셈, 곱셈

(A + B) % C = ((A % C) + (B % C)) % C
(A - B) % C = ((A % C) - (B % C)) % C
(A * B) % C = ((A % C) * (B % C)) % C

 모듈러 연산의 덧셈, 뺄셈, 곱셈에는 분배법칙이 성립한다.  이 성질을 응용하여 수학적으로 해결 가능한 문제도 있으며, 매우 큰 수를 구하는 문제에서 모듈러연산을 취한 값을 반환할 것을 요구할 경우, 단순히 최종값을 구한 뒤 모듈러 연산을 하게되면 자료형의 표현범위에 한계가 있는 언어일 경우 오버플로우가 발생할 수 있으며 Python 처럼 자료형의 표현범위에 제한이 없더라도 메모리 초과 등의 문제가 발생할 수 있기때문에 모듈러 연산의 분배법칙을 이용하여 연산 중간중간에 모듈러 연산을 취해주는 것으로 문제를 해결할 수도 있다.

모듈러 연산의 분배법칙을 활용하여 문제(https://www.acmicpc.net/problem/2981)를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol2981():
    n, *seq = map(int, input().split())
    g, *diff = [abs(seq[i]-seq[i-1]) for i in range(1, n)]
    for d in diff:
        g = gcd(g, d)
    res = {g}
    for i in range(2, int(g**.5)+1):
        if g % i == 0:
            res.add(i)
            res.add(g//i)
    return ' '.join(map(str, sorted(res)))


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


if __name__ == '__main__':
    print(sol2981())

 모든 수를 나누었을 때 나머지가 같다는 것을 식으로 나타내면 n개의 수를 A1, A2, ... , An 이라 할 때, 

A1 % m = k

A2 % m = k

A3 % m = k

...

와 같은 형태가 된다.

이 때, 인접한 수들끼리 뺄셈을 취하면 Ax % m - A(x-1) % m = 0 과 같은 형태가 된다.  m은 1보다 크기 때문에,

(Ax % m - A(x-1) % m) % m = 0 이 성립한다.  분배법칙에 따라 이는 (Ax - A(x-1)) % m = 0 이 된다. 즉, m은 n개의 수들의 차들의 공약수중 2 이상인 수가 된다.  이를 구하기 위해 인접한 수들의 차를 모두 구한 뒤, 그 차들의 최대공약수를 구한다.  이후 최대공약수의 약수를 모두 구하여 오름차순 정렬한 것이 답이된다.