꼭 알아야하는 코딩 테스트 유형: 10) #Geometry

• 이번에는 코딩 테스트에서 중요한 유형인 'Geometry(기하학)'에 대해 알아보겠습니다. 기하학은 공간의 형태와 크기, 상대적인 위치 등을 다루는 수학의 한 분야입니다. 기하학적 문제는 프로그래밍에서 다양한 분야에 활용되며, 복잡한 데이터를 다루고 분석하는 데 필요한 도구를 제공합니다.

 

기하학의 개념

 

• 기하학은 점, 선, 면 등의 도형과 그들 사이의 관계를 연구하는 수학 분야입니다. 프로그래밍에서 기하학적 문제는 주어진 조건과 요구사항을 이해하여 도형을 표현하고 연산하는 것을 요구합니다. 예를 들어 점과 선분의 거리 계산, 세 점이 이루는 각도 구하기, 두 직선이 교차하는지 판별하기 등이 있습니다.

 

기하학 문제 접근법

 

1. 좌표 기반 접근: 평면 상에서 좌표를 사용하여 문제를 해결하는 경우가 많습니다. 좌표계를 설정하고 점과 선분의 위치 관계, 거리 계산 등을 활용하여 원하는 값을 구할 수 있습니다.
2. 벡터와 내적: 벡터는 크기와 방향을 가지며, 벡터 연산을 통해 각도, 직선의 교차 여부 등을 계산할 수 있습니다. 두 벡터 사이의 내적은 두 벡터가 이루는 각에 대한 정보를 제공합니다.
3. 삼각형과 넓이: 삼각형은 기하학에서 중요한 개념으로 다양한 성질과 공식들이 존재합니다. 세 점으로 이루어진 삼각형에서 넓이를 계산하는 공식(헤론의 공식 등)과 삼각형의 면적 비교 등을 활용할 수 있습니다.
4. 볼록 다각형과 그라함 스캔: 볼록 다각형은 그라함 스캔 알고리즘을 사용하여 구할 수 있으며, 볼록 다각형에 대한 연산 및 속성 파악에 유용합니다.
5. 원과 원접선 / 원접원: 두 원 사이의 관계와 원접선 / 원접원에 대한 성질들은 기하학 문제에서 자주 활용됩니다. 두 원 사이의 거리, 교차 여부 등을 판단하기 위해 사용됩니다.
6. 사분면과 각도: 사분면은 좌표 평면 상에서 각도와 관련된 정보를 제공합니다.
7. 회전 변환(Rotation Transformation): 주어진 도형인 도형들을 회전시켜야 할 때 회전 변환을 사용할 수 있습니다. 회전 변환은 좌표 평면 상의 점들을 주어진 중심점을 기준으로 원하는 각도만큼 회전시키는 연산입니다.
8. 교차와 접촉 판정: 두 도형이 교차하는지, 접촉하는지 여부를 판정해야 할 때, 선분 교차 판정 알고리즘 등을 활용할 수 있습니다.
9. 볼록 다각형의 분할: 볼록 다각형을 작은 삼각형이나 다른 형태로 분할하여 문제를 해결하는 경우가 있습니다. 이를 위해 삼각화 알고리즘 등을 사용할 수 있습니다.
10. 기하학적 관계 활용: 도형들 간의 위치 관계, 내접/외접 여부, 피타고라스 정리 등과 같은 기하학적 성질과 관계를 파악하여 문제에 적용할 수 있습니다.

• 코딩 테스트에서 기하학적 문제를 해결하기 위해 위와 같은 몇 가지 패턴을 활용할 수 있습니다.
•  예시로 몇 가지 기하학적 문제 유형과 접근 방법을 살펴보겠습니다.

 

거리 계산

 

• 두 점 사이의 거리 계산은 가장 간단한 기하학적 연산 중 하나입니다. 좌표 평면 상 두 점 (x1, y1)과 (x2, y2) 사이의 거리 D는 다음과 같이 계산할 수 있습니다.

import math

def distance(x1, y1, x2, y2):
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

 

각도 계산

 

• 두 벡터 사이의 각도를 계산하는 문제도 자주 등장합니다. 두 벡터 A와 B가 주어졌을 때, 이들 사이의 각도 θ는 다음과 같이 계산할 수 있습니다.

import math

def angle(Ax, Ay, Bx, By):
    dot_product = Ax * Bx + Ay * By
    norm_A = math.sqrt(Ax ** 2 + Ay ** 2)
    norm_B = math.sqrt(Bx ** 2 + By ** 2)
    
    cos_theta = dot_product / (norm_A * norm_B)
    
    # acos 함수는 라디안 단위로 반환하므로 degrees() 함수를 사용하여 도 단위로 변환합니다.
    theta = math.degrees(math.acos(cos_theta))
    
    return theta

 

교차 여부 판별

 

• 두 선분이 교차하는지 여부를 판별하는 문제도 기하학적인 문제 유형 중 하나입니다. 선분 AB와 CD가 주어졌을 때, 이들이 교차하는지 여부를 확인하기 위해선 다음과 같은 알고리즘을 사용할 수 있습니다.

