공부정리

 mysite 프로젝트의 목표는 Django를 활용하여 간단한 게시판형태의 웹 앱을 만들어보는 것이다.  이번에는 우선 이 프로젝트를 위해 필요한 환경 세팅을 해보기로 한다. 이 프로젝트는 전적으로 Windows 환경에서 이루어진다.

1. Python의 설치

 필자는 기존에 Python을 사용하고 있었기 때문에 이미 설치가 되어있지만 완전히 제로상태에서 프로젝트를 시작하는 것을 상정하여 Python의 설치부터 시작하기로 한다. 

먼저 Python 공식 홈페이지 (https://www.python.org/) 에 접속하여 Downloads 탭에 커서를 가져가면 위와 같이 최신 버전의 Python 인스톨러를 다운로드 받을 수 있다.

인스톨러를 실행하여 ③의 체크박스를 체크해준다. 이렇게하면 별도로 환경변수에 Python의 경로를 추가해주지 않아도

어느 위치에서나 커맨드를 통해 Python을 실행할 수 있다. 그리고 ④의 Customize installation을 클릭한다.

Install Now를 클릭하여 바로 설치해도 좋지만 Python3의 기본 설치경로는 보다시피 매우 길어 찾아가기에 불편하다.

별도로 건드릴 것 없이 next를 클릭해준다.

⑥의 Browse를 클릭하여 경로를 좀더 간단하게 바꿔준다. 필자의 경우 C:\Python39로 설정하였다.

이후 ⑦의 install을 클릭하면 설치가 시작된다.

2. Python 가상환경의 구축

 Python은 하나의 데스크탑에서 서로 다른 버전의 프로그램이나 라이브러리 등을 사용할 수 있도록 독립된 가상 환경을 구축할 수 있는 기능을 제공한다.  이 프로젝트에서는 큰 의미를 가지지는 않지만 웹 개발을 위해서 꼭 알아둬야 할 기능이라고 하니 제대로 사용하여 프로젝트를 진행해보기로 한다.

① 가상 환경들을 저장해둘 디렉토리를 생성한다. 이름은 virtual environments의 줄임말로 venvs로 하기로 한다.

mkdir venvs

② 생성한 venvs 디렉토리로 이동한다.

cd venvs

③ Python의 모듈 venv를 사용하여 가상 환경 mysite를 생성한다.

python -m venv mysite

④ dir 명령어를 사용하여 mysite 디렉토리(가상환경)가 생성된 것을 확인할 수 있다.

dir

3. vim 에디터 설치

 이후의 진행을 위해서는 텍스트 에디터가 필요하다. 환경이 윈도우인 만큼 일일히 메모장 등을 열어서 편집할 수도 있지만 명령 프롬프트 상에서 작업을 바로바로 할 수 있는쪽이 편하기 때문에 vim 에디터를 설치하기로 한다.

 먼저 vim 공식 홈페이지(https://www.vim.org/)에 접속하여 ①의 다운로드 탭을 클릭한다.

그 다음 ②의 current stable version 이라고 소개된 링크를 클릭하면 인스톨러를 다운받을 수 있다.

next를 클릭한다.

④의 동의여부에 체크한 뒤 next를 클릭한다.

⑥의 Create .bat files에 체크한 뒤 next를 클릭한다.  이 항목에 체크하면 별도의 설정없이 vim을 명령 프롬프트에서 사용 가능하다.  이후는 계속해서 next를 클릭한 뒤 install을 클릭해주면 설치가 끝난다.

 Python을 주 언어로 잡았으니 Django 나 Flask중 하나를 배워볼 생각이었는데 입문자가 배우기엔 Django가 낫다는 의견이 많이 보여서 간단한 프로젝트를 통해 Django를 배워보기로 했다.  자료는 구글링으로 여러곳을 참고하긴 했지만 기본적으로는 WikiDocs의 점프 투 장고(https://wikidocs.net/book/4223)의 프로젝트를 따라해보기로 했다.  

 코딩테스트의 문제들을 풀다보면 어느정도의 수학적 지식을 요구하는 문제들이 종종 등장한다.  이번에는 그 중에도 최대공약수(GCD)와 최소공배수(LCM)에 대해 알아본다. 

1. 최대공약수(Greatest Common Divisor)

 어떤 두 수의 최대공약수는 두 수의 공통 약수중 가장 큰 것이다.  단순히 두 수중 작은쪽부터 시작해서 수를 점점 줄여나가며 처음으로 발견되는 공통 약수를 구하는 방법도 있지만 이 방법은 숫자의 크기가 크고 최대공약수가 작을수록 굉장히 많은 시간을 소요한다.   최대공약수를 보다 빠르고 간단하게 구하는 방법으로 유클리드 호제법이 있다. 

① 두 수중 큰 쪽을 A, 작은 쪽을 B라고 한다.

② A가 B로 나누어 떨어진다면 B가 두 수의 최대공약수이다.

③ 나누어 떨어지지 않는다면 A를 B로 나눈 나머지 C를 구한다

④ A = B,  B = C 로 한 뒤 ②번으로 돌아간다.

2. 최소공배수(Least Common Multiple)

 어떤 두 수의 최소공배수는 두 수의 공통 배수중 가장 작은 것이다.  최대공약수를 구하는 법을 안다면 최소공배수를 구하는 것은 매우 간단하다. 두 수를 곱한 뒤 최대공약수로 나누면 된다.  

이를 이용하여 최소공배수, 최대공약수를 구하는 문제(https://www.acmicpc.net/problem/2609)를 해결한 코드는 다음과 같다.

import sys


def sol2609():
    n, m = map(int, sys.stdin.read().split())
    # 1
    if n < m:
        n, m = m, n
    gcd = [n, m]
    # 2
    while gcd[1] != 0:
    	# 3, 4
        gcd = [gcd[1], gcd[0] % gcd[1]]
        
    print(gcd[0], n * m // gcd[0], sep='\n')
   

if __name__ == '__main__':
    sol2609()

여러개의 정점이 주어졌을 때, 간선들의 가중치의 합이 최소가 되도록 하면서 모든 정점을 연결한 형태를

최소 신장 트리(Minimum Spanning Tree)라고 한다.  가중치는 실제 문제에서 보통 거리, 비용 등의 형태로 주어진다. 

이번에는 최소 신장 트리를 생성하는 대표적인 두 가지 알고리즘을 알아본다.

1. Kruskal's Algorithm

 Kruskal's Algorithm은 n개의 정점이 주어졌을 때 n-1개의 간선을 선택하는 방식으로 MST를 구한다.

절차는 아래와 같다.

① 모든 간선을 가중치 기준 오름차순 정렬한다.

② 가장 가중치가 작은 간선부터 선택하여 트리를 만들어나간다.

③ 만약 간선이 이미 연결된 정점 간의 간선이라면 필요가 없기 때문에 넘어간다.

④ ②,③을 간선이 n-1개가 되거나 더이상 간선이 존재하지 않을 때 까지 계속한다.

⑤ n-1개의 간선을 선택하는 데 성공했다면 그 간선들이 MST를 이루는 간선들이 된다.

⑥ 그렇지 않다면 이 그래프에서는 MST를 만드는 것이 불가능하다.

이 과정에서 이미 연결된 정점간의 간선인지의 판단은 기존에 알아본 바 있는 Disjoint Set 알고리즘이 활용된다.  이를 구현하여 최소신장트리 문제를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol1197():
    v, e = map(int, input().split())
    edges = [list(map(int, input().split())) for _ in range(e)]
    # 1
    edges.sort(key = lambda x:x[2])
    u = [-1] * (v+1)
    cost = 0
    # 4
    for a, b, c in edges:
    	# 2, 3
        if union(u, a, b):
            cost += c
    # 5
    return cost

   
def union(u, a, b):
    a = find(u, a)
    b = find(u, b)
    if a == b:
        return False
    if u[a] < u[b]:
        u[a] += u[b]
        u[b] = a
    else:
        u[b] += u[a]
        u[a] = b
    return True
   

def find(u, x):
    if u[x] < 0:
        return x
    u[x] = find(u, u[x])
    return u[x]
    

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

 Kruskal's Algorithm은 모든 간선을 정렬하는 것이 필수이기 때문에 정점의 갯수에 비해 간선의 갯수가 적은 케이스에 사용하기 좋다.

2. Prim's Algorithm

 Prim's Algorithm은 n개의 정점이 주어졌을 때 가장 가까운 정점부터 하나씩 추가해나가는 방식으로 최소신장트리를 구한다. 절차는 아래와 같다.

① 정점 하나를 최소 신장 트리의 첫 정점으로 잡고 트리로부터 각 정점으로의 거리를 구한다.(초기값 INF)

② 트리에 포함되지 않은 모든 정점 중 가장 트리에 가까운 것을 선택하여 트리에 포함시키고 가중치를 더한다.

③ 추가된 정점으로부터 다른 정점까지의 거리로 트리로부터 각 정점으로의 거리를 갱신한다.

④ ②, ③을 n-1 번 반복한다.

⑤ 가중치의 합이 INF가 아니라면 최소 신장 트리가 만들어진다.  그렇지 않다면 최소 신장 트리를 만들 수 없다.

이를 구현하여 최소 신장 트리 문제(https://www.acmicpc.net/problem/20390)를 해결한 코드는 다음과 같다.

import sys


def sol20390():
    input = sys.stdin.read
    n, a, b, c, d, *vertex = map(int, input().split())
    INF = 2000000000000

    include = [False] * n
    inq = [INF] * n
    q = [(0, 0)]
    include[0] = True
    inq[0] = 0
    res = 0
    # 1
    for i in range(1, n):
        inq[i] = ((vertex[0] * a + vertex[i] * b) % c) ^ d
    # 4
    for i in range(n - 1):
        v, dist = 0, INF
        # 2
        for j in range(n):
            if not include[j] and inq[j] < dist:
                v, dist = j, inq[j]
        include[v] = True
        res += dist
        
        # 3
        for j in range(n):
            if not include[j]:
                dst = ((vertex[v] * a + vertex[j] * b) % c) ^ d if v < j else ((vertex[j] * a + vertex[v] * b) % c) ^ d
                inq[j] = min(inq[j], dst)
    # 5
    print(res)


if __name__ == '__main__':
    sol20390()

 2, 3 과정은 heapq를 사용하여 더 간단하게 만들 수도 있지만 이 문제는 메모리 제한이 16mb이기에 정석대로 트리로부터의 최단거리 배열과 반복문을 사용하여 해결하였다. Python3으로는 시간이 부족하기에 PyPy3으로 제출하였다.

 투 포인터 알고리즘은 일차원 배열상에서 두개의 포인터를 움직여 문제를 해결하는 방식을 말한다.  

일반적으로 두 개의 포인터는 각각 배열의 항목 중 하나를 가리키거나 연속구간의 시작과 끝을 나타내는 형태로 사용된다.

1. 연속구간의 합에 관한 문제

 합이 특정한 수가 되도록 하는 모든 연속 부분구간을 구하는 문제는 투 포인터 알고리즘이 사용되는 대표적 예시이다.  절차는 다음과 같다.

주어진 수열 seq 의 길이가 n 일 때, seq의 연속 부분수열 중 합이 m 이 되는 것의 갯수 answer 를 구한다면

① 주어진 수열의 시작과 끝을 나타낼 s, e(두 개의 포인터)와 구간의 합을 나타낼 t를 모두 0으로 초기화

② t에 seq[e] 를 더한다.

③ s가 e보다 커지거나 t가 m보다 작거나 같아질 때 까지 시작구간을 뒤로 이동하고 그만큼 합계를 감산

④ 연속구간의 길이가 1이 될때까지도 t가 m보다 크다면 e가 구간의 끝인 상태에선 더이상 t가 m이 될

    가능성이 없기 때문에 e += 1

⑤ ④에서 s<=e 인채로 t가 m보다 작거나 같아졌을 경우, t == m이라면 answer += 1

⑥ ②~⑤를 e가 n-1 이하일 동안 반복

⑦ 반복문이 종료된 후 answer 가 seq의 연속 부분수열 중 합이 m이 되는 것의 갯수가 된다.

아래는 이를 구현하여 문제(https://www.acmicpc.net/problem/2003)를 해결한 코드이다. 

import sys

input = sys.stdin.readline


def sol2003():
    n, m = map(int, input().split())
    seq = list(map(int, input().split()))
    
    # 1
    s, t = 0, 0
    res = 0
    
    # 6
    for e in range(n):
    	# 2
        t += seq[e]
        
        # 3
        while t > m and s <= e:
            t -= seq[s]
            s += 1
           
        # 4
        if s > e:
            continue
            
        # 5
        if t == m:
            res += 1
            
    # 7
    return res


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

2. 두 수의 합

 정렬된 수열의 양끝에서 두 개의 포인터를 좁혀가면서 두 수의 합이 특정 값과 같은 경우의 수를 찾거나 

특정 값에 가장 가까운 쌍을 찾는 등의 문제 또한 투포인터를 사용하여 해결 가능하다.  합의 특정한 수가 되는 경우의 수를 구하는 것은 매우 간단하고 투포인터를 사용하는 것 보다 쉬운 해결책도 있기 때문에 여기서는 특정 수에 가장 가까운 쌍을 찾는 문제만을 다룬다.

길이가 N인 수열 seq가 주어졌을 때, 이 중 두 수를 합한 값이 M에 가장 가까운 순서쌍을 구한다면

① seq를 오름차순 정렬

② 시작과 끝 포인터 s, e를 각각 0, N-1 로 초기화

③ 답이 될 두 수 r1, r2를 각각 0으로, M과의 차의 최솟값 d를 무한으로 초기화 

④ seq[s] + seq[e]와 M의 차가 d보다 작은 경우 r1, r2를 seq[s], seq[e]로, d를 abs(M-(seq[s]+seq[e]))로 갱신

⑤ seq[s] + seq[e] 가 M보다 작다면 s += 1, 크다면 e -= 1, M과 같다면 더이상 탐색이 필요없기 때문에 반복 종료

⑥ ④, ⑤ 과정을 s <= e인 동안 반복한다.

아래는 이를 구현하여 문제(https://www.acmicpc.net/problem/2470)를 해결한 코드이다.

import sys

input = sys.stdin.read


def sol2470():
    n, *seq = map(int, input().split())
    # 1
    seq.sort()
    
    # 2
    s, e = 0, n-1
    
    # 3
    r1, r2, d = 0, 0, float('inf')
    
    # 6
    while s < e:
        t = seq[s]+seq[e]
        # 4
        if abs(t) < d:
            r1, r2, d = seq[s], seq[e], abs(t)
            
        # 5
        if t == 0:
            break
        elif t < 0:
            s += 1
        else:
            e -= 1
    return '%d %d' % (r1, r2)


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

3. Meet in the Middle

 문제의 풀이법이 지수시간을 가질 때( ex) 2^N ) N이 조금만 커져도 해결에 엄청난 시간이 소모된다. 

Meet in the Middle은 이러한 문제를 절반으로 나누어 각각 해결하는것으로 시간복잡도를 줄이는 방식이다. 

N(1<=N<=40)개의 정수로 이루어진 수열 seq가 주어졌을 때 seq의 부분수열 중 크기가 양수이고 합이 S가 되는것의 수를 구할 경우, 단순히 모든 조합을 따진다면 2^40이라는 엄청난 시간이 필요하다. 이를 Meet in the middle 알고리즘을 활용하여 해결해본다.

① 주어진 수열을 반으로 나눈다

② 나누어진 각 수열에 대해 모든 부분 수열의 합을 구하여 dictionary에 카운트한다.(ls, rs)

③ 한쪽의 부분수열의 합이 T가 되는 경우의 수에 대해 다른 한쪽의 부분수열의 합이 S-T 가 되는 경우의 수를 곱하여 더해나간다. 

④ 만약 S가 0이라면 크기가 0인 부분수열(공집합)이 답에 포함되기 때문에 답에서 1을 빼준다.

아래는 이를 구현하여 부분수열의 합 문제(https://www.acmicpc.net/problem/1208)를 해결한 코드이다.

import sys
from itertools import combinations

input = sys.stdin.read


def sol1208():
    n, s, *seq = map(int, input().split())
    mid = n // 2
    # 1
    left, right = seq[:mid], seq[mid:]
    
    # 2
    ls, rs = {}, {}
    for c in [map(sum, combinations(left, i)) for i in range(mid + 1)]:
        for t in c:
            ls[t] = ls.get(t, 0) + 1
    for c in [map(sum, combinations(right, i)) for i in range(n - mid + 1)]:
        for t in c:
            rs[t] = rs.get(t, 0) + 1

    # 3
    res = 0
    for t in ls.keys():
        res += ls[t] * rs.get(s - t, 0)
        
    # 4
    if s == 0:
        res -= 1
        
    return res


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

Meet in the middle 알고리즘은 큰 문제를 작은문제로 나누어 해결하는 부분에서 분할정복과 비슷한 느낌이지만 문제를 재귀적으로 쪼개나가며 해결하는 방식은 아니라는점에서 차이가 있다.  

 LCS 알고리즘은 최장 공통 부분 수열(Longest Common Subsequence)과 최장 공통 부분 문자열(Longest Common Substring) 두 종류가 있다.  최장 공통 부분 수열은 공통부분의 원소가 연속이 아니어도 상관없지만 최장 공통 부분 문자열은 공통부분의 원소가 연속이어야 한다.

1. 최장 공통 부분 수열(Longest Common Subsequence)

 LCS 문제는 기본적으로 DP(Dynamic Programming)문제이다.  절차는 다음과 같다. 

1. 문자열 A와 B의 길이가 각각 N, M 일때,  (N+1) * (M+1) 크기의 배열 dp를 생성(메모이제이션을 위한 배열)

2. 1 <= i <= N ,  1 <= j <= M 인 i, j에 대해

   ① A[i-1] == B[j-1] 라면 dp[i][j] = dp[i-1][j-1] + 1

   ② A[i-1] != B[j-1] 라면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 최장 공통 부분 수열의 길이는 dp[N][M]

4. 실제 최장 공통 부분 수열을 담기 위한 배열 lcs를 생성

5. i=N, j=M 에서 시작

   ① A[i-1] == b[j-1] 이라면 lcs에 A[i-1] 추가, i -= 1,  j -= 1

   ② A[i-1] != b[j-1] 이고 dp[i][j-1] > dp[i-1][j] 라면 j -= 1

   ③ A[i-1] != b[j-1] 이고 dp[i][j-1] <= dp[i-1][j] 라면 i -= 1

6. lcs 뒤집기

3번 까지의 절차만 수행하면 LCS의 길이를 구할 수 있고 6번까지 수행하면 LCS를 직접 구할 수 있다.

아래는 위 절차에 따라 LCS 문제(https://www.acmicpc.net/problem/9252)를 해결한 코드이다. 

import sys


def sol9252(s1, s2):
    # 1
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

    # 2
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    # 3
    l = str(dp[-1][-1])

    # 4
    lcs = []

    # 5
    i, j = len(s1), len(s2)
    while dp[i][j]:
        if s1[i - 1] == s2[j - 1]:
            lcs.append(s1[i - 1])
            i -= 1
            j -= 1
        else:
            if dp[i][j - 1] > dp[i - 1][j]:
                j -= 1
            else:
                i -= 1
    
    # 6
    lcs.reverse()

    return '\n'.join((l, ''.join(lcs)))


if __name__ == '__main__':
    input = sys.stdin.read
    str1, str2 = input().split()
    print(sol9252(str1, str2))

2. 최장 공통 부분 문자열(Longest Common Substring)

 최장 공통 부분 문자열을 구하는 것은 최장 공통 부분 수열을 구하는것과 거의 유사하다. 절차는 다음과 같다.

1. 문자열 A와 B의 길이가 각각 N, M 일때,  (N+1) * (M+1) 크기의 배열 dp(메모이제이션을 위한 배열)와

   최장 공통 부분 문자열의 길이를 계산하기 위한 lcslen(= 0), 인덱스인 lcsi, lcsj 를 선언

2. 1 <= i <= N ,  1 <= j <= M 인 i, j에 대해 A[i-1] == B[j-1]일 경우

   ① dp[i][j] = dp[i-1][j-1] + 1

   ② dp[i][j] 가 lcslen 보다 크다면 lcslen = dp[i][j],  lcsi = i, lcsj = j

3. 최장 공통 부분 문자열의 길이는 lcslen

4. 실제 최장 공통 부분 문자열을 담기 위한 배열 lcs를 생성

5. i=lcsi, j=lcsj 에서 시작하여 dp[i][j]가 0이 아닐 때 까지 lcs에 A[i-1] 추가, i -= 1, j -= 1

6. lcs 뒤집기

마찬가지로 3번 까지의 절차만 수행하면 LCS의 길이를 구할 수 있고 6번까지 수행하면 LCS를 직접 구할 수 있다.

아래는 위 절차에 따라 LCS 문제(https://www.acmicpc.net/problem/5582)를 해결한 코드이다.  원래 문제에서는 LCS의 길이만을 구하지만 여기서는 제출한 것에서 코드를 조금 변형하여 LCS자체도 구하였다.  파이썬은 시간, 메모리 조건이 상당히 아슬아슬하기 때문에 실제로 위 문제를 해결하려면 dp배열을 N * M이 아니라 N * 2 로 제한하여 재활용하는 형태로 제출해야했다.

import sys

input = sys.stdin.read


def sol5582():
    a, b = input().split()
    # 1
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    lcslen, lcsi, lcsj = 0, 0, 0
    
    # 2
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > lcslen:
                    lcslen, lcsi, lcsj = dp[i][j], i, j

	# 3
    l = str(lcslen)
    
    # 4
    lcs = []
    
    # 5
    while dp[lcsi][lcsj]:
        lcs.append(a[lcsi-1])
        lcsi -= 1
        lcsj -= 1
       
    # 6   
    return '\n'.join((str(lcslen), ''.join(lcs[::-1])))


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

  Disjoint Set 은 서로 중복되지 않는 부분집합들을 저장, 관리하기 위한 자료구조이다. 

간단한 예시로 A = {1, 2, 3, 4, 5} 에 대해서  B = {1, 3},  C = {2, 4, 5} 라면 B와 C가 A의 disjoint set이 된다. 이 disjoint set을 활용하여 문제를 해결하는 방식이 이번에 알아볼 disjoint set 알고리즘이 되겠다. 집합을 서로 중복되지 않는 부분집합들로 분할하기 위한 핵심 연산이 union 과 find 연산이기에 Union-Find 알고리즘이라고도 부른다.

1. 집합의 표현

  Disjoint Set을 표현하는 데는 여러 방법이 있지만 가장 간단하고 효율적인 트리를 사용하는 방법을 알아본다.

disjoint_set = [-1] * (node_num + 1)

 먼저 각 노드의 부모 노드를 관리하는 리스트(배열)를 선언한다.  자기자신이 루트노드인 경우에는 해당 트리에 속한 자신을 포함한 노드의 갯수에 음수를 취한 값을 저장한다.  아직 분할이 이뤄지지 않은 처음에는 모두가 자기 자신만이 존재하는 트리의 루트노드이기에 초기값을 -1로 한다.

def union(disjoint_set, A, B):
    A = find(disjoint_set, A)
    B = find(disjoint_set, B)
    
    if A != B:
    	if disjoint_set[A] < disjoint_set[B]:
            disjoint_set[A] += disjoint_set[B]
            disjoint_set[B] = A
        else:
            disjoint_set[B] += disjoint_set[A]
            disjoint_set[A] = B

 다음은 union 연산의 구현이다.  A 와 B에 대해 find 연산을 통해 A와 B가 속한 부분집합의 루트 노드를 구한다.

만약 두 루트노드가 서로 같다면 A와 B는 이미 같은 집합에 속한 원소이기에 더이상 union 연산을 진행할 필요가 없다.

서로 다르다면 한쪽의 루트노드가 다른 한쪽의 자식 노드로 추가되어야 한다. 이 때, 보다 깊이가 큰 노드에 작은 노드가 매달려야 트리의 깊이를 최소화할 수 있기에, disjoint_set 값이 보다 작은쪽에 큰 쪽을 추가한다. (루트노드의 disjoint_set 값은 트리의 크기에 음수를 취한것이기 때문에 그 값이 더 작다는 것은 트리의 크기(깊이)가 더 크다는 것을 의미한다.) 

def find(disjoint_set, x):
    if disjoint_set[x] < 0:
        return x
    disjoint_set[x] = find(disjoint_set, disjoint_set[x])
    return disjoint_set[x]

 마지막으로 find 연산의 구현이다.  만약 x의 disjoint_set 값이 음수라면 자신이 루트노드이기 때문에 스스로를 반환한다.

음수가 아니라면 자신의 부모노드에 대해 find 함수를 재귀호출하여 루트노드를 구하여 반환한다.  이 때, disjoint_set[x] 를 루트노드로 갱신하여 트리의 깊이를 낮추는 것으로 find 연산에 걸리는 시간을 단축할 수 있다.

 Disjoint Set 은 여러개의 노드간의 연결관계가 주어질 때 그 노드들이 같은 네트워크에 속하는지 알아내는 종류의 문제에 유용하다. 아래는 그와같은 유형의 문제(https://www.acmicpc.net/problem/4195)를 Disjoint Set을 사용하여 해결한 코드이다.

import sys

input = sys.stdin.readline


# 4195 친구 네트워크
# 친구관계 (연결관계)가 주어질 때마다 친구네트워크의 크기, 즉 친구가 된 둘이 속한 친구집합의 크기를 구하는 문제
def sol4195():
    answer = []
    for t in range(int(input())):
        # 친구의 이름에 매칭되는 숫자를 저장
        friend = {}
        u = []
        res = []
        for _ in range(int(input())):
            # 서로 친구가 된 두 명의 이름
            a, b = input().split()
            
            # 처음 등장한 이름이 있다면 번호를 매겨주고 새로운 부분집합으로 추가한다
            if a not in friend:
                friend[a] = len(friend)
                u.append(-1)
            
            if b not in friend:
                friend[b] = len(friend)
                u.append(-1)
                
            # 두 사람이 속한 친구 네트워크를 합치기 위해 union 연산 실행
            a = friend[a]
            b = friend[b]
            
            # 두 사람이 속한 친구 네트워크의 크기를 구함
            res.append(-union(u, a, b))
        answer.append('\n'.join(map(str, res)))
    return '\n'.join(answer)


# union 연산
def union(u, a, b):
    a = find(u, a)
    b = find(u, b)
    if a != b:
        if u[a] < u[b]:
            u[a] += u[b]
            u[b] = a
            return u[a]
        else:
            u[b] += u[a]
            u[a] = b
            return u[b]
    return u[a]
   

# find 연산
def find(u, x):
    if u[x] < 0:
        return x
    u[x] = find(u, u[x])
    return u[x]

 또한 노드간의 연결이 계속해서 주어질 때, 사이클이 발생하는 연결인지의 탐지 또한 가능하다.  중복되지 않는 두 부분집합간의 union 에서는 사이클이 발생하지 않지만 이미 같은 부분집합에 속한 두 노드가 연결될 경우 둘 사이의 경로가 하나 더 생기기 떄문에 사이클이 발생한다.   아래는 사이클의 발생을 탐지하는 문제(https://www.acmicpc.net/problem/20040)를 Disjoint Set으로 해결한 코드이다.

import sys

input = sys.stdin.readline


# 20040 사이클 게임
# 주어진 점들을 선분으로 이어나가며 사이클이 생기는 차례를 구하는 문제
# 사이클이 생기려면 이미 같은 집합(네트워크)에 속해있는 점끼리 이어져야 한다.
# 이를 이용하면 유니온 파인드를 통해 간단히 해결 가능하다.
def sol20040():
    n, m = map(int, input().split())
    u = [-1] * (n + 1)
    check = 0
    for turn in range(1, m + 1):
        s, e = map(int, input().split())
        if not union(u, s, e):
            check = turn
            break

    return check


def union(u, a, b):
    a = find(u, a)
    b = find(u, b)
    if a == b:
        return False
    if u[a] < u[b]:
        u[a] += u[b]
        u[b] = a
    else:
        u[b] += u[a]
        u[a] = b
    return True


def find(u, x):
    if u[x] < 0:
        return x
    u[x] = find(u, u[x])
    return u[x]

단순히 union 연산이 발생했을 때, 인자로 받은 a, b가 같은 부분집합에 속해있는 경우 그 연산이 발생한 차례를 출력하면 해결 가능한 문제이다. 

두 문제 모두 Disjoint Set에 대해 알고있다면 굉장히 쉽게 해결 가능하지만 몰랐다면 상당히 고전했을 문제들이었다.  충분히 실전에서 볼 수 있을법한 유형의 문제들이기에 Disjoint Set을 확실히 이해해둘 필요가 있겠다.

 최장 증가 부분수열은 주어진 수열의 부분수열 중 모든 원소가 이전의 원소보다 크다는 조건을 만족하는 것 중 가장 긴 것을 의미한다.  부분수열(Subsequence)은 기존 수열에서의 순서는 지켜져야하지만 연속한 수일 필요는 없다.  이번에는 주어진 수열에서 최장 증가수열과 그 길이를 찾아내기 위한 LIS 알고리즘에 대해 정리한다.

1. O(N^2)의 방법

가장 간단한 방법은 이중 for문을 돌려 동적계획법으로 구하는 것이다.

수열의 i 번째 숫자가 들어왔을 때, i-1까지의 수열들 중에 그 숫자를 추가하여 길이를 늘릴 수 있는 가장 긴 수열을 찾아 i번쨰 숫자를 덧붙인것을 i번째 수열로 한다.

점화식으로 표현한다면 dp[i] = dp[j] + [seq[i]] for j in range(i) if (seq[j] < seq[i] and len(dp[j]) +1 > len(dp[i])) 가 된다.  i-1까지의 j인덱스에서 j번째 숫자, 즉 수열의 마지막이 i번째 숫자보다 작으면서 현재 구해놓은 i번째 수열 후보보다 더 긴 경우를 찾는 것이다.  이를 구현한 코드는 다음과 같다.

import sys


def sol14002(n, seq):
    lis = [[] for _ in range(n)]
    for i in range(n):
        lis[i] = [seq[i]]
        for j in range(i):
            if seq[j] < seq[i] and len(lis[j]) + 1 > len(lis[i]):
                lis[i] = lis[j] + [seq[i]]
    res = max(lis, key = lambda x:len(x))
    return f'{len(res)}\n'+' '.join(map(str, res))


if __name__ == '__main__':
    input = sys.stdin.read
    n, *seq = map(int, input().split())
    print(sol14002(n, seq))

백준 온라인저지(Baekjoon Online Judge)의 14002번 문제(https://www.acmicpc.net/problem/14002)에 제출한 코드이다. 

2. O(NlogN)의 방법

좀 더 빠른 방법으로 LIS를 구할 수도 있다.  마찬가지로 i번째 숫자가 들어왔을 때, lis 리스트의 마지막 요소보다 i번째 숫자가 크다면 숫자를 리스트에 append, 그렇지 않다면 리스트 내의 i번째 숫자보다 크거나 같은 수 중 가장 작은 수를 i번째 수로 대체한다.  길이만을 구한다면 이것으로 충분하지만 LIS 자체를 구하려면 그 때마다 i번쨰 숫자가 차지하는 위치(인덱스)를 저장해둘 필요가 있다.  이후 그 인덱스를 통해 LIS의 각 인덱스에 들어갈 수 있는 숫자를 찾아 LIS를 알아낼 수 있다.  이를 구현한 코드는 다음과 같다.

import sys
from bisect import bisect_left

def sol14003(n, seq):
    lis, path = [], []
    for i in range(n):
        num = seq[i]
        if not lis or num > lis[-1]:
            lis.append(num)
            path.append(len(lis)-1)
        else:
            p = bisect_left(lis, num)
            lis[p] = num
            path.append(p)
    
    l = len(lis) - 1
    res = []
    for p, num in list(zip(path, seq))[::-1]:
        if p == l:
            res.append(str(num)+' ')
            l -= 1
    res.append(str(len(lis))+'\n')
    return ''.join(res[::-1])
    
    
if __name__ == '__main__':
    input = sys.stdin.read
    n, *seq = map(int, input().split())
    print(sol14003(n, seq))

백준 온라인저지(Baekjoon Online Judge)의 14003번 문제(https://www.acmicpc.net/problem/14003)에 제출한 코드이다. 

코딩테스트에서 응용될 여지가 충분해보이기 때문에 잘 기억해둘 필요가 있을 것 같다.

 Dijkstra's Algorithm이나 Bellman-Ford Algorithm이 한 정점에서 모든 정점으로의 최단거리를 구하는

알고리즘이라면 Floyd-Warshall Algorithm은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다. 

경유지점이 될 m, 시작점이 될 s, 도착점이 될 e를 각각 루프를돌며 dp[s][m] + dp[m][e] 로 최단거리를 갱신한다.

절차는 다음과 같다.

① 모든 정점간의 연결을 V * V 리스트 형태로 저장한다. (dp[i][i] == 0) 

② 먼저 경유점이 될 m을 고른 뒤(V) 시작점 s(V)와 끝점 e(V)도 각각 고른다  =>  O(V^3)  

③ dp[s][e]를 dp[s][m] + dp[m][e] 와 비교하여 갱신한다

④ 3중 반복문이 모두 돌고나면 dp[s][e] 는 s에서 e까지의 최단거리가 된다

구현이 굉장히 단순하지만 O(V^3)의 시간복잡도를 가지기에 정점의 수가 적을 때만 사용 가능한 방법이다.

특히 파이썬의 경우 작은 수의 V로도 시간초과가 나기 쉽상이니 주의할 필요가 있다.

알고리즘을 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
INF = float('inf')


def sol11404():
    n, m = int(input()), int(input())
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for _ in range(m):
        a, b, c = map(int, input().split())
        dist[a - 1][b - 1] = min(dist[a-1][b-1], c)

    for k in range(n):
        for s in range(n):
            for e in range(n):
                dist[s][e] = min(dist[s][e], dist[s][k]+dist[k][e])
    print('\n'.join([' '.join(['0' if d == INF else str(d) for d in line]) for line in dist]))


if __name__ == '__main__':
    sol11404()

백준 온라인저지(Baekjoon Online Judge)의 11404번 문제(https://www.acmicpc.net/problem/11404)에 제출한 코드이다. 

 Dijkstra's Algorithm은 O(ElogV)의 시간복잡도로 한 정점에서 모든 정점으로의 최단거리를 구할 수 있지만

음수간선이 포함된 그래프에서는 사용이 불가능하다.  음수간선이 포함된 그래프에서 최단거리를 구할 수 있으며 음수사이클도 감지 가능한 최단경로 알고리즘인 Bellman-Ford Algorithm에 대해 알아본다.

 Bellman-Ford Alogorithm은 시작점에서 모든정점으로의 최단거리를 무한으로 초기화한 후 edge를 순회하며 해당 edge를 통과하는 거리로 최단거리를 갱신해나가는 방식으로 최단거리를 구하는 알고리즘이다.

절차는 다음과 같다.

① 먼저 시작점 s로부터의 각 정점까지의 거리를 나타낼 배열 d를 INF(무한)으로 초기화한다.

② d[s]를 0으로 초기화한다 (자기 자신과의 거리는 0이기 때문에)

③ 모든 간선을 순회하며 그 간선을 통과하는 경우의 거리로 최단거리를 갱신해나간다

    ex) d[1] == 0, d[3] == INF   ->  edge : (1, 3, 5)   ->  d[3] = min(d[3], d[1]+5)  ->  d[3] == 5

④ ③을 정점의 수 - 1 회 만큼 반복한다. (그 전에 갱신이 멈추면 반복을 종료한다)

⑤ ④에서 갱신이 멈추지않고 정점의 수 - 1회까지 반복문이 돌아갔을 경우, 한번 더 간선을 순회하여

    최단거리의 갱신이 발생할 경우 음수 사이클이 있어 최단거리를 구할 수 없다는 결과를 얻을 수 있다.

Dijkstra's Algorithm 보다도 구현이 단순해서 특별히 주의할 점은 없지만 ④에서 반복문이 정점의 수 - 1만큼 돌아가기 전에도 아무 갱신이 발생하지 않으면 break를 걸어주는 것이 성능 개선에 도움이 된다.

알고리즘을 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
INF = float('inf')


def sol11657():
    n, m = map(int, input().split())
    edge = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        edge.append((a-1, b-1, c))
    
    dp = [INF]*n
    dp[0] = 0
    for v in range(n-1):
        check = True
        for s, e, t in edge:
            if dp[s] + t < dp[e]:
                dp[e] = dp[s] + t
                check = False
        if check:
            break
            
    check = False
    for s, e, t in edge:
        if dp[s]+t < dp[e]:
            check = True
            break
    print(-1 if check else '\n'.join(map(conv, dp[1:])))
   

def conv(num):
    return '-1' if num==INF else str(num)


if __name__ == '__main__':
    sol11657()

백준 온라인저지(Baekjoon Online Judge)의 11657번 문제(https://www.acmicpc.net/problem/11657)에 제출한 코드이다.