코드메모장

(1) 문제

• 위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
• 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
• 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

(2) 입력

• 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

(3) 출력

• 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys

length = int(sys.stdin.readline())

triangle_list = []

for i in range(length):
    triangle_list.append(list(map(int,input().split())))
    

def bfs(i):
    if i == 0:
        return triangle_list[0][0]
    for j in range(len(triangle_list[i])):
        
        if 0 < j < len(triangle_list[i]) - 1:
            rigth_up = triangle_list[i][j] + triangle_list[i - 1][j]
            left_up = triangle_list[i][j] + triangle_list[i - 1][j - 1]

            if left_up > rigth_up:
                triangle_list[i][j] = left_up
            else:
                triangle_list[i][j] = rigth_up

        elif j == 0:
            rigth_up = triangle_list[i][j] + triangle_list[i - 1][j]
            triangle_list[i][j] = rigth_up

        elif j == len(triangle_list[i]) - 1:
            left_up = triangle_list[i][j] + triangle_list[i - 1][j - 1]
            triangle_list[i][j] = left_up
            

for i in range(length):
    bfs(i)

print(max(triangle_list[length - 1]))

(6) 실행결과

(1) 문제

• RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
• 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

(2) 입력

• 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

(3) 출력

• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys

length = int(sys.stdin.readline())

RGB_price_list = []

for i in range(length):
    RGB_price_list.append(list(map(int, sys.stdin.readline().split())))

def bfs(i):
    for j in range(len(RGB_price_list[i])):
        # if RGB_price_list[i - 1][(j + 1) % 3] < RGB_price_list[i - 1][(j + 2) % 3]:
        #     RGB_price_list[i][j] = RGB_price_list[i - 1][(j + 1) % 3] + RGB_price_list[i][j]
        # else:
        #     RGB_price_list[i][j] = RGB_price_list[i - 1][(j + 2) % 3] + RGB_price_list[i][j]    

        RGB_price_list[i][j] +=  min(RGB_price_list[i - 1][(j + 1) % 3], RGB_price_list[i - 1][(j + 2) % 3])
                     

for i in range(1, length):
    bfs(i)

print(min(RGB_price_list[length - 1]))

(6) 실행결과

(1) 문제

• 아래 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
• 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
• N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

(2) 입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

(3) 출력

• 각 테스트 케이스마다 P(N)을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys
length = int(sys.stdin.readline())

memo = {
    1 : 1,
    2 : 1,
    3 : 1,
    4 : 2,
    5 : 2
}

def triangle_length(n, memo):
    if n in memo:
        return memo[n]
    else:
        memo[n] = triangle_length(n -1,memo) + triangle_length(n - 5,memo)        
        return memo[n]

for i in range(length):
    step = int(sys.stdin.readline())
    print(triangle_length(step,memo))

(6) 실행결과

(1) 문제

• 재귀 호출만 생각하면 신이 난다! 아닌가요?
• 다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

• 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)
• a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

(2) 입력

• 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
• -50 ≤ a, b, c ≤ 50

(3) 출력

• 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys

memo = {

}

def w(a, b, c, memo):
    str_abc = str(a) + '0' + str(b) + '0' + str(c)

    if a <= 0 or b <= 0 or c <= 0:
        return 1

    elif a > 20 or b > 20 or c > 20:
        result = w(20, 20, 20, memo)
        return result

    if str_abc in memo:
        return memo[str_abc]

    else:
        if a < b and b < c:
            result = w(a, b, c-1, memo) + w(a, b-1, c-1, memo) - w(a, b-1, c, memo)
            memo[str_abc] = result
            return result
        else :
            result = w(a-1, b, c, memo) + w(a-1, b-1, c, memo) + w(a-1, b, c-1, memo) - w(a-1, b-1, c-1, memo)
            memo[str_abc] = result
            return result

while True:
    a, b, c = list(map(int, sys.stdin.readline().split()))
    if a == -1 and b == -1 and c == -1:
        break
    result = w(a,b,c, memo)
    print("w(%d, %d, %d) = %d" % (a, b, c, result))

(6) 실행결과

(1) 문제

• 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.
• 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.
• 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.
• 따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.
• 숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

(2) 입력

• 첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

(3) 출력

• 첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

length = int(input())

n = length

cur_n =1
number = 667

while n != cur_n:
    if '666' in str(number):
        cur_n += 1
    number += 1

print(number - 1)

(6) 실행결과

(1) 문제

• 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
• 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
• 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
• 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

(2) 입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
• 입력의 마지막에는 0이 주어진다.
• 1 ≤ n ≤ 123,456

(3) 출력

• 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

• n이 123456 이하로 제한되어 있어 소수를 미리 구하고 비교

import sys
import math

prime = []

for i in range(2, (123456 * 2) + 1):
    prime_check = True
    #제곱근 구하기
    sqrt_number = int(math.sqrt(i + 1))
    for j in range(2, sqrt_number + 1):
        if i % j == 0:
            prime_check = False
            break
    if prime_check:
        prime.append(i)

while True:
    number = int(sys.stdin.readline())
    count = 0
    if number == 0:
        break

    for element in prime:
        if element > number:
            if element <= number * 2:
                count += 1
            else:
                break
    
    print(count)