def is_intersect(Ax, Ay, Bx, By, Cx, Cy, Dx, Dy):
    # CCW 알고리즘을 사용하여 점 C와 D가 선분 AB의 어느 쪽에 위치하는지 확인합니다.
    def ccw(Ax,Ay,Bx,Cy,Cy,Dy):
        cross_product = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
        if cross_product > 0:
            return 1   # 반시계 방향으로 위치함(ABCD 순서로 회전)
        elif cross_product < 0:
            return -1   # 시계 방향으로 위치함(DCBA 순서로 회전)
        else:
            return 0   # 일직선 상에 위치함
    
    ccw_AB_CD = ccw(Ax,Ay,Bx,Cy,Dy,Dy)   # 점 C와 D가 선분 AB의 어느 쪽에 있는지 확인
    
    ccw_CD_AB = ccw(CX,CY,DX,AY,BY,BY)   # 점 A와 B가 선분 CD의 어느 쪽에 있는지 확인
    
     if ccw_AB_CD == 0 and ccw_CD_AB == 0:
         # 두 개의 선분이 일직선 상에 있으므로 겹치는 경우일 수도 있습니다. 겹치는 경우를 판별하기 위해 두 선분이 공통된 점을 가지고 있는지 확인합니다.
         
     	if min(Ax, Bx) <= Cx <= max(Ax, Bx) and min(Ay, By) <= Cy <= max(Ay, By):
            return True   # 점 C가 선분 AB 위에 존재함
        
        if min(Ax, Bx) <= Dx <= max(Ax, Bx) and min(Ay, By) <= Dy <= max(Ay, By):
            return True   # 점 D가 선분 AB 위에 존재함
        
        if min(Cx, Dx) <= Ax <= max(Cx, Dx) and min(Cy, Dy) <= Ay <= max(Cy, Dy):
            return True   # 점 A가 선분 CD 위에 존재함
        
        if min(Cx,Dx)<=B.x<=max(C.x,D.x)&&min(C.y,D.y)<=B.y<=max(C.y,D.y):
            return true;   //점 B가 선분 CD위에 존재함

    return False  # 겹치는 경우가 없음

 

1485번: 정사각형

  문제  
 

• 네 점이 주어졌을 때, 네 점을 이용해 정사각형을 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오.

 
  해결 방법  
 

• 이 문제는 네 점이 주어졌을 때 그 점들로 정사각형을 만들 수 있는지 판별하는 문제입니다.
• 정사각형은 네 변의 길이가 같고 두 대각선의 길이가 같으므로, 네 점 사이의 거리를 모두 구해서 정렬했을 때 처음 네 개의 값이 같고 마지막 두 개의 값이 같으면 그 점들은 정사각형을 이룹니다.

def isSquare(coord):
    d = []
    for i in range(3):
        for j in range(i+1, 4):
            d.append((coord[i][0]-coord[j][0]) ** 2 + (coord[i][1]-coord[j][1]) ** 2)
    d.sort()
    if d[0] == d[1] == d[2] == d[3] and d[4] == d[5]: return True
    else: return False

for _ in range(int(input())):
    coord = [list(map(int, input().split())) for _ in range(4)]
    print(1 if isSquare(coord) else 0)

 

2022번: 사다리

  문제  
 

• 아래의 그림과 같이 높은 빌딩 사이를 따라 좁은 길이 나있다. 두 개의 사다리가 있는데 길이가 x인 사다리는 오른쪽 빌딩의 아래를 받침대로 하여 왼쪽 빌딩에 기대져 있고 길이가 y인 사다리는 왼쪽 빌딩의 아래를 받침대로 하여 오른쪽 빌딩에 기대져 있다. 그리고 두 사다리는 땅에서부터 정확하게 c인 지점에서 서로 교차한다. 그렇다면 두 빌딩은 얼마나 떨어져 있는 걸까?

  해결 방법  
 

• 이 문제는 두 사다리의 높이와 두 사다리 사이의 거리가 주어졌을 때 강을 가로지르는 로프의 최대 길이를 구하는 문제입니다.
• 두 사다리의 꼭대기에서 강 바닥까지 내려오는 높이를 이용하여 피타고라스 정리와 비례식을 이용하여 해결할 수 있습니다.
• 먼저 중간값 mid를 구하고 그에 따른 높이 h를 계산합니다. 만약 계산된 h가 주어진 c보다 크다면 로프의 길이를 줄여야 하므로 왼쪽 경계값을 mid로 업데이트하고, 그렇지 않으면 오른쪽 경계값을 mid로 업데이트합니다.
• 이 과정을 반복하면서 왼쪽과 오른쪽 경계값의 차이가 충분히 작아질 때까지 반복합니다.

x, y, c = map(float, input().split())

left, right = 0, min(x, y)

while abs(left-right) > 1e-6:
    mid = (left+right) / 2.0
    d = mid
    h1 = (x*x - d*d) ** .5
    h2 = (y*y - d*d) ** .5
    h = (h1 * h2) / (h1 + h2)
    
    if h > c: left = mid
    else: right = mid

print("%.3f" % round(right, 3))

 

• Geometry(기하학)은 코딩 테스트에서 중요한 유형 중 하나입니다. 기하학적 문제를 해결하기 위해서는 문제 파악과 도형 모델링의 정확성이 매우 중요합니다. 수식이나 알고리즘 설계 시에도 기하학적인 개념과 원리를 잘 활용하여 코드를 작성해야 합니다.
• 코딩 테스트에서 기하학 문제를 만났을 때는 주어진 조건과 요구사항을 정확히 이해하고 필요한 도형 모델링 및 연산을 수행하는 것이 핵심입니다. 그리고 코드 작성 후 예시 입력과 출력을 통해 검증하는 것도 잊지 마세요.
• 기하학은 프로그래밍에서 다양한 분야에 활용되므로 여러 가지 문제 유형들을 다양한 예시와 함께 연습하는 것이 좋습니다. 많은 연습과 경험을 통해 기하학적인 사고력과 능력을 향상시켜 나갈 수 있습니다.