CCW? 그게 뭔데..?

CCW 들어가기에 앞서

  • 이름만 들으면 굉장히 어려운 CCW, 기하와 벡터를 공부했던 사람들이라면 한번쯤은 들어봤거나(못들어봤어도 상관없음) 했을 것이다.
  • 그러나 우리는 기벡의 원리를 자세히 따지기 보다는, 어떤 알고리즘이며 어떻게 사용하고 언제 적용하는지에 대해서만 알아보도록 할 것이다.

CCW 알고리즘이란?

  • CCW 는 벡터의 외적을 이용해서 두 벡터의 상대적인 위치를 알 수 있는 알고리즘이다. 조금 더 가볍게 설명을 하자면 A라는 정점으로 부터 B, C의 정점으로 가는 벡터 AB, AC가 있을 때, 이 두개의 벡터를 통해 B와 C의 상대적인 위치를 알아낼 수 있게 도와주는 알고리즘이다.(사실 수학 공식임)
  • 앞 예시에 이어 예를 들자면, AB 벡터를 기준으로 AC가 왼쪽에 존재한다면 외적의 값은 0보다 큰 값을 갖게 되고, AC가 오른쪽에 위치한다면 외적의 값은 0보다 작은 값을 갖게 된다. 만약 세 점이 일직선으로 놓였다면 외적의 값은 0의 값을 갖게 된다.
  • CCW를 통해 대표적으로 다각형의 넓이, 정점의 위치 판단 등 다양한 기하와 관련된 문제들을 해결 할 수 있다.
  • 그러면, 하나씩 알아보도록 하자!

CCW 코드

  • 다각형의 넓이, 정점의 위치 판단을 하기전에 CCW 알고리즘의 코드를 봐보도록 하겠다. (외적의 원리가 궁금한 사람들은 구글링을 통해 알아보고 오면 좀 더 쉽게 이해할 수 있을 것이다.)

C++ 코드

Python 코드

  • 위의 코드에서 ccw 함수의 리턴값은 두 벡터로 만들어지는 평행사변의 넓이랑 같다고 보면된다. 그렇다면 우리는 2가지를 알 수 있다.
    • 위에서 언급했던 것처럼 음수가 나오면, 그것의 절대값은 평행사변의 넓이고 기준이 되는 벡터의 왼쪽에 존재한다.
    • 양수가 나오면, 그것 자체가 평행사변의 넓이고 기준이 되는 벡터의 오른쪽에 존재한다.

관련된 문제

  • 백준 3042 트리플렛

    • 배열을 좌표라고 생각한다면, 이것이 ccw를 요구하는 문제라는 것을 단번에 알 수 있다.
    • 한 알파벳을 여러 칸에 쓸 수는 없다. 라는 조건을 잘 보면서 코딩을 할 수 있도록 하자.

  • 백준 11758 CCW

    • 문제 이름부터 CCW이다. 위에서 배운 내용을 그대로 적용하면 된다.