[C++] 행렬로 점과 직선 사이의 거리 구하기

글을 작성하게 된 계기

취업 준비를 시작하며 코딩 테스트를 치르게 되었습니다. 운 좋게 면접 기회도 있었는데, 당시 면접에서 "원과 직선의 충돌 여부를 확인할 수 있는 방법"을 물었습니다. 저는 원의 중심에서 직선까지의 거리를 구하면 된다고 답변했고, 면접관께서는 실제로 그 거리를 구하는 방법을 알고 있는지 다시 물으셨습니다.

컴퓨터가 대부분 계산해주다 보니 직접 계산하는 수학을 하지 않은 지 오래되었고, 공식도 거의 잊어버린 상태였습니다. 그래서 저는 "공식의 존재를 알고 있기 때문에 검색을 통해 확인하여 충분히 구현 가능합니다"라고 답변했습니다.

당시에는 '그런 거 굳이 외울 필요 있나'라며 속으로 대수롭지 않게 넘겼지만, 결과적으로 면접에서는 떨어졌습니다. 원인은 정확히 알 수 없지만, 이러한 대답 또한 감점 요인이 되지 않았을까 싶습니다.

하지만 결정적으로 이 글을 작성하게 된 계기는 코딩 테스트였습니다. 모 회사의 코딩 테스트에서 점과 직선 사이의 거리를 구하는 문제가 출제되었습니다. 막상 시험장에서 맞닥뜨리니 공식도 기억나지 않았고, 그것을 유도하는 과정조차 떠올리지 못했습니다. '분명 아는 건데...'라는 생각으로 머리가 하얘졌고, 남은 시간 동안 노력했지만 결국 풀이를 이끌어내지 못한 채 시험이 끝났습니다.

코딩 테스트가 끝나고 스스로 많이 아쉬웠고, 자책하기도 했습니다. 제가 생각하기에도 기초적인 수학 지식인데, 이런 것조차 의존한다면 과연 '회사 입장에서 뽑고 싶은 인재일까'라는 생각이 들었습니다.

하지만 저는 공식을 무작정 외우는 것을 좋아하지 않습니다. 수학을 열심히 하던 고등학교 시절부터 지금까지, 공식만을 외우는 과정은 제가 그것을 진정으로 익혔다는 느낌을 주지 못했습니다.

그래서 이번 경험을 계기로, 공식보다는 점과 직선 사이의 거리를 구하는 과정에 대해 생각해보기로 했습니다.

---

연립방정식 유도 과정

아래 그림과 같이 점 $P(x_0, y_0)$이 주어지고, 직선의 방정식 $y = ax + b$를 알고 있다고 가정합니다.

직선의 기울기를 알고 있기 때문에, 점 $(x_0, y_0)$에서 직선까지 수선의 발을 내릴 때 생기는 직선의 기울기 또한 구할 수 있습니다. 두 직선은 직교하므로 두 직선의 기울기의 곱은 반드시 $-1$이 됩니다. 따라서 수선의 기울기는 $-\frac{1}{a}$입니다.

수선의 방정식은 다음과 같이 표현됩니다:

$y - y_0 = -\frac{1}{a}(x - x_0)$

이 과정을 통해 두 개의 방정식을 얻었습니다:

1. $y = ax + b$ (주어진 직선)
2. $y - y_0 = -\frac{1}{a}(x - x_0)$ (수선)

이제 이 연립방정식의 해를 구하면 두 직선이 교차하는 지점, 즉 수선의 발을 구할 수 있습니다. 교차점을 구한다면 점과 점 사이의 거리를 통해 점과 직선 사이의 거리를 얻게 됩니다.

---

컴퓨터적 관점에서의 문제

사람 기준으로 생각하면 방정식이 두 개인 연립방정식은 해를 구하기 상당히 쉬운 편입니다. 하지만 컴퓨터적인 측면에서 이를 다시 생각해보면 다음과 같은 문제가 있었습니다:

1. 컴퓨터는 방정식을 행렬로 이해합니다. 사람이 풀이하는 방식과 다르게 접근해야 합니다.
2. 범용성을 고려해야 합니다. 현재는 방정식과 변수가 각각 2개이지만, 개수가 증감할 수 있다는 가정하에 범용적으로 작성해야 합니다.

결국 행렬로 접근해야 한다는 것을 깨닫고, 컴퓨터에서 연립방정식을 계산할 수 있는 방법을 찾아보기로 했습니다.

---

컴퓨터에서 연립방정식의 계산

연립방정식을 컴퓨터로 푸는 방법은 크게 세 가지가 있습니다: 가우스 소거법, 역행렬 곱, LU 분해. 각 방법의 특성을 구현 관점에서 비교하면 다음과 같습니다.

1. 가우스 소거법 (Gaussian Elimination)

• 직접 구현 난이도: 중간
• 수치 안정성: 좋음 (피벗팅 사용 시)
• 계산 복잡도: $O(n^3)$

2. 역행렬 곱 (Inverse Matrix Multiplication)

• 직접 구현 난이도: 쉬움
• 수치 안정성: 나쁨
• 계산 복잡도: $O(n^3)$ + 추가 곱셈
• 문제점:
  • 부동소수점 오차 누적

3. LU 분해 (LU Decomposition)

• 직접 구현 난이도: 중상
• 수치 안정성: 좋음 (피벗팅 사용 시)
• 계산 복잡도: $O(n^3)$
• 장점: 같은 행렬 $A$로 여러 $b$ 벡터를 풀 때 효율적

