문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 

6

10 20 10 30 20 50

예제 출력 1 

4

D[i] = array[i] 를 마지막 원소로 가지는 부분 수열 최대 길이

모든 0 <= j < i 에 대하여 , D[i] = max(D[i], D[j] + 1)  //if array[j] < array[i]

시간 복잡도 : O(N2)

n = int(input())
arr = list(map(int, input().split()))
dp = [1]*n

for i in range(1, n):
    for j in range(0, i):
        if arr[j]<arr[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

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()

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

lambda : 쓰고 버리는 일시적인 함수 / 함수가 생성된 곳에서만 필요

즉, 간단한 기능을 일반적인 함수와 같이 정의해두고 쓰는 것이 아니고, 즉시 사용하고 버릴 수 있다.

람다 함수 사용법

>>> def inc(n):

	return lambda x: x + n



>>> f = inc(2)

>>> g = inc(4)

>>> print(f(12))

14

>>> print(g(12))

16

>>> print(inc(2)(12))

14

1. map() : 두개의 인수를 가지는 함수 

r = map(function, iterable ...)

- function : 함수 이름

- iterable : 한번에 하나의 멤버를 반환할 수 있는 객체

- map은 리스트의 요소를 각각 처리하므로 lambda의 반환값도 요소여야 한다

>>> a = [1,2,3,4]

>>> b = [17,12,11,10]

>>> list(map(lambda x, y:x+y, a,b))

[18, 14, 14, 14]

2. filter() 함수

 r = filter(function, iterable)

- filter에 인자로 사용되는 function 은 처리되는 각 요소에 대해 boolean 값을 반환

- true 반환 : 그 요소만 남고

- false : 그 요소 제거

>>> sort = [2, 18, 9, 22, 17, 24, 8, 12, 27]

>>> list( filter(lambda x: x % 3 == 0, sort) )

[18, 9, 24, 12, 27]

3. reduce() 함수

functools.reduce(function, iterable[, initializer])

- 두 개의 필수 인자 + 하나의 옵션 인자

- function 을 사용해서 itreralble 하나의 값으로 줄인다. 

- initializer 사용 시 첫 번째 인자로 추가된다

>>> from functools import reduce

>>> reduce(lambda x,y: x+y, [1,2,3,4,5])

15

좌표 정렬하기

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

알고리즘

N = int(input())
dot = []

for _ in range(N):
    x, y = map(int, input().split(" "))
    dot.append((x,y))
    
dot_sort = sorted(dot, key=lambda x : (x[0], x[1]))

for x,y in dot_sort:
    print(x,y)

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

예제 입력 1 복사

2143

예제 출력 1 복사

4321

알고리즘

메모리 29285KB

시간      64ms

코드길이 115B

array = input()
for i in range(9, -1, -1):
    for j in array:
        if int(j) == i:
            print(i, end='')

437239
974332