• 글자수 사이의 소수를 실시간으로 구하기(python3로 하면 시간초과 pypy통과)

import math
import sys

while True:
    number = int(sys.stdin.readline())
    if number == 0:
        break
    min_number = number + 1
    max_number = number * 2

    prim_count = 0

    for i in range(min_number, max_number + 1):
        prime_check = True
        #제곱근 구하기
        sqrt_number = int(math.sqrt(i + 1))
        for j in range(2, sqrt_number + 1):
            if i % j == 0:
                prime_check = False
                break
        if prime_check:
            prim_count += 1

    print(prim_count)

(6) 실행결과

(1) 문제

• 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.
• 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )

• 김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.
• 김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

(2) 입력

• 입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

(3) 출력

• 각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import math
import sys
length = int(sys.stdin.readline())

for i in range(length):
    date_conut = 0
    x, y = sys.stdin.readline().split()
    x = int(x)
    y = int(y)
    distance = y - x
    if distance <= 3:
        print(distance)
    else:        
        square_root = int(math.sqrt(distance))
        
        if distance == square_root ** 2:
            date_conut = 2 * square_root - 1
        elif distance > square_root ** 2  and distance <= square_root ** 2 + square_root:
            date_conut = 2 * square_root
        else:
            date_conut = 2 * square_root + 1    
        print(date_conut)

(6) 실행결과

(1) 문제

• 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
• 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
• 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

(2) 입력

• 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

(3) 출력

• 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys

FIVE = 5
THREE = 3

sugar = int(sys.stdin.readline())

min_x = sugar // FIVE
min_y = (sugar - (FIVE * min_x)) // THREE

while True:
    if min_x * FIVE + min_y * THREE == sugar:
        print(min_x + min_y)
        break
    else:
        min_x -= 1
        min_y = (sugar - (FIVE * min_x)) // THREE

    if min_x == -1:
        print(-1)
        break

(6) 실행결과

(1) 문제

• 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
• 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

(2) 입력

• 첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

(3) 출력

• 첫째 줄에 그룹 단어의 개수를 출력한다.

(4) 예제 입력 및 출력

(5) 코드

import sys
length = int(sys.stdin.readline())

group_count = 0

def is_group_word(string):
    is_exist = []
    for index in range(len(string)):
        if string[index] in is_exist:
            if string[index - 1] != string[index]:
                return False
        else:
            is_exist.append(string[index])
    return True

for i in range(length):
    string = sys.stdin.readline()
    if is_group_word(string):
        group_count += 1

print(group_count)

(6) 실행결과

(1) Deque(DoubleEndedQueue)란?

• Deque(DoubleEndedQueue)는 앞,뒤 양방향 모두 데이터 처리가 가능한 자료구조이다.
• 큐와 스택 기능을 모두 가지고있어 원하는대로 사용하면 된다.
• Collections 내에 내장되어있어 import collections을 해줘야 사용이 가능하다.
• 장점
  • Deque는 어느 방향에서나 거의 동일한 O(1) 성능으로 데크의 양쪽에서 스레드 안전, 메모리 효율적인 추가 및 팝을 지원한다.

(2) Deque Class 및 함수

class collections.deque([iterable[, maxlen]])

• append(x) - 오른쪽에 x값 추가
• appendleft(x) - 왼쪽에 x값 추가
• clear() - 전체 요소 제거
• copy() - deque 복사
• count(x) - x와 같은 요소 갯수
• extend(iterable) - 오른쪽에 반복가능한 인수의 요소를 추가
• extendleft(iterable) - 왼쪽에 반복가능한 인수의 요소를 추가
• index(x) - x의 위치를 반환
• insert(i,x) - x를 i에 삽입
• pop() - 오른쪽 요소를 제거하고 반환
• popleft() - 왼쪽 요소를 제거하고 반환
• remove(x) - 값이 x인 첫번째 항목을 제거
• reverse() - 요소를 뒤집는다
• rotate(n) - n만큼 요소들을 오른쪽으로 이동(맨오른쪽에있는요소는 맨왼쪽으로 이동)

(3) 사용법

from collections import deque

deque = deque()

deque.append('a')
print(deque)                #deque(['a'])

deque.appendleft('b')
print(deque)                #deque(['b', 'a'])

temp_deque = deque.copy()
print(temp_deque)           #deque(['b', 'a'])

deque.clear()
print(deque)                #deque([])

deque.extend(temp_deque)
print(deque)                #deque(['b', 'a'])

deque.append('c')
print(deque)                #deque(['b', 'a', 'c'])

deque.extendleft(temp_deque)
print(deque)                #deque(['a', 'b', 'b', 'a', 'c'])

print(deque.index('b'))     #1

deque.insert(3,'d')
print(deque)                #deque(['a', 'b', 'b', 'd', 'a', 'c'])

print(deque.pop())          #c
print(deque)                #deque(['a', 'b', 'b', 'd', 'a'])

print(deque.popleft())      #a
print(deque)                #deque(['b', 'b', 'd', 'a'])

deque.remove('d')           #deque(['b', 'b', 'a'])
print(deque)

deque.reverse()             #deque(['a', 'b', 'b'])
print(deque)

deque.rotate(1)             #deque(['b', 'a', 'b'])
print(deque)

참조 - docs.python.org/3/library/collections.html