Full HD 화면상의 직사각형들이 차지하고 있는 총면적

문제

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

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

입력

각각의 사각형이 하나의 입력줄이 되며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어집니다. 좌표는 왼쪽 위가 (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

참고

프로젝트 오일러 212번은 한차원 더 높은 문제입니다.
https://euler.synap.co.kr/problem=212

출처) 사이냅소프트 채용퀴즈

아래 정답란에는..

파일 boxes.txt의 모든 직사각형이 차지하고 있는 총 면적을 구하여 제출하세요.

문제 풀이

핵심은 무엇일까?

• 문제의 핵심은 좌표를 기준으로 픽셀 단위로 특정 좌표로 이루어진 직사각형이 만들어진다.
• 여기서 문제의 경우의 수는 겹치거나 포개지는 경우가 있을 수 있다는 사실이다.
• 그런 상황에서 총 면적을 정확하게 구해내야 한다.

그렇다면 어떻게 접근할까

• 우선 핵심적으로 좌표를 굳이 곳대로 적을 필요는 없어 보인다. 왜냐면 좌표 값이라는 것을 표현하는 문자열 내지는 정수 좌표화 하는 경우 쓸데없는 로직을 추가할 우려가 있다.
• 데이터 구조로 핵심만 캐치하면 된다. 즉, 좌표가 들어갈 공간을 마련하고, 받은 좌표에 따라 해당 데이터를 True 로 바꾼 뒤, 그 갯수를 새는 건 어떨까?
• 데이터를 압축없이 그대로 담는 것은 오버헤드를 생각하더라도 전체 연산량을 생각하면 차라리 데이터를 1:1로 담기는 해야 한다.

로직

1. display 의 해상도를 기준으로 사전형 구조를 채택한다.
   • 기본적으로 사전형으로 키는 가로 좌표로 지정함
   • 값 영역에는 집합 자료형을 채택하고, 세로 좌표 를 담을 수 있도록 설정한다.
2. 파일을 열고, 전체를 라인단위로 읽는다.
3. 각 좌표를 받아낸 뒤, 해당 좌표의 범위를 데이터 셋에 기록한다.
4. 전부 다 정리 된 이후, set 자료형 덕분에 좌표는 1회만 기록되고, 이렇게 모인 좌표를 전부 더한다.

# 1920*1080 화면에서 지정된 직사각형 넓이를 다 더하는 문제  
# 이 문제의 핵심은 두 점이 주어지고, 그 점을 기준 직사각형을 만들었을 때, 그 점위들의 종합을 계산하는 것이다.  
# 여기서 핵심은 얼마나 데이터를 남길 것이며, 어떤 데이터는 버릴 것인가에 대한 정보이다.  
# 핵심은 세로줄을 기준으로 제공이 들어오면,  
# 가로 줄에서 어디까지를 사용범위로 둘지 기재하는 방식  
# 사전 형태가 가지는 특성을 잘 활용한다면 충분히 해결이 가능한 문제다.  
  
# 1920 의 가로 길이 만큼의 사전형  
# 그 지목된 세로 위치 좌표를 리스트로 가짐  
# 1920개의 사전 자료 기준으로 돌면서, 지목된 세로 좌표를 전체 개수를 구하고 더하면 됨  
# 내부 자료는 집합형을 사용하면 됨  
  
  
maximum_range = 1921  
  
  
def total_sum(display_dots):  
    result = 0  
    for index in range(len(display_dots)):  
        result += len(display_dots[index])  
    return result  
  
  
display = {x: set() for x in range(maximum_range)}  
  
# with open('sample_box.txt', 'r', encoding='utf-8') as file:  
with open('box.txt', 'r', encoding='utf-8') as file:  
    for line in file:  
        x_1, y_1, x_2, y_2 = map(int, line.strip().split())  
        for x in range(x_1, x_2):  
            for y in range(y_1, y_2):  
                display[x].add(y)  
    file.close()  
  
    print(total_sum(display))

스프레드시트 컬럼의 영문명칭 개선

문제

네이버 오피스 셀(Cell)이나 마이크로소프트 엑셀(Excel)과 같은 스프레드시트 프로그램은
열(column)을 표시하기 위해 알파벳 대문자를 사용합니다.
예를 들면 1열=A, 2열=B, 26열=Z 와 같이 표시되고,
26열이 넘어가면 앞쪽에 문자 하나를 추가해서 27열=AA, 28열=AB, 52열=AZ, 53열=BA가 되며,
동일한 원리로 ZZ의 다음 열은 AAA, AAB, … 처럼 이어집니다.