여기서는 구현이 비교적 쉽고 부동소수점의 영향을 덜 받는 가우스 소거법으로 연립방정식을 해결해보겠습니다.

---

가우스 소거법이란?

연립방정식을 상삼각행렬로 만든 뒤, 아래에서 위로 대입하여 해를 구하는 방법입니다.

• 상삼각행렬: 주대각선을 기준으로 대각항의 위쪽 항들의 값이 모두 0인 경우
  

예시: 2개 변수의 연립방정식

Step 1: 확장 행렬로 표현

Step 2: 전방 소거 (Forward Elimination)

목표: 왼쪽 아래를 0으로 만들기
첫 번째 행을 이용해 두 번째 행의 $x$를 제거합니다:

Step 3: 후방 대입 (Back Substitution)

아래부터 위로 올라가며 해를 구합니다:
2번째 식:

1번째 식:

답: $x = 1, \, y = 2$

복잡해 보이지만 결국 "한 식을 다른 식에서 빼서 변수를 하나씩 제거"하는 방법입니다.

---

가우스 소거법 C++ 구현 및 설명

구현

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<double> gaussianElimination(vector<vector<double>> A, vector<double> b)
{
	int n = A.size();

	// AX = b -> AX|b 형태로 변환
	for (int i = 0; i < n; i++)
	{
		A[i].push_back(b[i]);
	}

	// 전방 소거
	for (int i = 0; i < n; i++)
	{
		// 피벗 설정
		int maxRow = i;
		for (int j = i + 1; j < n; j++)
		{
			if (abs(A[j][i]) > abs(A[maxRow][i]))
				maxRow = j;
		}

		// 행 교환
		swap(A[i], A[maxRow]);

		// 아래 행들을 0으로 만들기
		for (int j = i + 1; j < n; j++)
		{
			double factor = A[j][i] / A[i][i];
			for (int k = i; k <= n; k++)
			{
				A[j][k] -= factor * A[i][k];
			}
		}
	}

	// 후방 대입
	vector<double> x(n);
	for (int i = n - 1; i >= 0; i--)
	{
		x[i] = A[i][n];
		for (int j = i + 1; j < n; j++)
		{
			x[i] -= A[i][j] * x[j];
		}
		x[i] /= A[i][i];
	}

	return x;
}

int main()
{
	vector<vector<double>> A = { {2, 3}, {1, -1} };
	vector<double> b = { 8, -1 };

	vector<double> solution = gaussianElimination(A, b);

	cout << "해: x = " << solution[0] << ", y = " << solution[1] << endl;

	return 0;
}

---

설명

1. 확장 행렬 생성

for (int i = 0; i < n; i++)
{
    A[i].push_back(b[i]);
}

연립방정식 $AX = b$를 확장 행렬 $[A|b]$ 형태로 변환합니다. 각 행의 끝에 $b$ 값을 추가하여 행렬과 우변을 함께 처리할 수 있게 만듭니다.

예시:

2. 전방 소거 (Forward Elimination)

2-1. 피벗 선택

int maxRow = i;
for (int j = i + 1; j < n; j++)
{
    if (abs(A[j][i]) > abs(A[maxRow][i]))
        maxRow = j;
}
swap(A[i], A[maxRow]);

피벗을 정하는 이유

• 현재 열($i$번째)에서 절댓값이 가장 큰 원소를 피벗으로 선택합니다
• 0으로 나누는 오류를 방지하고 수치적 안정성을 높입니다
• 작은 값으로 나누면 부동소수점 오차가 크게 증폭되므로, 큰 값을 피벗으로 사용하여 오차를 최소화합니다

예시:

(이 경우 $|2| > |1|$이므로 교환 불필요)

2-2. 하부 행 소거

for (int j = i + 1; j < n; j++)
{
    double factor = A[j][i] / A[i][i];
    for (int k = i; k <= n; k++)
    {
        A[j][k] -= factor * A[i][k];
    }
}

상삼각 행렬을 만드는 과정:

• factor: $i$번째 행을 몇 배 해서 빼야 $j$번째 행의 $i$번째 원소가 0이 되는지 계산
• $i$번째 피벗 행 아래의 모든 행에서 $i$번째 열의 값을 0으로 만듭니다
• k <= n인 이유: 확장된 우변 $b$ 값까지 함께 처리해야 하므로

예시:

3. 후방 대입 (Back Substitution)

vector<double> x(n);
for (int i = n - 1; i >= 0; i--)
{
    x[i] = A[i][n];
    for (int j = i + 1; j < n; j++)
    {
        x[i] -= A[i][j] * x[j];
    }
    x[i] /= A[i][i];
}

맨 아래 행부터 위로 올라가며 해를 구합니다:

1. x[i] = A[i][n]: 우변 값으로 초기화
2. x[i] -= A[i][j] * x[j]: 이미 구한 $x[j]$ 값들을 대입하여 뺍니다
3. x[i] /= A[i][i]: 계수로 나누어 최종 해를 구합니다

예시:

$i = 1$ (두 번째 행):

$i = 0$ (첫 번째 행):

최종 해: $x = 1, y = 2$

---

마치며

연립방정식의 해를 구하는 과정은 복잡하고, 시간 복잡도 또한 $O(n^3)$입니다. 비록 $n$이 방정식의 개수이기 때문에 점과 직선의 거리를 구하는 경우($n=2$)에는 큰 부담이 되지 않지만, 코딩 테스트 환경에서는 점과 직선 사이의 거리 공식을 직접 사용하는 것이 훨씬 효율적입니다.

오늘의 교훈: 기초 수학을 잊지 말자!