exp_blog

문제

수열 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))

문제

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

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

준서가 여행에 필요하다고 생각하는 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부터 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)

문제

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