exp_blog

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1

4 7

6 13

4 8

3 6

5 12

예제 출력 1

14

knapsack probelm / 동적 프로그래밍 문제

물품 수 N, 배남 담을 수 있는 무게 K

동적 프로그래밍을 이용하여 시간복잡도 O(NK)로 문제 해결할 수 있음

모든 무게에 대하여 최대 가치를 저장

D[i][j] = "배낭에 넣은 물품 무게 합이 j일때 얻을 수 있는 최대 가치"

각 물품 번호 i에 따라서 최대 가치 D[i][j] 를 갱신하여 문제 해결

D[i][j] = 1. D[i-1][j]                                                                  //if j < W[i]

                2. max(D[i-1][j], D[i-1][j-W[i]] + V[i])               //if j >= W[i]

n,k = map(int, input().split())
dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(1, n+1):
    w, v = map(int, input().split()) #w = weight / v = value
    for j in range(1, k+1):
        if j < w:
            dp[i][j] = dp[i-1][j] #작을 때는 위의 값과 동일 값 삽입
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v) #위의 값과 이전 값의 최대 가치에 이전 값을 더해 삽입
print(dp[n][k])
    

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다.(N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력 1

4

예제 출력 1

5

핵심 

• 사용할 수 있는 타일의 종류 : 2개
• 두 가지 종류의 타일을 이용, N 길이의 수열 만드는 모든 경우의 수 구함
• 동적 프로그래밍
• N이 최대 1,000,000 이므로, 시간 복잡도 O(N) 으로 해결

길이가 짧은 경우 부터 먼저 계산 하고 (특정 리스트에 저장 해놓고)-> 길어지는 것을 뒤에서 계산 하는 것이 좋음 

점화식(인정합 항들 사이의 관계식) 을 세워야 한다

D[i] = "수열의 길이가 i일 때의 경우의 수" / ex) D[3] = 3, D[4] = 5

타일을 왼쪽에서 오른쪽으로 이어 붙인다고 가정

길이가 i 인 수열을 형성하는 방법은 두가지

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

=> 피보나치 수열과 동일한 문제

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
	dp[i] = (dp[i-2] + dp[i-1]) % 15746 #큰 수 대비
print(dp[n])

1. 정의

• 동적계획법 (DP 라고 많이 부름)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
  • Memoization 기법을 사용함
    • Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
    • 예: 피보나치 수열
• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    • 예: 병합 정렬, 퀵 정렬 등

2. 공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점
  • 동적 계획법
    • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
    • Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
  • 분할 정복
    • 부분 문제는 서로 중복되지 않음
    • Memoization 기법 사용 안함

3. 동적 계획법 알고리즘

피보나치 수열: n 을 입력받아서 다음과 같이 계산됨
n 을 입력받았을 때 피보나치 수열로 결과값을 출력하세요

def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]
    
    
>>>fibo(10)
55

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

예제 입력 1 

2 3 7

예제 출력 1 

1+2-3

1+2-3+4-5-6+7

1+2-3-4+5+6-7

1-2 3+4+5+6+7

1-2 3-4 5+6 7

1-2+3+4-5+6-7

1-2-3-4-5+6+7

import copy
def recursive(array, n):
    if len(array) == n:
        operators_list.append(copy.deepcopy(array)) #깊은 복사 ; 테스트 케이스마다 다른 형식을 보여줘야 하니까
        return
    array.append(' ')
    recursive(array, n)
    array.pop()

    array.append('+')
    recursive(array, n)
    array.pop()

    array.append('-')
    recursive(array, n)
    array.pop()

test_case = int(input())

for _ in range(test_case):
    operators_list = []
    n = int(input())
    recursive([], n - 1)

    integers = [i for i in range(1, n + 1)]

    for operators in operators_list:
        string = ""
        for i in range(n - 1):
            string += str(integers[i]) + operators[i]
        string += str(integers[-1])
        if eval(string.replace(" ", "")) == 0:
            print(string)
    print()

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

Z모양을 구성하는 4가지 방향에 대하여 차례대로 재귀적으로 호출

N,r,c = map(int, input().split(' '))
count = 0