숫자를 입력받으면 그 순서에 대응되는 스프레드시트 컬럼을 출력하는 프로그램을 작성하세요.

입력

입력은 다음과 같습니다.

1
10
100
1000
10000

출력
아래와 같이 출력합니다.

A
J
CV 
ALL
NTP

출처) 사이냅소프트 채용퀴즈

아래 정답란에는..

알파벳 대문자로 된 1억(108108) 번째 컬럼의 명칭을 구하여 제출하세요.

문제 풀이

핵심

• 간단히 27진수 값을 만들고, 이때 26진수의 각 숫자는 알파벳으로 대체하면 된다.

로직

1. 사전형을 활용해, 숫자를 알파벳으로 만들어준다.
2. 지정 값을 받는다.
3. 각 값이 27로 나눈다.
4. 27보다 작으면, 바로 대입, 27보다 크거나 같으면 나눠준다. 이때 나오는 몫과 나머지로 결과 값에 넣어주되, 마지막에 출력시 뒤집는다.

코드

alpha = {x: char for x, char in zip(range(1, 27),"ABCDEFGHIJKLMNOPQRSTUVWXYZ")}  
  
target = int(input('Enter a number: '))  
result = ""  
  
while True:  
    if target >= 27:  
        result += alpha[target % 26]  
        target = target // 26  
    else:  
        result += alpha[target]  
        target -= target  
        break  
  
result = result[::-1]  
print(result)

숫자 목록을 이용해 만든 두 자연수 합의 최솟값

문제

0~9 사이의 정수 n개를 빠짐없이 한 번씩만 써서 두 개의 자연수를 만들 수 있습니다.
예를 들어, 숫자 목록 1, 2, 4, 7, 9가 있다면 (149, 27), (124, 79), (1, 9742)… 처럼 많은 자연수 조합이 가능합니다.
이렇게 만든 두 개의 자연수의 합이 최소가 되는 쌍을 찾아 그 합을 구하세요.

조건

• 입력받는 숫자의 개수는 2≤n≤18 사이입니다.
• 당연한 이야기지만, 숫자를 조합할 때 맨 앞자리에 0이 오게 해서는 안됩니다.
• 입력받은 숫자로 자연수를 두 개 만들 수 없는 경우도 있습니다. 이 때의 결과값은 -1이 됩니다.
• 숫자를 입력받는 방식은 어떻게 구현해도 상관없습니다.
  • 외부 파일으로부터 읽어오기
  • 콘솔 터미널에서 직접 입력받기
  • 소스 내 하드코딩(!!)
  • rest API 연동(!!!!!!) ← 그냥 하지 마세요 -_-;;

입력

한 줄은 숫자 목록 하나 입니다. 각 숫자는 콤마 또는 공백으로 구분되어 있습니다. 다음은 입력 예입니다.

1, 2, 4, 7, 9
1, 2, 3, 1, 2, 3
1, 2, 3, 4, 5, 6, 7
0, 1, 2, 3, 0, 1, 2, 3, 4
0, 0, 1

출력

숫자 목록을 이용해 만든 두 자연수의 합의 최솟값을 각 줄에 하나씩 출력합니다. 위 예의 출력은 아래와 같습니다.

176
246
1603
11257
-1

출처) 사이냅소프트 채용퀴즈

아래 정답란에는..
숫자 목록 0, 0, 1, 8, 2, 2, 8, 9, 0, 3, 4, 0, 0을 이용해 만든 두 자연수 합의 최솟값을 구하여 제출하세요.

문제 풀이

핵심

