굳건하게

안녕하세요.

여행벌입니다.

오늘은 세 점이 주어졌을 때, 방향성을 파악할 수 있는 CCW 알고리즘에 대해 다뤄보겠습니다.

다음과 같이 세 점 A, B, C 가 있을 때, 세 점의 방향성을 시계방향 / 반시계방향 / 일직선 3가지로 나눌 수 있습니다.

그렇다면 세 점이 주어졌을 때, 어떻게 시계방향인지 반시계 방향인지 일직선인지 구분할 수 있을까요?

우리가 잘 알고 있는 직선의 방정식을 이용해서 쉽게 구분할 수 있습니다.

[결론]

int CCW(int x1, int y1, int x2, int y2, int x3, int y3){
	int temp1 = (y2 - y1) * (x3 - x1) + y1 * (x2 - x1);
	int temp2 = (x2 - x1) * y3;

	if (temp1 < temp2) // 반시계
		return 1;
	else if (temp1 > temp2) // 시계
		return -1;
	else // 일직선
		return 0;

}

[증명]

A점 (x1, y1) /  B점 (x2, y2) / C점 (x3, y3) 가 주어졌다고 해보겠습니다.

아래 그림과 같이 AB점을 지나는 직선으로 평면을 두 개로 나눴을 때,

어느 쪽에 C점이 있느냐에 따라 시계방향인지 반시계 방향인지 판단할 수 있습니다.

[AB직선의 방정식]

-AB 직선의 기울기가 양수.

먼저 기울기가 양수인 경우, AB 직선의 방정식에 C점의 X 좌표인 x3를 대입했을 때, 얻어낸 y 값이

y3랑 같다면 직선 위

y3보다 작다면 반시계방향,

y3보다 크다면 시계방향인 것을 확인할 수 있습니다.

x2 - x1이 양수이므로 x2 - x1을 양변에 곱해도 부등호는 변하지 않습니다.

-AB 직선의 기울기가 음수.

위 그림은 반대로 직선의 방정식에 x3를 대입해서 얻은 y 값이 

y3랑 같다면 직선 위

y3보다 작다면 시계방향,

y3보다 크다면 반시계방향인 것을 확인할 수 있습니다.

하지만 이때, x2 - x1 은 음수이므로 양변에 x2 - x1을 곱해주면 부등호 방향이 바뀌어 위에서 얻어낸 식과 같아집니다.

세 점의 방향성을 알려주는 알고리즘을 'CCW 알고리즘' 이라고 합니다.

CCW 알고리즘을 기반으로 한 여러 기하 알고리즘이 많기 때문에 익혀두시는 게 좋을 것 같습니다!

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

오늘은 알고리즘 문제를 풀 때 자주 쓰이는

각 자릿수 구하기 알고리즘에 대해서 포스팅해보도록 하겠습니다.

알고리즘 문제를 풀다 보면, 어떤 정수의 각 자릿수를 구해야 하는 경우가 자주 생깁니다.

예를 들어, 5자리 정수 54321이 Input으로 들어온다고 가정해봅시다.

54321이라는 값이 들어오면 우리는 5, 4, 3, 2, 1 이라는 값을 구해야 되는데요.

다음과 같이 구할 수 있습니다.

5 = 54321 / 10000

4 = ( 54321 % 10000 ) / 1000

3 = ( 54321 % 1000 ) / 100

2 = ( 54321 % 100 ) / 10

1 = ( 54321 % 10 )

간단한 규칙이 보이시나요? %와 / 을 이용해 자릿수를 간단하게 다룰 수 있습니다.

다른 예시를 하나 더 다뤄볼까요?

9236715 라는 값이 들어오면 위의 알고리즘을 어떻게 변형하면 될까요?

9 = 9236715 / 1000000

2 = ( 9236715 % 1000000 ) / 100000

3 = ( 9236715 % 100000 ) / 10000

6 = ( 9236715 % 10000 ) / 1000

7 = ( 9236715 % 1000 ) / 100

1 = ( 9236715 % 100 ) / 10

5 = ( 9236715 % 10 )

다음과 같이 구할 수 있습니다.

지금 예시들은 다 몇 자리 숫자인지 미리 알고 있는 경우인데요.

보통 알고리즘 문제는 Input의 범위가 다음과 같이 정해져 있습니다.

Input : N , 1 ≤ N ≤ 100,000

그렇다면 이런 상황에서는 어떻게 알고리즘을 구현할 수 있을까요?

다음과 같이 코드를 구현할 수 있습니다.

#include<iostream>

using namespace std;

int list[6];

int main(void) {
	// 1 ~ 100,000 사이의 숫자가 Input으로 들어온다.
	int ninput;
	cin >> ninput;
	// 2자리 ~ 6자리 숫자는 각 자릿수를 구해서 출력해준다.
	list[0] = ninput / 100000; // 십만의자릿수
	list[1] = (ninput % 100000) / 10000; //만의자릿수
	list[2] = (ninput % 10000) / 1000; //천의자릿수
	list[3] = (ninput % 1000) / 100; //백의자릿수
	list[4] = (ninput % 100) / 10; //십의자릿수
	list[5] = (ninput % 10); //일의자릿수

	for (int i = 0; i < 6; i++) {
		cout << list[i] << ' ';
	}
}

최대 자릿수를 안다면 항상 다음과 같이 코드를 구현해 배열에 각 자릿수를 저장할 수 있습니다.

하지만 언뜻 보기에는 6자리 숫자가 들어오면 문제가 없지만, 1~5자리 숫자가 들어오면 문제가 있어 보입니다.

다음 예시를 통해서 1 ~ 5 자리 숫자가 들어오면 알고리즘이 어떻게 작동하는지 알아보겠습니다.

4321 이라는 4자리 숫자가 들어왔다고 가정해봅시다.

list[0] = 4321 / 100000 = 0

list[1] = (4321 % 100000) / 10000 = 0

list[2] = (4321 % 10000) / 1000 = 4

list[3] = (4321 % 1000) / 100 = 3

list[4] = (4321 % 100) / 10 = 2

list[5] = (4321 % 10)  = 1

다음과 같이 배열에 저장이 됩니다.

즉 Ninput보다 큰 자릿수에는 0이 저장되는 것을 확인할 수 있습니다.

이 알고리즘을 잘 활용하면 다음과 같은 문제들을 쉽게 해결할 수 있습니다.

https://www.acmicpc.net/problem/14954

오늘 포스팅은 여기서 마치겠습니다.