프로그래밍 수학 - 실력 테스트

암호 해독

앨리스와 밥은 절친한 친구 사이로, 평소 둘만의 암호를 편지로 주고 받으며 비밀 약속을 하곤 하였습니다. 둘 사이를 질투하는 이브는 편지를 몰래 훔쳐보았지만 거기에는 단지 정체모를 숫자만 적혀있을 뿐이었습니다.

믿을만한 정보통에 의하면 앨리스와 밥이 암호를 주고받는 과정은 다음과 같다고 합니다.

두 명 중 한명이 소수 하나를 적어 누구나 볼 수 있는 장소에 공개합니다. 이를 공개번호라고 합니다. 앨리스와 밥은 각자 자신만의 소수를 하나 정하여 그 공개번호에 곱합니다. 이 때 정한 소수는 혼자만이 볼 수 있습니다. 곱하여 나온 번호를 편지에 적어 서로 교환합니다. 각자 받은 편지에 적힌 숫자에 자신의 비밀숫자를 곱하면 둘은 동일한 숫자를 공유하게 된다고 합니다. 이브는 이 공유숫자를 알아내는 일이 먼저라고 판단하였습니다. 이에 이브는 이 일의 의뢰자로 당신을 선택했습니다. 정의롭지 못한 일이지만 거절할 수 없는 액수의 보수에 당신은 일일 악당을 자처했습니다.

이브의 정보를 바탕으로 앨리스와 밥의 비밀숫자를 알아내는 프로그램을 작성해봅시다.

• 입력

p: 앨리스가 밥에게 보내는 숫자  
q: 밥에 앨리스에게 보내는 숫자

• 출력

둘의 공유숫자

• 실행 결과

>> decrypt(6, 10)  
30

해설: 6 = 2x3, 10 = 2x5이므로 공개번호는 2이며 앨리스의 비밀 소수는 3, 밥의 비밀 소수는 5이다. 따라서 둘의 비밀 숫자는 2x3x5 = 30

• 이렇게 해보세요!

먼저 앨리스와 밥이 서로에게 보내는 메세지 p와 q를 소인수분해 해보세요.

소인수 분해 결과에서 공통된 소수를 찾고 이를 이용하여 앨리스와 밥의 비밀 소수를 알아내보세요.

알아낸 비밀 소수와 공개 소수를 사용하여 공유 숫자를 계산하세요.

def decrypt(p, q):
    Max = max(p, q)
    
    check = [False for i in range(Max+1)]
    
    result = []
    
    for i in range(2,Max+1):
        if not check[i]:
            result.append(i)
            tmp = i
            while tmp + i<=Max:
                tmp += i
                check[tmp] = True
                
    print(result)
    
    ###############################
    p_list = []
    q_list = []
    ###############################
    
    for re in result:
        while True:
            if p%re == 0:
                p_list.append(re)
                p/=re
                continue
            if q%re == 0:
                q_list.append(re)
                q/=re
            else:
                break
                
    print(p_list)
    print(q_list)
    
    ###############################
    
    tmp = [] 
    
    for i in p_list:
        tmp.append(i)
        
    for j in q_list:
        if j not in p_list:
            tmp.append(j)
    
    print(tmp)
    
    mul = 1
    
    for i in tmp:
        mul*=i
    
    return mul
    
print(decrypt(6,10))

[2, 3, 5, 7]
[2, 3]
[2, 5]
[2, 3, 5]
30

금고 털기

암호 해독에 성공한 이브는 그들의 공유 숫자를 알아내는데 성공했고 이 숫자는 앨리스와 밥이 만나기로 한 장소와 1:1로 매칭된다는 사실을 알게되었습니다.

믿을만한 정보통에 의해 전해진 정보는 다음과 같습니다.

밥의 방에는 여러개의 서랍이 있고 각 서랍에는 공유숫자와 장소가 적힌 쪽지가 들어있다 하지만 서랍마다 자물쇠가 걸려있어 해제에 시간이 걸리기 때문에 이브가 확인 할 수 있는 서랍은 최대 10개이다. 서랍은 공유숫자에 따라 오름차순 정렬되어 있다. 이브는 약속장소를 알아내는 이번 일에 지난번에 활약한 당신을 다시 한번 고용하기로 하였습니다. 당신은 이번일은 본격적인 범죄가 되는것 같아 거절하려 했으나 그러기에는 너무도 많은 돈이었습니다.

밥의 서랍은 최대 1000개까지도 존재하기 때문에 순서대로 확인하는 방법으로는 시간 안에 일을 끝마치지 못합니다. 정보통의 마지막 정보에 초점을 두고 효율적으로 서랍을 확인하는 프로그램을 작성해 봅시다.

