둔필승총

(https://school.programmers.co.kr/learn/courses/30/lessons/214289)

[문제 정보]

먼저 온도가 여러 개 나오는데 실내온도, 실외온도, 희망온도가 주어지고, 또 승객들 등등 여러 가지 정보가 한번에 나온다. 한번에 읽으면 정리가 안되기 때문에 어떤 걸 해결해야하는지 고민해봐야 한다. 

먼저 온도가 변하는 것을 생각하지 말고 온도가 어떤 범위 내에 있어야 하는지를 생각해보자. 승객이 있을 때는 온도는 t1~t2에 있어야 한다. 그리고 승객이 없을 때는 온도가 어디든지 사실 상관이 없다. 그러나 문제는 온도는 1도씩밖에 바뀌지 않기 때문에 승객이 있기 1분 전에는 반드시 t1-1에 있거나 t2+1에 있어야 승객이 있을 때 범위 내에 있게 된다. 

이번엔 온도가 어떻게 변하는지 살펴보겠다. 일단 에어컨이 꺼져 있을 경우, 온도는 실외온도를 따라간다. 에어컨을 껐는데 실외온도에 차이가 없다면 온도는 그대로 유지가 된다.

에어컨이 켜져 있을 경우엔 2가지 이다. 에어컨을 켜고 온도를 유지하는 경우와 에어컨을 켜서 실내온도와 반대 방향으로 1도 변경하는 경우이다. 

이렇게 단계적으로 생각해보면 희망온도는 사실 의미가 없다. 에어컨을 켜서 온도를 변하게 할 것인지 아니면 유지할 것인지의 문제일 뿐이다.

• 에어컨 X, 실내온도 방향으로 1도 변경하는 경우(비용 0)
• 에어컨 X, 온도를 유지하는 경우(비용 0)
• 에어컨 O, 온도를 유지하는 경우(비용 b)
• 에어컨 O, 온도를 실내온도와 반대 방향으로 1도 변경하는 경우(비용 a)

여기까지 이해하고 문제를 풀면 된다.

[문제 해설]

먼저 시간의 흐름이 있고, 온도의 변화도 있으므로 dp 2차원을 생각해내야 한다. 시간이 흐름에 따라 온도가 어떻게 변화하는지 확인하여 최적의 비용을 계산할 수 있기 때문이다.

DP를 사용하려면 문제가 있다. 지금 온도 범위는 -10도에서 40도까지인데 2차원 배열의 인덱스에는 음수가 들어갈 수 없다는 점이다. 그래서 온도를 임의로 10도씩 올려서 계산한다. 

그리고 dp를 사용하여 int(1e9)의 큰 값으로 모든 값들을 초기화 한다.

처음의 온도는 실외온도와 같다고 하였으므로 dp[0][temperature]은 0으로 초기화해준다. (여기가 출발점이다.)

그 이후에는 dp를 1부터 주어진 onboard의 길이까지 진행하면 된다. 

승객이 있을 경우는 dp 온도를 t1에서 t2만 구하면 된다. 그리고 승객이 없다면 나머지를 굳이 구할 필요없이 min(t1, 실외온도) 에서 max(t2, 실외온도)로 구하면 된다. 실외온도는 t1~t2 바깥 값이므로 이렇게 범위를 구하면 된다. 온도가 계속하여 이 사이의 값에 있어야 효율적임을 알 수 있다. 이유는 예시를 하나 생각해보면 된다. t1이 10도 이고, 실외온도가 8도라고 가정하면 8도 이상이어야 된다. 에어컨을 사용하여 8도 밑으로 내려갈 이유가 없다. (에어컨의 소비전력이 최소화가 되지 않는다)

그래서 먼저 범위를 구해주고 범위내의 dp값을 업데이트하는 식을 통해서 진행하면 된다. 

이 업데이트 하는 식이 조금 고민해야 한다. 

for j in range(start, end + 1):
    if j - 1 < 0:
        x = int(1e9)
    else:
        x = dp[i - 1][j - 1]
    if j + 1 > 50:
        y = int(1e9)
    else:
        y = dp[i - 1][j + 1]
    if j < temperature:
        dp[i][j] = min(x, y + a, dp[i - 1][j] + b)
    elif j > temperature:
        dp[i][j] = min(x + a, y, dp[i - 1][j] + b)
    elif j == temperature:
        dp[i][j] = min(x, y, dp[i - 1][j])

여기서 먼저 j-1이 0보다 작거나 j+1이 50을 넘어가면 계산이 안되므로 해당 값들을 처리해준다. 

먼저 j가 실외온도보다 낮을때 처리하는 경우를 생각해보자. dp[i][j]는 i분에 j온도가 되기 위한 비용이다. 

첫번째 먼저 i-1분에 j-1온도일 때는 실외온도를 따라가므로 에어컨이 없더라도 1도 올라간다. 

두번째 i-1분에 j+1온도일 때는 실외온도를 따라가면 j+2가 되거나 j+1이 유지(실외온도가 j+1이라면)되므로 j가 되기 위해서는 에어컨을 틀어서 온도를 낮춰야 한다. 

세번째 i-1분에 j온도일때는 유지만 하면 된다. 만약 에어컨을 끄면 실외온도를 따라가서 온도가 올라가므로 유지하려면 에어컨을 켜서 유지해야 한다. 에어컨이 유지하는 비용은 b라고 명시해주었다. 따라서 식은 다음과 같다. 여기서 x는 dp[i-1][j-1], y는 dp[i-1][j+1]이라고 생각하면 된다.

if j < temperature:
    dp[i][j] = min(x, y + a, dp[i - 1][j] + b)

그 다음에는 j가 실외온도보다 높을때 살펴보겠다. 

먼저 현재온도가 j-1이라면 j가 되려면 에어컨을 켜야한다. 아니면 실외온도를 따라가므로 온도가 떨어지거나 유지되기 때문이다.

두번째 j+1온도라면 실외온도를 그냥 따라가면 내려가므로 에어컨을 꺼도 된다.

세번째 j온도라면 유지를 해야한다. 그럼 그냥 b 비용을 내면된다. 이 세 개중에서 최소가 dp[i][j]가 된다.

elif j > temperature:
    dp[i][j] = min(x + a, y, dp[i - 1][j] + b)

마지막으로 j와 실외온도가 같을때 이다.

첫번째 현재온도가 j-1이라면 실외온도를 따라 올라가면 되므로 에어컨이 필요없다.

두번째 현재온도가 j+1이라면 실외온도를 따라 내려가면 되므로 에어컨이 필요없다.

세번쨰 현재온도가 j라면 실외온도 현재온도 목표온도가 다 같으므로 그냥 나두면 된다.

elif j == temperature:
    dp[i][j] = min(x, y, dp[i - 1][j])

이렇게 점화식을 계산하고 마지막 dp[i][j]에서 i가 onboard의 마지막일때 가능한 비용들이 나온다. 이 중 최소값이 정답이 되게 된다.

[코드]

def solution(temperature, t1, t2, a, b, onboard):
    temperature = temperature + 10
    t1 = t1 + 10
    t2 = t2 + 10

    dp = [[int(1e9)] * 51 for _ in range(len(onboard))]
    dp[0][temperature] = 0
    for i in range(1, len(onboard)):
        if onboard[i] == 1:
            start = t1
            end = t2
        else:
            start = min(t1, temperature)
            end = max(t2, temperature)
        for j in range(start, end + 1):
            if j - 1 < 0:
                x = int(1e9)
            else:
                x = dp[i - 1][j - 1]
            if j + 1 > 50:
                y = int(1e9)
            else:
                y = dp[i - 1][j + 1]
            if j < temperature:
                dp[i][j] = min(x, y + a, dp[i - 1][j] + b)
            elif j > temperature:
                dp[i][j] = min(x + a, y, dp[i - 1][j] + b)
            elif j == temperature:
                dp[i][j] = min(x, y, dp[i - 1][j])
        if i == len(onboard) - 1:
            return min(dp[len(onboard) - 1])

[후기]

실제 현대모비스 알고리즘 대회 때 머리만 싸매다가 못풀었었는데.. 다시 풀어도 머리가 터질 뻔했었다.
어려운 알고리즘이 있는 것보다 더 어려운 문제가 아닐까..(dp만 알면 풀 수는 있는)
그래도 좋은 문제 같아서 나중에 코딩 테스트 전에 한번 풀어보면 또 좋을것 같다.

알고리즘 문제를 풀다가 출력 부분을 해결할 때, 문자열을 join 함수로 사용하는 방법을 많이 보아서 알아볼려고 하였다.

join 함수

형태 : 구분자.join(리스트)

join 함수는 매개변수로 들어온 리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환하는 함수이다.

• ''.join(리스트) ''.join(리스트)를 이용하면 매개변수로 들어온 ['a', 'b', 'c'] 이런 식의 리스트를 'abc'의 문자열로 합쳐서 반환해주는 함수인 것이다.
• '구분자'.join(리스트) '구분자'.join(리스트)를 이용하면 리스트의 값과 값 사이에 '구분자'에 들어온 구분자를 넣어서 하나의 문자열로 합쳐줍니다.

ex>

a = ['a', 'b', 'c', 'd', '1', '2', '3']
print(a)
print("".join(a))
# 'a', 'b', 'c', 'd', '1', '2', '3'
# abcd123

그래서 임의의 구분자를 리스트 요소 사이사이에 넣어줄 수도 있다.

# 원본 리스트
a = ['BlockDMask', 'python', 'join', 'example']
print(a)
print()
 
# 리스트를 문자열로 합치기
result1 = "_".join(a)
print(result1)
 
# 리스트를 문자열로 합치기
result2 = ".".join(a)
print(result2)

# ['BlockDMask', 'python', 'join', 'example']
# BlockDMask_python_join_example
# BlockDMask.python.join.example

파이썬은 map, filter와 같은 함수형 기능을 지원하며 다음과 같은 람다 표현식도 지원한다.

list(map(lambda x:x+10,[1,2,3]))
# [11,12,13]

리스트 컴프리헨션

리스트 컴프리헨션이란 기존 리스트를 기반으로 새로운 리스트를 만들어내는 구문으로, 파이썬 2.0부터 지원되었으며 파이썬의 대표적인 특징이다. 

람다 표현식에 map이나 filter를 섞어서 사용하는 것에 비해 가독성이 훨씬 높다.

Ex> 홀수인 경우 2를 곱해 출력하라는 리스트 컴프리헨션

[n*2 for n in range(1,10+1) if n%2 == 1]
# [2, 6, 10, 14, 18]

만약에 리스트 컴프리헨션을 사용하지 않는다면 다음과 같이 작성해야 한다.

a=[]
for n in range(1,10+1):
    if n%2 == 1:
        a.append(n*2)

파이썬은 리스트만 가능한것이 아니라 딕셔너리도 가능하다.

a={}
for key,value in original.items():
    a[key] = value
# 위의 코드를 아래와 같이 바꿀 수 있다
a={key:value for key,value in original.items()}

제너레이터

제너레이터는 루프의 반복 동작을 제어할 수 있는 루틴 형태를 말한다. 예를 들어 숫자 1억 개를 만들어내 계산하는 프로그램을 작성한다고 하였을때 이 경우 제너레이터가 없으면 메모리 어딘가에 만들어낸 숫자 1억 개를 보관하고 있어야 한다. 그러나 제너레이터를 이용하면, 단순히 제너레이터만 생성해두고 필요할 때 언제든 숫자를 만들어낼 수 있다. 

기존의 함수는 return 구문을 맞닥뜨리면 값을 리턴하고 모든 함수의 동작을 종료한다. 그러나 yield는 제너레이터가 여기까지 실행 중이던 값을 내보낸다는 의미로, 중간값을 리턴한 다음 함수는 종료되지 않고 계속해서 맨 끝에 도달할 때까지 실행된다. 

def get_natural_number():
    n=0
    while True:
        n+=1
        yield n

이 경우 함수의 리턴 값은 다음과 같이 제너레이터가 된다.

만약 다음 값을 생성하려면 next()로 추출하면 된다. 예를 들어 100개의 값을 생성하고 싶다면 다음과 같이 100번 동안 next()를 수행하면 된다.

g=get_natural_number()
for _ in range(0,100):
	print(next(g))

range()

제너레이터의 방식을 활용하는 대표적인 함수로 range() 가 있다. 주로 for 문에서 쓰이는 range() 함수의 쓰임은 다음과 같다. 

list(range(5))

# [0,1,2,3,4]

range()는 range 클래스를 리턴하며, for 문에서 사용할 경우 내부적으로는 제너레이터의 next()를 호출하듯 매번 다음 숫자를 생성해내게 된다. 

enumerate()

enumerate()는 '열거한다'는 뜻의 함수로, 순서가 있는 자료형(list,set,tuple)을 인덱스를 포함한 enumerate 객체로 리턴한다. 

a=[1,2,3,2,45,2,5]
print(list(enumerate(a)))
# [(0, 1), (1, 2), (2, 3), (3, 2), (4, 45), (5, 2), (6, 5)]

이처럼 list()로 결과를 추루할 수 있는데, 인덱스를 자동으로 부여해주기 때문에 매우 편리하게 사용할 수 있다. 

for i,v in enumerate(a):
	print(i,v)

다른 파이썬 프로그램에서 사용할 수 있는 파이썬 코드를 모듈이라고 한다.

예를 들어 calculation.py 파일을 만들었다고 가정하자

def add(x,y):
    return x+y

def subtract(x,y):
    return x-y

def multiply(x,y):
    return x*y

def divide(x,y):
    return x/y

이 calculation.py를 사용하기 위해 아래에 함수를 호출하면 코드가 너무 길어진다. 그래서 다른 파이썬 파일에서 calculation.py를 사용할 수 있도록 할 수 있다.

run.py 파일에서 calculation.py를 사용해보도록 하겠다.

import calculation

print(calculation.add(2,5))
print(calculation.multiply(3,4))

위와 같이 import를 통해서 calculation.py의 함수들을 사용할 수 있다.

calculation이라는 이름이 너무 길다고 생각될 경우 import calculation as (원하는 이름) 을 통해 사용할 수도 있다.

import calculation as calc

print(calc.add(2,5))
print(calc.multiply(3,4))

모듈이름을 쓰고 점을 찍고 함수이름을 쓰는 방법을 배웠다. 그런데 모듈이름을 계속 쓰기가 귀찮을수도 있다. 

calculation 함수에서 add와 multiply함수만 불러올 수도 있다.

from calculation import add,multiply

print(add(2,5))
print(multiply(3,4))

불러온 함수만 쓸 수 있다. 모든 함수를 쓰려고 하면 from calculation import * 방법으로 쓰면 되는데 출처가 불분명해지기 때문에 잘 쓰지 않는다고 한다.

개발자들이 자주 쓸법한 파일들은 이미 만들어져 있다. 파이썬을 설치하면 standard library라는 것이 같이 따라온다.

1. math 모듈

# standard library (표준 라이브러리)
import math

print(math.log10(100))
print(math.cos(0))
print(math.pi)

2.random 모듈

import random

print(random.random())#0.0과 1.0 사이의 random한 값이 출력됨

randint 함수 : 두 수 사이의 어떤 랜덤한 정수를 리턴하는 함수

randint(a,b)를 하면, a<=N<=b를 만족하는 어떤 랜덤한 정수 N을 리턴한다.

uniform 함수 : 두 수 사이의 랜덤한 소수를 리턴한다.

uniform(a,b)를 하면, a<=N<=b를 만족하는 어떤 랜덤한 소수 N을 리턴한다.

3. os 모듈

import os
print(os.getlogin())#어떤 계정으로 login 되어있는지 알 수 있음
print(os.getcwd())#현재 이 파일이 있는 경로를 알 수 있음

4. datetime 모듈

datetime 모듈은 '날짜'와 '시간'을 다루기 위한 다양한 '클래스'를 갖추고 있다. 

import datetime
#datetime 값 생성
yesterday=datetime.datetime(2021,5,28)
print(yesterday)#2021-05-29 00:00:00

#오늘 날짜
today = datetime.datetime.now()
print(today)

#timedelta - 두 datetime 값 사이의 기간을 알고 싶을때
today = datetime.datetime.now()
pi_day=datetime.datetime(2020,3,14,13,6,15)
print(today-pi_day)#441 days, 7:34:40.480029
today = datetime.datetime.now()
my_timedelta = datetime.timedelta(days=5, hours=3, minutes=10, seconds=50)
print(today)
print(today + my_timedelta)

#datetime 해부하기
today = datetime.datetime.now()
print(today)
print(today.year)  # 연도
print(today.month)  # 월
print(today.day)  # 일
print(today.hour)  # 시
print(today.minute)  # 분
print(today.second)  # 초
print(today.microsecond)  # 마이크로초

#datetime 포맷팅
today = datetime.datetime.now()
print(today)
print(today.strftime("%A, %B %dth %Y"))

key - value pair (키 - 값)

my_dictionary={
    5: 25,#key:5, value:25
    2: 4,
    3:9
}
print(type(my_dictionary))#<class 'dict'>
print(my_dictionary[3])#9
my_dictionary[7]=81
print(my_dictionary[7])#81

사전에는 순서라는 개념이 없고 index는 굳이 정수가 아니더라도 된다. 이러한 점 때문에 리스트, 사전 둘 다 사용 가치가 있다.

사전활용법

my_family={
    '아빠': '김동식',
    '엄마': '이윤경',
    '아들': '김태헌',
    '딸': '김주영'
}
#value 값들이 필요할 때
print(my_family.values())#dict_values(['김동식', '이윤경', '김태헌', '김주영'])
#값이 있는지 확인
print('김태헌' in my_family.values())#True
#이 값들로 반복문을 돌고 싶을 때
for value in my_family.values():
    print(value)
#키 값을 받고 싶을 때
print(my_family.keys())#dict_keys(['아빠', '엄마', '아들', '딸'])
#key와 value 모두 같이 받아오려고 할 때
for key,value in my_family.items():
    print(key,value)

파라미터에게 '기본값(default value)'을 설정할 수 있다. 기본값을 설정해 두면, 함수를 호출할 때 꼭 파라미터에 값을 안 넘겨 줘도 된다. 이런 파라미터를 '옵셔널 파라미터(optional parameter)'라고 한다. 

def myself(name, age, nationality="한국"):
    print("내 이름은 {}".format(name))
    print("나이는 {}살".format(age))
    print("국적은 {}".format(nationality))


myself("김태헌", 24, "미국")  # 옵셔널 파라미터를 제공하는 경우
print()
myself("김태헌", 1)  # 옵셔널 파라미터를 제공하지 않는 경우

Optional Parameter는 모두 마지막에 있어야 한다. 중간에 Optional Parameter를 넣으면 오류가 난다.

불 대수 : AND, OR, NOT

NOT 연산은 그냥 반대로 뒤집어 주면 된다.

불린형 (Boolean) : True, False

무조건 따옴표 없이 써야된다. 불린형으로 불대수 계산이 가능하다.

print(True and True)#True
print(True and False)#False
print(False and True)#False
print(False and False)#False
print(True or True)#True
print(True or False)#True
print(False or True)#True
print(False or False)#False

print(2>1)#True
print(3<=3)#True

type 함수

이제까지 배운 자료형을 알아볼 수 있는 함수이다.

print(type(3))#<class 'int'>
print(type(3.0))#<class 'float'>
print(type("3"))#<class 'str'>

리스트 컴프리헨션

: 리스트 컴프리헨션(List Comprehension)이란 기존 리스트를 기반으로 새로운 리스트를 만들어내는 구문으로 파이썬의 대표적인 특징이다. 짧게 한 줄로 만들 수 있는 파이썬의 문법 이라고 생각하면 된다.

예를 들면, 다음과 같다.

#1
#[ ( 변수를 활용한 값 ) for ( 사용할 변수 이름 ) in ( 순회할 수 있는 값 )]
 a = [n*2 for n in range(1,10+1) if n%2==1]


#2
a=[]
for n in range(1,10+1):
    if n%2==1:
        a.append(n*2)

1번과 2번의 결과값은 같다. 1부터 10까지 중 홀수를 구하는 식이다. 그러나 리스트 컴프리헨션을 쓰면 2번처럼 길게 풀어서 쓸 필요가 없어지는 것이다. 리스트 뿐만 아니라 딕셔너리 등이 가능하도록 추가됐다.

//나눗셈 연산자

파이썬에서는 / 하나만 사용하면 float형태로 구하기 때문에 원하는 몫을 구할 수 없다. //를 이용해서 몫을 구하면 된다.

만약 나머지를 구하려면 %연산자를 사용하면 된다.

그리고 몫과 나머지를 모두 구하려면 divmod()함수를 사용하면 된다.

divmod(5,3)
#(1,2)

print

코딩 테스트 문제 풀이 과정에서 디버깅을 할 때 가장 자주 쓰는 명령은 print()다.

가장 쉽게 값을 출력하는 방법은 콤마(,)로 구분하는 것이다. 이 경우 한 칸 공백이 디폴트로 설정되어 있다.

print('A1','B2')
#A1 B2
#sep 파라미터로 구분자를 콤마로 지정
print('A1','B2',sep=',')
#A1,B2

print()함수는 항상 줄바꿈을 하기 때문에 긴 루프의 값을 반복적으로 출력하면 디버깅하기가 어려워서 end파라미터를 공백으로 처리하여 줄바꿈을 하지 않도록 제한하자.

print('aa',end=' ')
print('bb')
#aa bb

리스트를 출력할 때는 join()으로 묶어서 처리한다.

a = ['A','B']
print(' ',join(a))
#A B

pass

코딩을 하다 보면 일단 코드의 전체 골격을 잡아 놓고 내부에서 처리할 내용은 차근차근 생각하며 만들겠다는 의도로 다음과 같이 코딩하는 경우가 있다. 

class MyClass(Object):
 def method_a(self):
 
 def method_b(self):
  print("Method B")
  
C=MyClass()

그러나 이 클래스는 실행이 되지 않는다. 

이 문제는 method_a()가 아무런 처리를 하지 않았기 때문에 엉뚱하게 method_b()에서 오류가 발생한 것인데, 필요한 오류이긴 하나 한참 개발을 하던 중에 이런 오류에 맞닥뜨리게 되면 생각보다 처리하기가 번거롭다. pass는 이런 오류를 막는 역할을 한다. 다음과 같이 pass를 method_a()에 삽입해 간단히 처리할 수 있다.

class MyClass(Object):
 def method_a(self):
  pass
 
 def method_b(self):
  print("Method B")
  
C=MyClass()

파이썬에서 pass는 널 연산(Null Operation)으로 아무것도 하지 않는 기능이다. 이처럼 아무 역할을 하지 않는 pass를 지정하면, 오류를 방지할 수 있다.