• 조합과 순열이 필요해… 보인다! 하지만 그렇지 않았다. 그렇게 해서 값을 찾도록 구성하는 것은 가능하지만(문제 내 보기 한정), 해당 방법으로는 10자리가 넘어가기 시작하면서 부터 조합의 그 숫자가 너무 방대해진다.
• 따라서 메모리 및 연산량 문제로 itertools 라이브러리를 활용해서 조합과 순열을 사용하는 것은 좋은 선택이 아니다.
• 따라서 반드시 기억해야 할 것은 조합을 하기전, 원하는 값, 데이터를 뽑아내기 위한 조건이 어떻게 구성되는가? 에 대한 질문일 것이다.
• 결국 받는 숫자들의 개수를 기준으로 생각해보면 다음과 같은 조건이 되어야 최솟값이 되는 것을 알 수 있다.
  1. 각 숫자는 최솟값이 되기 위해선, 앞자리일 수록 작아야 한다.
  2. 각 숫자는 비대칭이 되는 경우, 주어지는 숫자의 개수가 많아질 수록 최솟값이 될 수가 없다.
  3. 각 숫자에서 0은 최초 앞자리 숫자를 제외하면, 바로 뒤에 붙어야 최솟값이 될 가능성이 높아진다.

로직

1. 들어오는 값에서 우선 0을 따로 모아둔다.
2. 그 뒤 두개의 값을 구성하기 위해 최소 값들을 먼저 두개의 값에 넣어준다.
3. 모아둔 0을 전부 각 값에 우선 배치를 시킨다.
4. 이후 남은 숫자의 배열에서, 하나씩 최솟값을 꺼내서 양 수에게 번갈아 제공한다.

코드

arr = list(map(int, input().split(", ")))  
zero_arr = list()  
print(arr)  
numberA = ""  
numberB = ""  
while True:  
    if 0 in arr:  
        zero_arr.append(0)  
        arr.remove(0)  
    else:  
        break  
  
min_value = min(arr)  
numberA += str(min_value)  
arr.remove(min_value)  
  
min_value = min(arr)  
numberB += str(min_value)  
arr.remove(min_value)  
  
i = 0  
while len(arr) != 0 :  
    if i % 2 != 0:  
        if 0 in zero_arr:  
            zero_arr.remove(0)  
            numberB += '0'  
        else:  
            min_value = min(arr)  
            arr.remove(min_value)  
            numberB += str(min_value)  
    else :  
        if 0 in zero_arr:  
            zero_arr.remove(0)  
            numberA += '0'  
        else:  
            min_value = min(arr)  
            arr.remove(min_value)  
            numberA += str(min_value)  
    i += 1  
  
print("A:", numberA)  
print("B:", numberB)  
print(int(numberA) + int(numberB))

특정 구간내의 모든 피보나치 수의 합

문제

피보나치 수에 대한 문제입니다. 피보나치 수는 아래와 같이 정의됩니다.
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 1 + 2 = 3
f(4) = f(2) + f(3) = 2 + 3 = 5
f(5) = f(3) + f(4) = 3 + 5 = 8
…
f(n) = f(n-2) + f(n-1), n>=3

a와 b라는 두 수가 주어져 있을 때 두 수 사이에는 몇 개의 피보나치 수가 있을까요?
예를 들어 10과 100 사이에는 총 5개(13, 21, 34, 55, 89)의 피보나치 수가 있고 모두 더한 값은 212입니다.

12345678999과 99987654321 사이에도 몇 개의 피보나치 수가 있습니다.
이 구간 내의 모든 피보나치 수를 더한 값이 기념품을 받을 수 있는 열쇠입니다 값은 얼마입니까?

출처) 풀면 기념품을 줬다는 2007년 사이냅소프트 퀴즈 도입 문제

문제풀이

핵심

• 이 역시 있는 그대로 구현을 하게 되면 효율적이지 못한 결과를 초래한다.
• 우선 제시되는 값의 숫자만 보더라도 피보나치 값을 기억하는 순간 엄청난 메모리 사용량과 연산량이 나온다.
• 따라서 가장 핵심은 피보나치를 구현하되, 필요한 부분인 조건에 해당할 때만, 저장하는 방식으로 가면 된다.

로직

코드

min_limit, max_limit = map(int, input().split())  
result = list()  
  
a = 0  
b = 1  
  
while a <= max_limit:  
    if a >= min_limit:  
        result.append(a)  
    a, b = b, a + b  
  
print(result)  
print(sum(result))

암호 산술 1. SYNAP + SOFT = WANTS + YOU

문제

‘SEND + MORE = MONEY’ 라고 들어 보셨나요?? 모르셔도 상관없습니다. 고고싱~!!

