2019 채용퀴즈 해설

안녕하세요 사이냅소프트입니다.

사이냅소프트에 개발자로 지원 시 채용퀴즈를 함께 제출하셔야 합니다. 조금 까다롭게 느껴지실 수 있지만 개발실력으로 지원자 여러분과 마주하고자 하는 사이냅소프트의 마음가짐이라고 생각해주시면 좋을 것 같습니다.

사이냅소프트의 채용퀴즈는 쉽게 풀 수 있으면서도 다양한 방법으로 접근 할 수 있는 문제를 출제하고 있습니다. 하지만 문제 곳곳에 함정이 숨어있어서 쉽게 생각한다면 잘못된 답이 도출됩니다. 이는 문제 요구사항을 정확히 이해하고 문제를 해결하기 위해 다양한 방식을 찾아가는 모습을 확인하고자 하는데 목적이 있습니다.

이러한 의도를 지원자 여러분과 공유하고자 2019년 공개채용 문제 풀이를 해보려고 합니다. 문제 풀이를 통해 사이냅소프트에서 어떤 목적으로 문제를 출제하고 지원자 여러분들은 어떻게 접근하는 것이 좋을지에 대한 아이디어를 얻으셨으면 좋겠습니다.

문제 설명

1920×1080 픽셀을 가진 Full HD 화면상에 수직선, 수평선으로만 이루어진 직사각형들이 놓여 있습니다. 직사각형들은 홀로 떨어져 있거나, 일부 겹치거나, 변 또는 꼭지점이 접하거나, 포함관계에 있을 수 있습니다. 직사각형들이 차지하고 있는 총면적을 구하는 프로그램을 작성해주세요. 프로그래밍 언어는 가장 자신 있는 것을 사용하세요.

예로 10×10 픽셀을 가진 화면상에 아래와 같은 직사각형들이 있을 수 있습니다.

– 입력

각각의 사각형이 하나의 입력줄이 되며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어집니다. 좌표는 왼쪽 위가 (0,0)이고 오른쪽 아래가 (1920, 1080) 입니다. 첫 두 정수는 사각형의 왼쪽 위 꼭지점의 x, y좌표이고 다음 두 정수는 오른쪽 아래 꼭지점의 x, y좌표입니다.

위 예는 아래와 같은 입력을 갖습니다. 입력은 별도 파일에서 읽어와도 되고 소스코드 안에 포함시켜도 됩니다.

1 0 4 2
8 3 9 4
2 3 5 7
4 6 7 8
3 1 6 5
1 8 4 10
7 2 9 5
8 8 10 9
1 4 2 6

-출력

화면에서 직사각형들이 차지하고 있는 총면적을 출력합니다. 위 예의 출력은 다음과 같습니다.

46

문제 풀이

[잘못된 접근]

각각의 사각형 영역을 다 더하여 전체 영역의 넓이를 구한 후 두 개의 사각형이 겹치는 부분의 넓이를 빼는 방식입니다. 언뜻 생각하면 효율적인 방법처럼 보이지만 실제로는 잘못된 답이 도출되는 방식입니다.

# wrong solution
def solution3(rects):
total_area = 0

for l,t,r,b in rects:
total_area += (r-l) * (b-t)

for i in range(len(rects)):
    for j in range(i+1, len(rects)):
      l = max(rects[i][0], rects[j][0])
      t = max(rects[i][1], rects[j][1])
      r = min(rects[i][2], rects[j][2])
      b = min(rects[i][3], rects[j][3])

if l<r and t<b:
total_area -= (r-l) * (b-t)

return total_area

하나의 영역에 세 개 이상의 사각형이 겹쳐지는 경우 동일한 영역이 여러 번 제외되어 원하는 결과를 얻지 못하게 됩니다.

예를 들어, 세 개의 사각형이 겹쳐있는 경우에는 아래와 같이 계산이 됩니다.

하지만 원하는 결과를 얻기 위해서는 아래와 같이 계산을 해주어야 합니다.

마치 합집합의 원소 개수를 구하는 것과 비슷한 모양이 되었습니다.

실제로 각각의 사각형은 픽셀들을 가지고 있는 집합으로 볼 수 있습니다. 따라서 면적을 구하는 것은 픽셀 집합의 합집합의 원소의 개수를 구하는 것과 같은 문제가 됩니다. 사각형이 네 개가 겹쳐있다면 아래와 같이 계산할 수 있습니다.

A∪B∪C∪D = A + B + C + D – A∩B – A∩C – A∩D – B∩C – B∩D – C∩D + A∩B∩C + A∩B∩D + A∩C∩D + B∩C∩D – A∩B∩C∩D

사각형이 네 개, 다섯 개 혹은 그 이상 겹쳐있다면 더 복잡해지겠지요?

이 방법으로 원하는 결과를 얻는 것은 어려울 것 같습니다.

[일반적인 방법]

공채에 지원하신 대부분의 지원자가 아래 소개하는 방식으로 문제를 해결하였습니다.

1. 화면을 채우는 방식

1920 x 1080 화면을 2차원배열로 선언하여 사각형영역을 색칠을 한 후, 색칠된 픽셀의 개수를 세는 방식입니다.

def solution1(rects):
coord = [[0]*W for _ in range(H)]

for l,t,r,b in rects:
    for y in range(t,b):
      for x in range(l,r):
        coord[y][x] = 1

