둔필승총

www.acmicpc.net/problem/9095

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

[문제 풀이]

다이나믹 프로그래밍의 대표적인 문제이다. 2 x n의 타일링은 일단 가로가 관건이다. 

타일은 1x2, 2x1 밖에 없다. n길이의 가로를 채울려면 일단 n-2길이를 채우고 1x2타일을 2개 넣으면된다.

또, n-1길이를 채우고 2x1타일을 채우면 된다.

따라서 다이나믹 프로그래밍에 따라 점화식을 세워보자.

d[i]=d[i-2]+d[i-1]

그리고 초기값을 구하면 된다. d[1]일 때는 2x1밖에 안들어간다. d[1]=1

d[2]는 2x1 타일 2개 아니면 1x2 타일 2개를 쓰면 채워진다. d[2] = 2

초기값을 채우고 나서 나머지 식을 구하면 된다.

#2Xn 타일링

n = int(input())

d = [0]*1001
d[1]=1
d[2]=2
for i in range(3,n+1):
    d[i]=d[i-2]+d[i-1]

result = d[n]%10007
print(result)

 Brute-Force Attack은 우리말로 무차별 대입 공격이란 뜻이다. 이 말은 정말 무차별적으로 모든 방법을 시도하는 것을 뜻한다. Brute-Force 알고리즘도 비슷하다.

 예를 들어 자물쇠 0~99까지 가능하다면 0부터 99까지 모든 경우의 수를 시도하는 것이다. 힘들긴 하겠지만 시간만 있다면 가능한 것이다. 브루트 포스는 말 그대로 가장 순진한 알고리즘 접근법이다. 가능한 모든 조합을 찾아서 계산하면 되는 것이다.

 브루트 포스 알고리즘은 모든 경우의 수를 봐서 확실한 답을 구한다는 장점이 있지만 알고리즘 자체는 비효율적이다. 특히, input이 클수록 더 비효율적이라는 생각이 들것이다. 

 브루트 포스는 직관적이고 명확하고 답을 확실하게 찾을 수 있다는 장점이 있다. 그래서 효율적인 알고리즘의 첫 시작은 브루트 포스이기때문에 알고리즘을 배울 필요가 있는 것이다.

아래에 있는 브루트 포스 알고리즘의 예시를 보자.

[문제 설명]

카드 두 뭉치가 있습니다.

왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶은데요. 어떻게 하면 가장 큰 곱을 구할 수 있을까요?

함수 max_product는 리스트 left_cards와 리스트 right_cards를 파라미터로 받습니다.

left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨 있고, max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합니다.

def max_product(left_cards, right_cards):
	print(max_product([1, 6, 5], [4, 2, 3]))
	print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
	print(max_product([-1, -7, 3], [-4, 3, 6])) 

[풀이과정]

 브루트 포스 방법으로 for문을 2개 사용하여 풀면 된다. 처음에 max를 사용하여 left_cards 와 right_cards에서 하나씩 최대값을 뽑아서 곱했는데 그러면 음수와 음수의 곱이 최대가 될 경우를 생각못할 수 있다. 

그래서 일일이 다 구해서 최대값을 구하면 된다.

[해답]

def max_product(left_cards, right_cards):
    bigg=0
    for left_card in left_cards:
        for right_card in right_cards:
            wow = left_card*right_card
            if wow>bigg:
                bigg=wow
    return bigg
# 테스트
print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

#Tip#

3중 반복문에서 3번째 반복문을 실행 후 2번째 반복문을 다시 실행하는 과정을 재귀로 구현한 코드에서 현재 실행 중인 함수를 호출한 곳으로 돌아가는 과정으로 비유하면 백트래킹 기법을 적용했다고 한다. 백트래킹을 브루트 포스를 수행하는 방법 중 하나로 본다.

www.acmicpc.net/problem/2839

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

[풀이]

 일단 d배열의 전체를 10001로 저장해두고 d[0]=0을 해둔다. 보텀업으로 아래부터 하나하나씩 채워가기 위해서 둔것이다. 예를 들어 n을 18을 입력하였다면 18에서 5를 뺀 값은 13이다. 그럼 d[13]이 저장되어있다면 d[18]과 d[13]+1 중에서 최소값이 어떤 것인지 찾아내면 되는 것이다. 5를 뺀 d[13]이 10001이면(그러니까 5kg 3kg 두 개로 배달이 불가능한 경우일때)는 d[18]에서 3을 뺀 d[15]가 있는지 한번 살펴보는 것이다. 그럼 또 d[15]+1과 d[18]의 최소값을 찾으면 되는것이다. 예전에 '효율적인 화폐 구성' 문제에서 아이디어를 받았다. (N가지 종류의 화폐로 비용을 지불하는 문제)

