직장인의 개발 일기

1. 트라이(Trie)

트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다.

2. 트라이(Trie) 동작 원리

먼저 그림을 통해 살펴보도록 하겠습니다.

다음 그림은 문자열 {"jade", "japp", "an", "answer"}를 트라이(Trie)로 구현한 것입니다.

3. 트라이(Trie) 구현

트라이의 노드는 자손 노드를 가리키는 포인터 배열과, 문자열의 끝인지를 나타내는 bool 변수로 구성되어 있습니다.

보통 영어 소문자로만 이루어딘 경우가 대부분이기 때문에 배열의 크기를 26으로 선언합니다.

동적으로 메모리를 할당하기 때문에 delete로 해제해주는 것이 매우 중요합니다.

이제 문자열을 트라이에 넣어주는 함수에 대해 알아보겠습니다.

이미 트라이에 해당 문자에 해당하는 노드가 있다면 따라가고, 그렇지 않다면 새로 만들어줍니다.

문자열의 끝에 도달하면 end의 값을 true로 바꾸어줍니다.

마지막으로 트라이에서 찾고자 하는 문자열이 있는지 탐색하는 함수에 대해 알아보겠습니다.

만약 다음 문자로 가는 노드가 존재하지 않는다면 존재하지 않는 단어입니다.

또한, 문자열의 끝에 도달했을 때 end의 값이 true가 아니라면 존재하지 않는 단어입니다.

[ 소스코드 ]

1. 이분 매칭(Bipartite Matching)이란?

정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 이분 그래프(Bipartite Graph)라고 말합니다. 이러한 이분 그래프에서 예를 들어, 한쪽 그룹은 X 그룹, 다른 한쪽 그룹은 Y 그룹이라고 할 때 모든 경로의 방향이 X->Y인 그래프의 최대 유량을 구하는 것이 이분 매칭(Bipartite Matching)입니다.

2. 이분 매칭(Bipartite Matching)동작 원리

우선, 정점 A는 정점 1을 점유할 수 있습니다. (총 매칭 수 : 1)

그 다음 정점 B는 정점 1을 점유하려고 합니다. 그런데 정점 A가 이미 정점 1을 보유하고 있으므로 A는 다른 정점을 점유하러 경로를 다시 찾습니다. 정점 3이 비어있으므로 A는 정점 3을 점유합니다. (총 매칭 수 : 2)

정점 C는 정점 5를 점유합니다. (총 매칭 수 : 3)

정점 D는 정점 3을 점유하려고 합니다. 그런데 정점 A가 이미 정점 3을 점유하고 있으므로 A가 다른 경로를 찾아 정점 1의 점유를 시도합니다. 그런데 정점 1 역시 정점 B가 점유하고 있으므로 B는 다른 경로를 찾아 비어있던 정점 2를 점유합니다. (총 매칭 수 : 4)

정점 E가 정점 2를 점유하려고 합니다. 그러나 정점 E는 더이상 매칭할 수 없습니다. 2를 점유하면 B가 경로를 다시 찾을 것이고 또 A가 다시 경로를 찾게되며 또 D가 다시 경로를 찾고 계속해서 반복되기 때문에 매칭이 불가능합니다.

따라서 최종 매칭 수는 4가 됩니다.

오늘은 모듈러 연산에 대해 설명드리겠습니다. 특정 수 M을 넘는 수에 모듈러 연산을 하려면 어떻게 해야 할까요?

모듈러 연산의 특성을 활용하면 쉽게 구할 수 있습니다.

[ 동작 원리 ]

정수 A와 B를 M으로 나눈 나머지를 각각 a, b라고 한다면, 이때 A+B를 M으로 나눈 나머지는 얼마일까요?

A = xM + a

B = yM + b

A + B = (x + y)M + (a + b)

(A + B)%M = (a + b)%M

따라서, (A + B)%M = ((a%M) + (b%M))%M이라는 결과가 나옵니다. 이러한 성질은 덧셈, 뺄셈, 곱셈에 모두 성립합니다.

하지만 음수에 모듈러를 적용하면 다음과 같은 결과가 나옵니다.

-9 % 11 = 2

-5 % 11 = 6

-23 % 11 = 10

=>

(23%11) = 1

-1 + 11 = 10

따라서 음수는 양수로 바꾼 값을 M으로 나눈 값을 다시 음수로 바꿉니다. 그 후 그 값에 M의 값을 더해주면 음수에 모듈러를 계산한 값이 나오게 됩니다. 나눗셈을 제외한 모듈러 연산은 다음과 같이 정의할 수 있습니다.

(A + B)%M = ((a%M) + (b%M))%M

(A - B)%M = ((a%M) - (b%M) + M)%M

(A * B)%M = ((a%M) * (b%M))%M

오늘 설명할 알고리즘은 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)입니다. 조합 최적화 문제로 전산학에서 연구된 가장 유명한 문제 중 하나입니다. 이 문제의 요구사항은 간단합니다. 각 도시들을 한 번씩 방문하고, 여행을 시작한 도시로 다시 돌아오는 최단 경로를 구하는 것입니다.

외판원 순회 문제의 경우 도시(N)의 개수가 10개 이하일 때와 16개 이하일 때 2가지로 나눠서 생각할 수 있습니다.

[ 동작 원리 ]

먼저 N이 10개 이하일 때는 완전 탐색을 통하여 구할 수 있습니다. 10개의 도시를 모두 한 번씩 방문하고 시작했던 도시로 돌아오는 방법은 모두 10! = 3628800이므로 충분히 완전 탐색을 통하여 구할 수 있습니다.

여기서 가장 중요한 포인트는 시작점이 어디여도 상관이 없다는 것입니다.

예를 들어

1→2→3→4→5→1,

2→3→4→5→1→2,

3→4→5→1→2→3,

…

위의 모든 경로가 이동거리가 같은 것을 볼 수 있습니다. 하지만 위의 방법은 겹치는 경로가 많이 발생하고 이를 줄일 수 있다면 더 많은 도시를 경유할 수 있을 것입니다. 따라서 N의 개수를 16개까지 더 늘려보겠습니다.

N이 16개 이하일 때는 dp을 통하여 구할 수 있습니다. dp [ 현재 도시 ][ 방문한 도시 ] = 남은 도시들을 방문할 수 있는 최단 경로입니다. 현재 도시에서 나머지 도시들을 방문할 때 최단 경로를 저장함으로써 중복되는 계산과정을 줄일 수 있습니다.

그리고 이때 방문한 도시는 비트 마스킹을 통해서 구현합니다. 위의 그래프처럼 5개의 도시가 있다고 생각하면 모두 방문했을 때 비트는 11111일 것입니다. 만약 1번 도시를 제외하고 모든 도시를 방문했다면 11110이 됩니다.

이를 점화식으로 표현하면 dp [ 현재 도시 ][ 방문한 도시 ] = min( dp [ 현재 도시 ][ 방문한 도시 ], 현재노드에서 i번 도시까지 거리 + dp[ i ][ 방문한 도시 ] )가 됩니다.

이를 통해 다음 문제를 풀 수 있습니다.

https://rudalsd.tistory.com/37