2015.05.04 16:05

AlgoSpot Quiz '사각형 그리기 (DRAWRECT)' 문제 풀이.


▶ DRAWRECT 문제 분석


- input       : 입력의 첫 행은 T 값이며, 테스트 케이스(test case)의 갯수이다. 

                 나머지 입력은 x, y 좌표 값을 공백으로 구분한 행들이며, 3 * T 갯수 만큼 입력된다.

- processing : T 만큼 반복하면서, 3개의 2차원 좌표를 이용해 마지막 좌표를 계산한다.

- output     : 계산된 마지막 좌표를 출력한다.


입력 값의 범위와 유형은 아래와 같이 표현할 수 있습니다.




▶ 문제 분할

문제 자체가 복잡하지 않기 때문에 세밀한 문제 분할은 필요가 없습니다.


▶ 핵심 논리 구성

4개의 점 중에서 하나가 누락될 경우, 3개의 점으로 구성할 수 있는 경우의 수를 구해 봅니다. 수학의 '조합(combination)'을 활용하면 되겠습니다. 조합(Combination)이란, 서로 다른 개 중 순서를 무시하고 개를 택하는 것이며,  기호로 나타냅니다.



조합을 이용해 4개의 점 중에서 3개의 점을 순서를 구분하지 않고 선택하는 경우의 수를 계산하면, 아래와 같습니다.



4개의 경우의 수를 표 형태로 표현해 보면 다음과 같습니다.


 조합

 Case #1

Case #2 

Case #3 

Case #4 

 좌표

 p1 (x1, y1)

 p2 (x2, y1)

 p3 (x1, y2)

 p1 (x1, y1)

 p2 (x2, y1)

 p4 (x2, y2)

 p1 (x1, y1) 
 p3 (x1, y2)
 p4 (x2, y2)
 p2 (x2, y1)
 p3 (x1, y2)
 p4 (x2, y2)

 비고

 p4 제외

 p3 제외 

 p2 제외  p1 제외 


위 표를 통해 얻을 수 있는 핵심 논리는 아래와 같습니다.


직사각형의 3개의 점(point)가 입력되었을 때, x와 y 좌표는 항상 2개는 같고 나머지 하나는 다르다.

다른 값을 가지는 2개의 x, y 좌표 값을 결합하면 4번째 좌표를 얻을 수 있다.


▶ 플랫폼 문제 해결

본 문제는 플랫폼 문제를 해결할 필요가 없습니다.


▶ 핵심 정리

알고리즘 문제 해결을 위해 가장 좋은 도구는 '수학'입니다. 또한, 문제를 풀기 위해서 좌표계 등의 시각적인 도구를 활용하면, 직관적으로 문제를 이해하는데 있어 큰 도움이 됩니다.

Posted by 善 곽중선