n = int(input())

d = [10001]*5001
d[0]=0
for i in range(3,n+1):
    if i-5>=0 and d[i-5]!=10001:
        d[i]=min(d[i],d[i-5]+1)
    if d[i-3]!=10001:
        d[i]=min(d[i],d[i-3]+1)

if d[n]==10001:
    print(-1)
else:
    print(d[n])

www.acmicpc.net/problem/9095

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1

3 4 7 10

예제 출력 1

7 44 274

[풀이]

 먼저, 숫자가 3개 1,2,3이 있다는 사실을 안다. 4부터는 4하나로는 만들 수가 없다. 배열 d에 d[1], d[2], d[3]에 대한 값을 저장해두고 d[1], d[2], d[3]을 이용해서 나머지 4부터 10까지의 배열값을 저장할려고 했다.

4는 1에 3을 더한것, 2에 2를 더한것, 3에 1을 더한것이므로 d[4] = d[1] + d[2] + d[3] 이라고 생각할 수 있다.

5는 1에 4를 더한것, 2에 3을 더한것, 3에 2를 더한것, 4에 1을 더한것이라고 생각하면 되는데 1,2,3밖에 없으므로

d[5] = d[4] + d[3] + d[2] 까지만 하면 된다.

d[i] = d[i-1] + d[i-2] + d[i-3]이라는 점화식을 끌어오면 된다.

#1,2,3 더하기

T = int(input())
d=[0]*11
d[1]=1
d[2]=2
d[3]=4

for i in range(4,11):
    d[i]=d[i-3]+d[i-2]+d[i-1]
for i in range(T):
    n = int(input())
    print(d[n])

 컴퓨터를 이용하여 최적의 해를 구하는데 메모리 공간에는 한계가 있다. 그래서 우리는 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

 반대로, 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용하여 연산 속도를 증가시키는 방법이다. 다이나믹 프로그래밍은 탑다운과 보텀업 두가지 방식으로 나뉘다. 그리고 메모이제이션 기법까지 알아야 된다.

 피보나치 수열은 다이나믹 프로그래밍의 대표적인 예이다. 점화식으로 표현하여 푸는 것을 다이나믹 프로그래밍의 문제라고 생각하면 된다. 

def fibo(x):
	if x==1 or x==2 :
    	return 1
    return fibo(x-1)+fibo(x-2)

다음과 같이 코드를 짜면 fibo(x)에서 x에 값이 중복되면 계속 새로 계산해야된다는 단점이 있다. 그렇다면 시간복잡도가 기하급수적으로 늘어난다. 따라서 다이나믹 프로그래밍을 통해 문제를 해결한다. 다이나믹 프로그래밍을 항상 사용할 수 수는 없고 다음 조건을 만족할 때 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 다음과 같은 조건을 만족한다. 이 문제를 메모이제이션(Memoization)기법을 사용해서 해결할 수 있다.

아래는 탑다운 방식이다.

#한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화

d = [0]*100

def fibo(x):
    if x==1 or x==2:
        retun 1
    if d[x]!=0:
        return d[x]
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]

이렇게 되면 시간복잡도가 O(N)이 된다.

 이처럼 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위하여 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다. 

 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 한다. 피보나치 수열 문제를 보텀업으로도 풀어보자.

d = [0]*100
d[1]=1
d[2]=1
n=99

for i in range(3,n+1):
    d[i]=d[i-1]+d[i-2]  

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.

알고리즘은 시간과 공간에 따라 평가 된다. 공간이라고 하면 뭔가 내 방 같은 눈에 보이는 공간 느낌이라 이상할 수 있는데 공간은 컴퓨터의 메모리라고 생각하면 된다. 

둘 중 어느 것이 중요하냐고 물어보면 시간을 더 중요하게 여긴다. (알고리즘 문제를 풀더라도.. 보통 시간초과 문제에 머리를 싸멘다..)

메모리는 돈 주고 늘릴 수 있지만, 시간은 그렇지 않기 때문이다. 

 컴퓨터 사양, 프로그래밍 언어에 따라 속도에 차이가 있을 수 있으므로 단순히 프로그램이 돌아가는 시간으로 알고리즘을 평가하기는 어렵다. 그래서 시간복잡도를 이용해서 평가한다.

