exp_blog

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() 을 사용하여야 한다.

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

10 5 2 3 1 4 2 3 5 1 7

예제 출력 1 복사

1 1 2 2 3 3 4 5 5 7

import sys

n = int(sys.stdin.readline())
array = [0] * 10001

for i in range(n):
	data = int(sys.stdin.readline())
    array[data] += 1

for i in range(10001):
	if array[i] != 0:
    	for j in range(array[i]):
        	print(i)

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력 1

3

21 Junkyu

21 Dohyun

20 Sunyoung

예제 출력 1

20 Sunyoung

21 Junkyu

21 Dohyun

## (나이, 이름)의 정보를 입력 받은 뒤 나이를 기준으로 정렬

파이썬 기본 정렬 라이브러리 이용

나이가 동일 시 , 먼저 입력된 이름 순서 따르도록 key 속성 설정(key 를 람다 함수로 설정)

n = int(input())
array = []
for _ in range(n):
	data = input().split(' ')
	array.append((int(data[0]), data[1]))

array = sorted(array, key=lambda x: x[0])

for i in array:
	print(i[0], i[1])