프로그래밍을 일상 생활속으로

 브랜치가 포함된 두 배관 라인을 비교하는 방법입니다. 아래와 같이 두 배관 라인이 존재할때 바뀐 부분을 찾는 로직입니다. 이 두 라인을 비교하기 위해 문자열 diff 알고리즘을 적용할 수 있습니다. 먼저 라인을 구성하는 항목들을 코드화 시킵니다. 두 라인을 문자열로 표현하면 $OLD = PRPTPRPBPOPRP$ $NEW = PRPRPBPOPRPTP$ 가 됩니다. 이제 배관 라인을 두 문자열로 만들었으니 문자열 diff 알고리즘을 적용시킬 차례입니다. LCS(Longest Common Subsequence)를 이용하여 두 문자열을 비교합니다. LCS는 다음 식으로 표현됩니다. $$LCS(X_i,Y_j) = \begin{eqnarray} \left\{ \begin{aligned} &0 && if\text{ }i = 0\text{ }or\text{ }j=0\\ &LCS(X_{i-1},Y_{j-1})+1 && if\text{ }X_i=Y_j\\&max(LCS(X_i,Y_{j-1}),LCS(X_{i-1},Y_j)) && if\text{ }X_i \neq Y_j \end{aligned} \right. \end{eqnarray}$$ $X,Y$는 비교할 문자열이고 $i,j$는 문자열의 인덱스입니다. 위 식을 이해하기 쉽게 2차원 배열로 나타내면 아래와 같습니다. 가장 큰 숫자인 11이 공통 부분 수열의 길이가 됩니다. 1에서 11까지 비용($Cost\text{ }=\text{ }i+j$)이 가장 작은 위치의 숫자를 선택하여 그 위치의 문자를 연결하면 공통 부분 수열이 됩니다.(공통 부분 수열은 하나가 아니라 여러개가 나타날 수 있습니다.) 공통 부분 수열은 $PRP\text{ }RPBPOPRP$(동그라미 친 부분)이며 변경이 일어나지 않은 부분입니다. 해석을 해보면 $OLD$에서 가운데 $TP$가 삭제되고 $NEW$에서 맨 끝에 $TP$가 추가되었습니다. 두 라인에서 브랜치가 변동이 없는 경우에는 두...

   Graph 형식의 데이타를 서로 겹치지 않게 도면에 펼치는 방법에 대한 내용입니다. 우선 생각이 드는 것은 우선 도면에 흩뿌려놓고 겹치는 부분이 있으면 겹치지 않게 서로 이동하는 것입니다. 모든 항목들이 서로 겹치지 않을때까지 이동하는 겁니다. 말은 쉽지만 그 결과가 어떨지 예측이 되지 않습니다.(시간은 얼마나 걸릴지, 모양은 어떻게 나올지…) 그래서 생각해본 것은 항목의 Bounding Box를 통하여 차지하는 영역을 예측하여 펼치는 방안입니다. 서로 직교하면서 지그재그 방식으로 펼쳐보도록 하겠습니다. 바로 이렇게요. 우선 하나의 라인을 선택합니다. 선택한 라인에 붙어 있는 브랜치 라인의 영역을 구합니다. 라인은 공간을 좌,우로 분할하고 홀수 브랜치는 좌, 짝수 브랜치는 오른쪽에 두게 되면 홀수 브랜치와 짝수 브랜치는 서로 겹쳐지지 않게 됩니다. 짝수 혹은 홀수 브랜치끼리 겹쳐지지 않도록 펼치면 됩니다. 위 그림에서 브랜치 3의 위치를 브랜치 3의 위치 = 브랜치 1의 위치 + 브랜치 1의 오른쪽 폭(A) + 브랜치 3의 왼쪽 폭(B) 이렇게 설정하면 브랜치 1과 3은 서로 겹쳐지지 않게 됩니다. 브랜치 3의 위치를 정한 후 브랜치 5가 있다면 브랜치 5의 위치 = 브랜치 3의 위치 + 브랜치 3의 오른쪽 폭 + 브랜치 5의 왼쪽 폭 로 정하면 브랜치 3과 브랜치 5는 서로 겹쳐지지 않게 됩니다. 이를 일반화시키면 브 랜 치 ( i + 1 ) ∗ 2 = 브 랜 치 i ∗ 2 의 위 치 + 브 랜 치 i ∗ 2 의 오 른 쪽 폭 + 브 랜 치 ( i + 1 ) ∗ 2 의 왼 쪽 폭 으로 브랜치의 위치를 구하면 됩니다. 여기서 브랜치 1의 영역을 구하기 위해서는 브랜치 1에 연결되어 있는 브랜치들의 영역을 구해야 합니다. 이것도 일반화시키면 Graph의 깊이 탐색을 하여 말단 노드의 영역을 구한 뒤 합하여 상위 노드의 영역을 구하면 됩니다. 브랜치 1의 영역은 다음과 같은 식으로 표현됩니다.  $$\begin{Bmatrix}\beg...