시간복잡도(Time Complexity)

시간복잡도의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오다.

빅오로 시간복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다.

데이터가 많아질수록 걸리는 시간이 얼마나 증가하는가에 따라 결정한다. 시간복잡도를 평가하기위해서는 수학적 개념이 들어간다. 거듭제곱과 로그이다.

내가 보통 Python으로 알고리즘을 풀면, 시간제한은 1초, 2초, (함정으로 0.5초도 가끔 보인다.) 이다. 해당 문제를 해결하려면 시간복잡도를 항상 따져야 한다. 
1초라면 1억번의 연산을 할 수 있다고 생각하고 문제를 풀면 된다. 예를 들어, n이 10000보다 작다면 n제곱까지 고려를 할 수 있다. 시간제한과 n의 값의 범위를 보고 어떤 알고리즘을 사용할지 결정하는데 도움이 된다.

점근 표기법(Big -O Notation)

빅오(O, big-O)란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.

 알고리즘 소요시간은 input 크기에 따라 표현할 수 있다. 점근 표기법이란 소요시간이 20n +40이면 40은 없애주고 앞에 붙은 20도 없애줘서 O(n)으로 그냥 표기하는 것이다. 또 2n^2+8n+157이면 O(n^2)이 되는것이다. 

 점근 표기법의 핵심은 n이 엄청 크다고 가정하는 것이다. n이 별로 크지 않으면, 안 좋은 알고리즘을 써도 상관없다. n이 엄청 큰 경우 알고리즘의 중요함을 느낀다.

O(1) 

input사이즈에 영향을 받지 않는다. input크기와 상관 없이 실행되는 코드만 O(1)이다. 최고의 알고리즘이라 할 수 있다. O(1)에 실행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.

O(logn)

로그는 매우 큰 입력값에도 크게 영향을 받지 않는편. 대표적으로 이진 검색이 이에 해당한다.

def print_powers(n) :
	i=1
    while i<n:
    	print(i)
        i=i*2

O(n)

입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간(Linear-Time) 알고리즘이라고 한다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당한다. 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.

O(nlogn) : O(n)과 O(logn)이 겹쳐진 것

병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(nlogn) 보다 빠를 수 없다. 

def print_powers_of_two_repeatedly(n):
    for i in range(n): # 반복횟수: n에 비례
        j = 1
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2

O(n^2) 

버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.

O(2^n)

피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당한다. n^2보다 2^n이 훨씬 크다.

O(n!)

각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(TSP)를 브루트 포스로 풀이할 때. 가장 느린 알고리즘이다.

공간 복잡도

O(1) 

def product(a, b, c):
    result = a * b * c
    return result

result가 차지하는 메모리 공간은 인풋과 무관하기 때문

O(n)

def get_every_other(my_list):
    every_other = my_list[::2]
    return every_other

my_list의 길이가 n이라고 하면 변수 every_other이 공간을 차지한다. every_other에는 my_list의 짝수 인덱스의 값들이 복사돼서 들어간다. 약 n/2개의 값이 들어간다. O(n)이다. 

문자열 포매팅

방법 1 %기호 -> C나 Java같은 언어들에서 이 방법으로 문자열 포매팅을 한다.

name = "김태헌"
age = 24

print("제 이름은 %s이고 %d살입니다." % (name, age))

숫자 바로 대입

character = "I'm the %d in the world" %1

문자열 바로 대입

character = "I'm the %s in the world" % "first"

숫자 값을 나타내는 변수로 대입

number = 1
character = "I'm the %d in the world" %number

문자열 포맷 코드

%s는 어떤 형태의 값이든 변환해 넣을 수 있다.

방법 2 format 메소드 ( 이 방법을 사용하자)

name = "김태헌"
age = 24

print("제 이름은 {}이고 {}살입니다.".format(name, age))

숫자 바로 대입하기

"I eat {0} apples".format(3)
#I eat 3 apples.

문자열 바로 대입하기

"I eat {0} apples".format("five")
#I eat five apples.

number = 3
"I eat {0} apples".format(number)
#I eat 3 apples

number = 5
day = "three"
"I ate {0} apples in {1} days" .format(number,day)
#I ate 5apples in 3 days

방법 3 f-string

name = "김태헌"
age = 24