• 입력

e: 공유 숫자  
n: 서랍의 개수 (최대 1000개)  
desk: 서랍장

• 출력

약속 장소

Desk 이번 미션에서 서랍을 열기 위해서는 다음과 같은 코드를 사용합니다

# 첫 번째 서랍을 연다
>> desk.open(0)
(11, '서울')

위 예제에서 만약 공유 숫자 e가 11이였다면 답은 “서울”이 됩니다.

서랍을 열때마다 카운트가 올라가며 11번째가 되면 실패하게 됩니다.

• 실행 결과

# desk = [(11, '서울'), (23, '경기'), (37, '강원')]  
>> crack(23, 3, desk)  
경기

해석: desk안에서 23에 해당하는 장소는 ‘경기’이므로 답은 “경기”. 처음부터 열어본다고 하면 2번째 만에 찾으므로 성공한다.

• 이렇게 해보세요!

desk.open()으로 적당한 위치의 서랍을 열어 쪽지의 번호를 확인해보세요.

찾고자하는 번호가 연 서랍의 쪽지의 번호 보다 작다면 지금보다 앞쪽 서랍을 열고, 더 크다면 뒤쪽 서랍을 열어보세요.

원하는 번호가 나올때까지 위 과정을 반복하여 시도해보세요.

• Tip

업-다운 게임을 생각하면 쉽게 해결할 수 있습니다.

이진 탐색에 대해 검색해 봅시다.

#main.py
import desk_class

def ham(e, start, end, desk):
    mid = (start+end)//2
    
    num, re = desk.open(mid)
    
    if num < e:
        return ham(e,mid+1,end,desk)
    elif num > e:
        return ham(e,start,mid-1,desk)
    return re
    
def crack(e, n, desk):
    # 1 ~ 8    
    return ham(e, 1, n, desk)
    
desk = desk_class.ex_desk
print(crack(11, 3, desk))

# desk_class.py
class Desk():
    def __init__(self, d):
        self.counter = 0
        self.drawer = d
    
    def open(self, n):
        self.counter += 1
        return self.drawer[n-1]
        
ex_desk = Desk([
    (11, '서울'),
    (23, '경기'),
    (37, '강원'),
    (41, '충청'),
    (56, '전라'),
    (62, '경상'),
    (73, '제주'),
    (88, '독도')
])

서울

미션

지난번의 의뢰로 인해 앨리스와 밥의 약속 장소를 알게 된 이브는 이제 둘의 만남을 염탐하기로 결심했습니다. 미리부터 따라다니면 들킬확률이 늘어나므로 이브는 정확한 시간에 움직이고자 합니다.

이제는 얼굴이 익숙한 믿을만한 정보통이 밥의 평소 동선을 면밀히 관찰하여 그간의 외출 시간과 앨리스와의 약속 여부를 제공한다고 합니다. 이쯤되면 그의 정체가 궁금해집니다. 아무튼 그가 제공하는 정보는 다음과 같습니다.

(약속 시간, 앨리스와의 약속 여부) 형태의 튜플 여러개로 이루어진 리스트

[
    (9, True),
    (11, True),
    (15, False),
    ...
]

약속 시간은 0시~23시 중 하나이며 앨리스와의 약속 여부는 True, False로 나타냅니다.

이브는 다음의 데이터를 바탕으로 밥이 특정 시간에 외출했을 때 앨리스를 만날 확률이 가장 높은 시간을 추측하는 프로그램을 작성하도록 지시했습니다. 만약 밥이 외출한 적이 없는 시간의 경우 확률은 0으로 간주합니다. 주님, 오늘도 정의로운 범죄자가 되는것을 허락해주세요.

• 입력

outing_info: 밥의 외출 일정 리스트

• 출력

시간 T에 외출했을 때 앨리스를 만날 확률이 가장 높은 시간 T. 확률이 동일하다면 더 이른 시간을 선택한다.

• 실행 결과

>>> tailing([(9, True), (11, True), (15, False)])
9
>>> tailing([(7, True), (9, True), (16, True), (15, False), (1, False), (19, True), (0, False),
(19, False), (16, True), (13, True)])
7

• 이렇게 해보세요!

사건 A를 앨리스를 만나는 사건, 사건 B_T를 시간 T에 외출한 사건으로 설정해보세요.

시간 T에 외출했다고 했을 때 앨리스를 만날 확률은 P(A1B_T))이므로 베이지안 확률로 이를 계산해 보세요.