total_area = 0
for row in coord:
for cell in row:
total_area += cell

return total_area

그러나 화면 전체를 덮는 1920 x 1080크기의 사각형이 100개가 있으면 1920 x 1080 x 100 = 200,000,000의 픽셀을 색칠해야 합니다. 이보다는 더 효율적인 방법이 필요할 것 같습니다.

2. 픽셀 좌표를 저장하는 방식

사각형 영역이 덮고 있는 픽셀의 좌표를 적절한 자료구조에 넣고 해당 자료구조에 들어가 있는 좌표의 개수를 세는 방식입니다. 이 방법을 사용하려면 효율적인 자료구조를 선택해야 합니다. 먼저 중복된 데이터를 허용하지 않아야 하고, 데이터를 추가하는 연산 비용이 작아야 합니다. 대부분의 언어에서 ‘set’이나 ‘hash’와 같은 자료구조를 기본적으로 지원하고 있어서 어렵지 않게 구현할 수 있습니다.

def solution2(rects):
coord = set()

for l,t,r,b in rects:
    for y in range(t,b):
      for x in range(l,r):
        coord.add((x,y))

return len(coord)

하지만 이 방법도 화면 전체를 덮는 사각형이 많으면 데이터를 삽입하는 횟수가 많아지기 때문에 보다 더 효율적인 방법이 필요합니다.

[조금 더 효율적인 방법]

위의 방식은 사각형의 개수 외에도 화면의 크기에 영향을 받습니다. 화면의 크기가 커지면 처리하는 시간도 늘어나고 사용하는 메모리의 양도 늘어나게 되지요. 어떻게 하면 좀 더 효율적으로 해결할 수 있을까요?

사이냅소프트는 다음과 같은 알고리즘을 생각해봤습니다.

def solution4(rects):
    x_events = set()
    for l,t,r,b in rects:
        x_events.add(l)
        x_events.add(r)
    x_events = sorted(x_events)

    total_area = 0
    subarea_left = 0
    for subarea_right in x_events:
        inter_checker = lambda rect: rect[0]<=subarea_left and subarea_right<=rect[2]
        y_events = []
        for l,t,r,b in filter(inter_checker, rects):
            y_events.extend([(t, 1), (b, -1)])
        y_events.sort()

        start_y, overlap_cnt = 0, 0
        for p, e in y_events:
            if overlap_cnt == 0:
                start_y = p

overlap_cnt += e

if overlap_cnt == 0:
total_area += (subarea_right – subarea_left) * (p – start_y)

subarea_left = subarea_right

return total_area

이 방식은 널리 알려진 방식으로 인터넷에서 관련된 많은 자료를 찾을 수 있습니다.

가로축을 기준으로 사각형의 왼쪽/오른쪽 모서리를 만나는 지점을 미리 모아보면 해당 지점 사이에서는 사각형의 넓이가 변하지 않는 것을 알 수 있습니다. 위의 그림에서 붉게 표시된 영역을 보시면 너비가 d인 사각형들의 집합처럼 보이는 것이죠. 그럼 사각형들과 붉게 표시된 영역이 교차되는 구간의 길이 h를 구하게 되면 d x h로 해당 구간에서의 넓이를 구할 수 있게 됩니다. 이러한 동작을 각 구간에서 반복하게 되면 전체 넓이를 구할 수 있습니다.

h는 어떻게 구할 수 있을까요? 마찬가지로 세로축을 기준으로 사각형의 위쪽/아래쪽 모서리를 만나는 지점에서 새로운 사각형이 발견되면 +1, 기존의 사각형이 빠져나가면 -1을 해주어서 0이 아닌 구간의 길이가 h가 됩니다.

이러한 방식을 Line Sweep이라고 합니다. 마치 빗자루 쓸듯이 라인을 이동시켜가면서 계산해 나가는 방식입니다. 일일이 모든 픽셀을 계산하지 않고 영역별로 계산해 나가기 때문에 앞선 방식들에 비해 효율적으로 계산할 수 있게 됩니다.

물론 세로 방향의 길이, 즉 h를 구하는 부분에 있어서도 개선할 수 있는 방법이 있습니다. 바로 segment tree라는 자료구조를 이용하는 것이지요. segment tree 자료구조는 각 구간에서 쪼개진 사각형 넓이의 합을 누적해서 쌓아나가는 방법입니다. 어떻게 하면 될지는 여러분께서 한번 고민해보세요. 직접 구현해보시면 개발 능력이 한 단계 업그레이드 되실 겁니다!

마치며

이번 채용퀴즈는 해결할 수 있는 방식은 다양하지만 최적의 알고리즘을 찾는 탐구과정이 필요한 문제였습니다.

Line Sweep 알고리즘을 알고 계셨던 분은 어렵지 않게 작성하셨지요? 이번 문제는 Line Sweep 알고리즘을 알고 있는지 판단하려는 것이 아니라 Line Sweep 알고리즘을 탐구를 통해 알아내고 적용할 수 있는가가 출제의도였습니다. 결과도 중요하지만 문제해결방식을 찾아가는 모습을 보고자 했던 것이죠.

여러분들께서는 어떤 방식으로 접근하셨나요?

메일로 여러분의 알고리즘을 공유해주세요. 문제에 대한 의견이나 기타 궁금한 사항도 메일 주시면 답변 드리겠습니다.

감사합니다.