print(f"제 이름은 {name}이고 {age}살입니다.")

1. 코멘트

코멘트는 앞에 #을 붙이고 쓰면 된다. 실제 실행할떄는 무시된다. 복잡한 코드 설명, 하다가 만 부분 표시, 다른 개발자들과 소통을 위해 쓰게 된다. 

#Goobdye world 출력해보자
print('Goodbye world!')

2. 변수

추상화 - 변수, 함수, 객체

변수(Variable)는 값을 저장하는 것. 

함수(Function)는 명령을 저장하는 것  ex) print() 함수

추상화의 장점은 함수가 어떤 구조인지 알지 못하더라도 사용을 할 수 있다. 

3. 자료형

자료형이란 프로그래밍을 할 때 쓰이는 숫자, 문자열 등 자료 형태로 사용하는 모든 것을 의미한다. 

프로그램의 기본이자 핵심 단위

 1) 숫자형 자료형

 정수형 : Integer이란 말 그대로 정수를 뜻하는 자료형

  a = 123

  a = -178

 실수형 Floating-point 소수점이 포함된 숫자

  a = 1.2

  a = -3.45

  a = 4.24E10 #이 방식은 "컴퓨터식 지수 표현 방식"으로 파이썬에서는 4.24e10 또는 4.24E10처럼 표현한다. 여기서 4.24E10은 4.24*10의 10제곱을 의미한다.

 8진수와 16진수

 8진수(Octal)를 만들기 위해서는 숫자가 0o 또는 0O(숫자 0 + 알파벳 소문자 o 또는 대문자 O)로 시작하면 된다.

a = 0o177

 16진수(Hexadecimal)를 만들기 위해서는 0x로 시작하면 된다.

a = 0x8ff
b = 0xABC

숫자형을 사용하기 위한 연산자

 사칙연산 : + - * / 을 수행할 수 있다.

 x의 y 제곱을 나타내는 ** 연산자

a = 3
b = 2
print(a**b) #9

 나눗셈 후 나머지를 반환하는 %연산자

a = 7
b = 3
print(a%b) #1

2) 문자열 자료형

 문자열(String)이란 문자, 단어 등으로 구성된 문자들의 집합을 의미. 따옴표로 둘러싸여 있으면 모두 문자열

문자열 안에 작은따옴표나 큰따옴표 포함시키고 싶을때

큰따옴표 안에 들어있는 작은따옴표는 문자열을 나타내기 위한 기호로 인식되지 않는다.

character = "I'm the best character in the world"

백슬래시를 사용해서 작은따옴표와 큰따옴표 문자열에 포함시키기

백슬래시를 작은따옴표나 큰따옴표 앞에 삽입하면 백슬래시 뒤의 작은따옴표나 큰따옴표는 문자열을 둘러싸는 기호의 의미가 아니라 문자 그 자체를 뜻하게 된다.

여러 줄인 문자열을 변수에 대입하고 싶을 때

줄을 바꾸기 위한 이스케이프 코드 사용하면 된다.

character = "I'm the best in the world\nAnd you can either"

이스케이프 코드 : 프로그래밍할 때 사용할 수 있ㄷ로고 미리 정의해 둔 문자 조합이다. 

문자열 곱하기

a = "python"
print(a*2) #pythonpython

문자열 길이 구하기 

len 함수를 사용하면 구할 수 있다.

문자열 인덱싱과 슬라이싱 : 인덱싱이란 무엇인가를 "가리킨다" 슬라이싱은 무엇인가를 "잘라낸다"의 의미이다.

인덱싱을 통해 문자열의 각 문자에 접근하고, 슬라이싱을 통해 문자열 안의 문자들을 잘라낼 수 있다.

  character = "I'm the best in the world\nAnd you can either"
  print(character[0]) #I
  print(character[4]) #t
  print(character[-1]) #r

character = "I'm the best in the world\nAnd you can either"
print(character[0:2]) #I'

# 0:2 의 의미는 character[0]에서 character[1]까지 출력하라는 의미이다

3)형변환(Type Conversion)

: 값을 한 자료형에서 다른 자료형으로 바꾸는 것이다. 예를 들어서 7을 7.0 (정수->소수), "7"을 7 (문자열->정수)로 바꿀 수 있다.

print(int(3.8)) # 3

int형은 소수부분이 없기 때문에 정수 부분만 출력된다.

print(int("2")+int("5")) #7