코틀린 코딩테스트 강좌, 기하 알아보기

기하학은 컴퓨터 과학에서 많은 분야에서 활용되며, 코딩테스트에서도 자주 출제되는 주제입니다.
이번 포스팅에서는 기하 사용자 문제를 다루고, 코틀린을 사용하여 효율적으로 해결하는 방법을
설명하겠습니다.

문제 설명

문제: 주어진 N개의 점이 2차원 평면에 있을 때, 이들 점 중에서 볼록 껍질(Convex Hull)을
이루는 점들의 좌표를 시계 방향으로 출력하시오.

볼록 껍질이란, 평면상의 점들 중에서 모든 점을 포함하는 가장 작은 볼록 다각형을 의미합니다.
이 문제는 흔히 알고리즘 문제로 자주 출제되며, 효율적인 알고리즘으로는 그레이엄 스캔(Graham’s scan)
이나 잔디밭 방식(Jarvis March) 등이 있습니다.

입출력 형식

입력: 첫 번째 줄에 정수 N(1 ≤ N ≤ 100,000)이 주어지고,
다음 N개의 줄에 각 점의 x, y 좌표가 주어진다.
(x, y는 -10^9 이상, 10^9 이하의 정수다.)

출력: 볼록 껍질을 구성하는 점들의 좌표를
시계 방향으로 출력하고, 각 좌표는 공백으로 구분한다.

문제 풀이 과정

문제를 풀기 위해서는 다음과 같은 단계들을 거쳐야 합니다:

입력 데이터 처리:
점의 좌표를 입력받아 리스트에 저장합니다.
이때, 각 점을 Pair 객체로 저장하면 편리합니다.
좌표 정렬:
극각도를 기준으로 점들을 정렬합니다.
가장 왼쪽 아래(또는 위) 점을 기준으로 삼고, 나머지 점들을 극각도에 따라 정렬합니다.
볼록 껍질 생성:
그레이엄 스캔 알고리즘을 사용하여 볼록 껍질의 점들을 찾습니다.
출력 형식에 맞게 포맷팅:
결과를 시계 방향으로 정리하고, 요구하는 형식으로 출력합니다.

코드 구현

        
            import kotlin.math.atan2
            
            data class Point(val x: Int, val y: Int)
            
            fun convexHull(points: List): List {
                val sortedPoints = points.sortedWith(compareBy({ it.x }, { it.y }))
                val hull = mutableListOf()
                
                // 아래쪽 부분
                for (point in sortedPoints) {
                    while (hull.size >= 2 && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)
                        hull.removeAt(hull.size - 1)
                    hull.add(point)
                }
                
                val lowerSize = hull.size
                
                // 위쪽 부분
                for (i in sortedPoints.size - 1 downTo 0) {
                    val point = sortedPoints[i]
                    while (hull.size > lowerSize && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)
                        hull.removeAt(hull.size - 1)
                    hull.add(point)
                }
                
                hull.removeAt(hull.size - 1) // 마지막 점은 중복되므로 제거
                
                return hull
            }
            
            fun cross(o: Point, a: Point, b: Point): Int {
                return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
            }
            
            fun main() {
                val n = readLine()!!.toInt()
                val points = List(n) {
                    val (x, y) = readLine()!!.split(" ").map { it.toInt() }
                    Point(x, y)
                }
                val hull = convexHull(points)
                hull.forEach { println("${it.x} ${it.y}") }
            }

결론

이번 포스팅에서는 볼록 껍질을 구하는 문제에 대해 설명하였습니다.
기하학적인 문제는 실전 코딩테스트에서 자주 출제되므로
충분히 연습하고 다양한 유형의 문제를 풀어보는 것이 중요합니다.
이 외에도 다른 기하학적 문제를 통해 문제 해결 능력을 키워나가시기 바랍니다.

추가 학습 자료

코틀린을 더 깊이 있게 배우고 싶으시다면 다음의 자료들을 추천드립니다:

코딩 테스트 준비 잘 하시고, 좋은 결과 있기를 바랍니다!

문제 설명

입출력 형식

문제 풀이 과정

코드 구현

결론

추가 학습 자료

관련