def divide(size, x, y):
    global count
    if size <=2:
        if(x==r and y ==c):
            print(count)
            return
        count+=1
        if(x==r and y+1==c):
            print(count)
            return
        count+=1
        if(x+1 == r and y==c):
            print(count)
            return
        count+=1
        if(x+1 == r and y+1==c):
            print(count)
            return
        count+=1
        return
    divide((size//2), x,y)
    divide((size//2), x, y+(size//2))
    divide((size//2), x+(size//2), y)
    divide((size//2), x+(size//2),y+(size//2))

if __name__ =="__main__":
    divide(2**N,0,0)

--이렇게 돌리면 시간 초과 에러.. ㅜㅜ 

n, x, y = map(int, input().split())

def power2(k): # 두배 만드는 함수
    return 1 << k

def go(n, x, y):
    if n == 1:
        return 2*x+y
    else:
        if x < power2(n-1): # 점점 쪼개진다.
            if y < power2(n-1):# 점점 쪼개진다.
                return go(n-1, x, y)
            else:
                return go(n-1, x, y-power2(n-1)) + power2(2*n-2)
        else:
            if y < power2(n-1):
                return go(n-1, x-power2(n-1), y) + power2(2*n-2)*2
            else:
                return go(n-1, x-power2(n-1), y-power2(n-1)) + power2(2*n-2)*3;

print(go(n,x,y))

이렇게 돌리면 시간 내에 돌아간다!

def Z(n,x,y):
    if n==1:return 0
    if r<x+n//2:
        if c<y+n//2:
            return Z(n//2,x,y) #0분면
        else:
            return Z(n//2,x,y+n//2)+n*n//4 #1분면
    else:
        if c<y+n//2:
            return Z(n//2,x+n//2,y)+n*n//4*2 #2분면
        else:
            return Z(n//2,x+n//2,y+n//2)+n*n//4*3 #3분면
n,r,c=map(int,input().split())
print(Z(2**n,0,0))

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

55

n = int(input())

a, b = 0, 1

while n > 0:
    a, b = b, a+b
    n -= 1

print(a)

1. 재귀 용법 (recursive call, 재귀 호출)

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용되므로, 익숙해져야 함

2. 예제

- 팩토리얼을 구하는 알고리즘을 Recursive Call 을 활용해서 알고리즘 작성하기

분석

• 간단한 경우부터 생각해보기
  • 2! = 1 X 2
  • 3! = 1 X 2 X 3
  • 4! = 1 X 2 X 3 X 4 = 4 X 3!
• 규칙이 보임: n! = n X (n - 1)!
  1. 함수를 하나 만든다.
  2. 함수(n) 은 n > 1 이면 return n X 함수(n - 1)
  3. 함수(n) 은 n = 1 이면 return n
• 검증 (코드로 검증하지 않고, 직접 간단한 경우부터 대입해서 검증해야 함)
  • 먼저 4! 부터
    • 함수(4) 이면, 4 > 1 이므로 4 X 함수(3)
    • 함수(3) 은 결국 2번에 의해 3 X 2 X 1 = 6
    • 4 X 함수(3) = 4 X 6 = 24 !!

코드

def factorial(n):
	if n > 1:
    	return n * factorial(n - 1)
    else:
    	return n

for n in range(10):
	print(factorial(n))

>>>
0
1
2
6
24
120
720
5040
40320
362880

시간, 공간 복잡도

• factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함

  • 일종의 n-1번 반복문을 호출한 것과 동일
  • factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨

• 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n)

3.재귀 호출 일반적인 형태 

#일반적인 형태 1
def function(입력):
	if 입력 > 입력값: #입력이 일정 값 이상이면
    	return function(입력 -1) #입력 보다 작은 값
    else:
    	return 일정값, 입력값, 또는 특정값 #재귀 호출 종료

#일반적인 형태2
def function(입력):
	if 입력 <= 일정값: #입력이 일정값보다 작으면 
    	return 일정값, 입력값 또는 특정 값 #재귀호출 종료
    function(입력보다 작은 값)
    return 결과값

def factorial(num):
	if num <= 1:
    	return num
    return num * factorial(num - 1)
 

for num in range(10):
	print(factorial(num))
>>>
0
1
2
6
24
120
720
5040
40320
362880

함수는 내부적으로 스택처럼 관리

4. 알고리즘 

1) 1부터 num 까지 곱이 출력되게 생성

>>>def multiple(num):
	if num <= 1:
    	return num
    return num * multiple(num -1)
    
>>>multiple(20)
2432902008176640000

2)  숫자가 들어있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수로 만듬 

##임의 값으로 리스트 생성하는 방법

import random

data = random.sample(range(100), 10)
data

[15, 18, 57, 89, 17, 28, 23, 73, 75, 60]

<알고리즘>

def sum(data):
	if len(data) <= 1:
    	return data[0]
    return data[0] + sum(data[1:])
    
>>>sum(data)
455

3)  회문 판별할 수 있는 함수를 재귀함수로 생성

##회문(palindrome)이란? : 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장 의미 / 리스트를 슬라이싱 활용하여 만듬

def palidrome(string):
	if len(strung) <= 1:
    	return True
    
    if string[0] == string[-1]:
    	return palindrome(string[1:-1])
    else:
    	return False

4) 정수 n 이 홀수면 3*n +1 , 짝수이면 n/2 => n이 결국 1이 될 때까지 계속 반복하여 1이 되는 모든 과정 출력

ex) 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

def func(n):
	print(n)
    if n == 1:
    	return n
    
    if n % 2 == 1:
    	return (func((3*n) +1))
    else:
    	return (func(inf(n/2)))
        
>>>func(3)
3
10
5
16
8
4
2
1

- 배열의 인덱스를 특정 데이터 값으로 여기는 정렬 방법

- 배열 크기는 데이터의 범위를 포함할 수 있도록 설정

- 데이터가 등장한 횟수를 셈

예시 데이터 

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

=> 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 

데이터를 숫자 순대로 인덱스에 넣고 , 그 인덱스 크기 자체를 비교하고 for문을 통해 반복하면 오름차순, 내림차순으로 정렬가능

# 유의사항  : 데이터 개수가 많을 때 파이썬에는 sys.stdin.readLine() 을 사용하여야 한다.