모든 시간에 대해 조건부 확률을 계산하고 가장 높은 확률을 가지는 시간을 찾아보세요.

def tailing(outing_info):
    
    arr1 =[0 for i in range(24)]
    arr2 =[0 for i in range(24)]
    
    for i in outing_info:
        if i[1]:
            arr1[i[0]]+=1
            
    #print(arr1)
    
    for i in outing_info:
        arr2[i[0]]+=1
        
    #print(arr2)
    
    Max = 0
    max_index = -1
    for i in range(24):
        if arr2[i] == 0:
            continue
        if Max < arr1[i]/arr2[i]:
            Max = arr1[i]/arr2[i]
            max_index = i
            
    return max_index

print(tailing([(9, True), (11, True), (15, False)]))
print(tailing([(7, True), (9, True), (16, True), (15, False), (1, False), (19, True), (0, False), (19, False), (16, True), (13, True)]))

9
7

영상 확대

앨리스와 밥이 만나는 시간대 중 높은 확률을 가진 시간에 밥을 미행한 결과 두 사람이 만나는 장면을 목격한 이브. 둘은 카페 ‘Coffee Jeohang’에서 무언가를 종이에 적으며 대화를 나누고 있습니다. 이브는 종이에 적힌 내용이 매우 궁금했지만 거리가 너무 멀어 잘 보이지 않습니다.

이브는 이런 일이 있을 줄 알고 믿을만한 정보통으로부터 SR(Super Resolution) 기술의 핵심 구조를 알아왔다고 합니다. 그의 설명에 따르면 다음과 같은 방법으로 이미지의 작은 부분을 고해상도로 늘릴 수 있다고 합니다.

확대하고자 하는 이미지를 II라고 했을 때 커널 3개를 순서대로 2D 컨볼루션 연산하면 놀랍게도 확대된 이미지가 나타난다고 합니다. 인풋 데이터로 각각의 커널 정보와 함께 컨볼루션에 적용되는 제로 패딩 값과 스트라이드 정보가 (K, p, s) 형태로 주어집니다.

[
    (np.array([[1, 0], [0, 1]]), (0, 0), (1, 1)),
    (np.array([[1, 2], [3, 4]]), (1, 1), (2, 2)),
    (np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]]), (1, 2), (1, 2))
]

이브는 위의 정보를 바탕으로 당신에게 어서 이미지 확대 프로그램을 작성하라고 전했습니다. 당신은 이번 일만 끝나면 해외 어딘가 틀어박혀 평온히 지내리라 결심하면서 키보드에 손을 얹었습니다.

※ 커널을 뒤집지 않고 계산합니다.

• 입력

I: 원본 이미지 numpy 배열  
conv_info: (K, p, s) 형태의 튜플 3개가 든 리스트
    K: 커널 numpy 배열
    p: 제로 패딩 정보 튜플 (h, w)
    s: 스트라이드 정보 튜플 (h, w)   

• 출력

I에 각 커널을 순서대로 2D 컨볼루션 한 결과

• 실행 결과

>>> sr(array([[1, 0, 1, 0],
...           [0, 1, 0, 1],
...           [1, 0, 0, 1],
...           [0, 1, 1, 0]]),
...    [
...       (array([[1, 1], [1, 1]]), (1, 1), (1, 1)),
...       (array([[1, 1], [1, 1]]), (0, 0), (1, 1)),
...       (array([[1, 1], [1, 1]]), (0, 0), (2, 2))])
array([[24. 24.]
       [24. 25.]])

• 이렇게 해보세요!

I, K, p, s가 주어졌을 때 2D 컨볼루션을 행하는 함수를 작성해보세요.

작성한 함수를 사용해서 주어진 커널을 차례로 이미지에 2D 컨볼루션 연산해보세요.

• Tip

실제로 필터 몇장을 컨볼루션한다고 해상도가 올라가지는 않습니다만, 딥러닝을 이용한 SR기술 중에는 수많은 필터를 컨볼루션하는 방법으로 이를 구현하는 방법도 존재합니다.

img_data.py

from img_data import img_data
import numpy as np

def sr(I, conv_info):

    for k in range(len(conv_info)):
    
        K = conv_info[k][0]
        p_h = len(K)
        p_w = len(K[0])
        K_t = np.array((p_h, p_w))
        P = np.array(conv_info[k][1])
        S = np.array(conv_info[k][2])

        h = len(I)
        w = len(I[0])

        I = np.pad(I, ((P[0],P[0]),(P[1],P[1])), 'constant', constant_values=0)

        I_len = np.array((h, w))

        a = (I_len - K_t + 2 * P)/S + 1

        a = a.astype(np.int64)

        ze = np.zeros(a)

        #################################
        for i in range(a[0]):
            for j in range(a[1]):
                pi = i*S[0]
                pj = j*S[1]
                b = I[pi:pi+K_t[0],pj:pj+K_t[1]]*K
                ze[i][j] = b.sum()
        I = ze
    return I