이 문제는 20세기 최고의 퍼즐리스트중 한명인 헨리 듀드니가 만든 대표적인 암호산술 문제입니다.
각 알파벳은 하나의 숫자를 나타내고, 숫자의 첫 번째 자리에 ‘0’을 쓸 수는 없습니다.
한마디로 이 문제에서 ‘S’와 ‘M’은 ‘0’이 아니라는 거죠. 답이 궁금하세요?

답은 한 가지입니다. 먼저 연습 삼아 연필로 풀어보세요. ^0^/

‘SEND + MORE = MONEY’ 답 보기

재밌죠? 하나 더 해 볼까요? 이번엔 덧셈은 말고 곱셈으로 해 보겠습니다.
사이냅소프트 사장님 이름으로 해 보죠. ^^*
‘Allen Kyonghun Jeon’ 으로 암호산술 문제를 만들었습니다.

‘ALLEN = K * JEON’ 답 보기

이 문제의 답은 3가지가 있습니다.
어때요? 해볼만 하시죠? 어려워 보여도 조금만 신경 쓰면 쉽게 풀 수 있을 겁니다. ^^*

자~ 여기까진 문제의 이해를 돕기 위한 도움말이었습니다~!!
드디어 진짜 문제가 나갑니다~ 집중하세요~! ^0^/

‘SYNAP + SOFT = WANTS + YOU’

해석해 볼까요?? ‘사이냅소프트는 당신을 원하고 있습니다’ 라는군요~ ^0^

기념품을 받으실 열쇠는 ‘가능한 모든 답의 좌변 숫자를 더한 값’입니다.
위 암호산술의 가능한 모든 답의 좌변 숫자를 더한 값을 제출하세요.

출처) 풀면 기념품을 줬다는 2007년 사이냅소프트 퀴즈 1단계 문제

문제 풀이

핵심

• 이 문제는 어떻게 풀어야 할지 다소 난감했고, 현재 조합을 통해 풀긴 했으나 온전한 방법인지는 아직 의문이다.
• 그러나 어쨌든 핵심은 주어지는 키워드 알파벳은 각각 숫자를 나타내며, 따라서 암호의 경우의 수를 따져, 키워드들로 만들 수 있는 숫자를 통해 제공한 문제의 식이 부합 되는지를 판단하는 것이 핵심이다.
• 또한 다행이도 모든 경우의 수가 아닌 몇 부분에 대해 확정적인 조건을 파악하고 넣어 줌으로써 경우의 수를 줄여서 암호를 해석할 수 있다.

로직

1. 영어들을 모두 모아서, 0~9까지의 숫자 조합을 만든다.
2. 이때 조건인 S, W, Y는 0이 되지 않는 경우만을 모은다.
3. 1차 조건을 통과한 숫자 배열(영어에 대입될)을 가지고와 각 문장에 맞춰 정수를 만들어낸다.
4. 그렇게 연산결과 조건에 부합하는 경우 결과 문장에 이를 담고 초기화 한다.
5. 마지막으로 요구하는 값으로 더해서 결과를 출력한다.

코드

import itertools

# 문자 리스트
sy = "SYNAP"
so = "SOFT"
wa = "WANTS"
yo = "YOU"
n_sy = ""
n_so = ""
n_wa = ""
n_yo = ""

letters = set(x for x in sy + so + wa + yo)

arr = sorted(list(letters))

result = list()

for combi in itertools.permutations(arr, 10):
    combined_number = ''.join(map(str, combi))
    if (combined_number[0] != 'S' and combined_number[0] != 'W' and combined_number[0] != 'Y'):
        arr_dict = dict({char: i for i, char in enumerate(combined_number)})

        for key in sy:
            n_sy += str(arr_dict[key])
        for key in so:
            n_so += str(arr_dict[key])
        for key in wa:
            n_wa += str(arr_dict[key])
        for key in yo:
            n_yo += str(arr_dict[key])

        # 숫자 해독이 가능한 케이스
        if int(n_sy) + int(n_so) == int(n_wa) + int(n_yo):
            result.append(dict(arr_dict))

        # 초기화
        arr_dict.clear()
        n_sy = ""
        n_so = ""
        n_wa = ""
        n_yo = ""

print(result)

total_value = 0
for interpreted_number in result:
    for key in sy:
        n_sy += str(interpreted_number[key])
    for key in so:
        n_so += str(interpreted_number[key])

    total_value += int(n_sy) + int(n_so)

    n_sy = ""
    n_so = ""

print(total_value)