# 결과 출력을 위한 코드입니다. 자유롭게 값을 바꿔보며 확인해보세요.
print(sr(img_data,
    [(np.array([[0.37914178], [0.13646277], [0.60444785], [0.38037229],[0.49934981]]), (1, 0), (1, 3)),
     (np.array([[0.00310856, 0.74939736, 0.2204316 , 0.69683005], [0.76133071, 0.43496928, 0.10401057, 0.5994197 ]]), (1, 0), (3, 2)), 
     (np.array([[0.07662133, 0.25300788, 0.29004057, 0.4892341 ], [0.76413049, 0.80572028, 0.93174801, 0.32110102], [0.29205757, 0.01265993, 0.77292819, 0.88364807], [0.66241493, 0.74710932, 0.13501994, 0.07417719], [0.074782  , 0.51340079, 0.77992905, 0.84407727]]), (0, 1), (3, 2))]
))

[[25.84547133 30.32256403 23.38397975]
 [29.84653428 38.58435185 27.01115747]
 [28.35008071 35.84956207 26.36755825]
 [27.7105097  35.98255492 25.61065853]]

소수 사이의 수

어떤 소수 p와, p 바로 다음의 소수 p+n 사이에는 n-1개의 합성수들이 있다.

이 n-1개의 합성수들을 “소수 사이 수열” 이라고 한다.

예를 들어, 7과 11의 소수 사이 수열은 {8, 9, 10}이고, 길이가 3이다.

23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이가 5이다.

solve 함수의 입력으로 자연수 k가 주어졌을 때, solve 함수는 k를 포함하는 “소수 사이 수열”의 길이를 구하여 반환하면 된다.

k는 1보다 크며 9592번째 소수인 100003보다 작은 정수이다.

• 예시

k가 10이라면, k를 포함하는 소수 사이 수열은 {8, 9, 10}이므로 k를 포함하는 소수 사이 수열의 길이는 3이다.

주의 : 주어진 solve 함수의 이름을 변경할 경우 오류가 발생할 수 있습니다.

def solve(k) :
    result = []
    arr = [0 for i in range(200000)]
    for i in range(2, 200000):
        if arr[i]:
            continue
            
        result.append(i)
        
        if i>k:
            break
            
        tmp = i
        while tmp+i<200000:
            tmp+=i
            arr[tmp] = 1
    
    if k in result:
        return 0
    
    return result[-1] - result[-2] - 1
print(solve(3))

0

소수번째 계단

엘리스는 계단을 오르는 중이다.

그런데 계단이 너무 높아 올라가는 중 계단에 걸터앉아 휴식을 취하려고 한다.

다만 엘리스는 소수를 매우 사랑한다.

따라서 되도록이면 휴식을 위해 걸터앉는 계단은 소수번째 계단이길 원한다.

엘리스가 현재 서 있는 계단이 k번째 계단일 때, 최소 계단을 몇 개 더 올라가야 소수번째 계단에서 휴식을 취할 수 있을지 구하는 함수를 작성해보자.

계단은 총 10만개이며, 만약 엘리스가 서 있는 계단으로부터 앞으로 소수번째 계단이 없는 경우는 -1을 반환한다.

k는 2 이상 10만 이하의 자연수이다.

• 예시

k가 44라면, 엘리스는 계단을 3번 더 올라가 47번째 계단에서 휴식을 취할 수 있다.

따라서 solve(44)는 3을 반환해야 한다.

k가 83이라면, 엘리스는 이미 소수번째 계단에 있으므로 계단을 올라갈 필요가 없다.

따라서 solve(83)은 0을 반환해야 한다.

• Tip!

에라토스테네스의 체를 이용한다.

주의 : 주어진 함수의 이름을 변경할 경우 오류가 발생할 수 있습니다.

def solve(k) :

    result = []
    
    arr = [0 for i in range(100001)]
    for i in range(2, 100001):
        if arr[i]:
            continue
            
        result.append(i)
        
        if i>=k:
            break
            
        tmp = i
        while tmp+i<100001:
            tmp+=i
            arr[tmp] = 1
    
    if result[-1] - k<0:
        return -1
    
    return result[-1] - k

print(solve(4))

1