K번째 수

문제

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

예제 입력 1

5 2

4 1 2 3 5

예제 출력 1

2

<핵심>

• 시간 복잡도 : 𝑶(𝑵𝒍𝒐𝒈𝑵)

• 기본 정렬 라이브러리

• 병합 정렬, 퀵정렬, 힙정렬 등 이용하여 문제 해결

n, k = map(int, input().split())
array = list(map(int, input().split()))

array = sorted(array)

print(array[k - 1])

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

예제 입력 1 

5 5 4 3 2 1

예제 출력 1 

1 2 3 4

분석하기

시간 복잡도 : 𝑶(𝑵𝒍𝒐𝒈𝑵)

고급 정렬 알고리즘(병합, 퀵, 힙) 이용하거나

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

n = int(input())
array = []

for _ in range(n):
    array.append(int(input()))
    
array = sorted(array)

for data in array:
    print(data)

1. 퀵 정렬 (quick sort) 이란?

• 기준점(pivot 이라고 부름) 정해
  기준점보다 작은 데이터는 왼쪽(left)
  큰 데이터는 오른쪽(right) 으로 모으는 함수
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 리턴

 2. 구현

• quicksort 함수 만들기
  • 만약 리스트 갯수가 한개이면 해당 리스트 리턴
  • 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 놓기
  • left, right 리스트 변수를 만들고,
  • 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교(pivot)
    • 기준점보다 작으면 left.append(해당 데이터)
    • 기준점보다 크면 right.append(해당 데이터)
  • return quicksort(left) + pivot + quicksort(right) 로 재귀 호출

def qsort(data):
	if len(data) <= 1:
    	return data
    
    left, right = list(), list()
    pivot = data[0]
    
    for index in range(1, len(data)):
    	if pivot > data[index]:
        	left.append(data[index])
        else:
        	right.append(data[index])
    return qsort(left) + [pivot] + qsort(right)

#list comprehension 사용해서 깔끔하게

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]

    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)

import random

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

qsort(data_list)

>>>[7, 17, 19, 24, 34, 55, 60, 85, 86, 88]

 3. 분석

시간복잡도는 O(n log n)

• 단, 최악의 경우
  • 맨 처음 pivot이 가장 크거나, 가장 작으면
  • 모든 데이터를 비교하는 상황이 나옴
  • O(𝑛2n2)

1. 병합 정렬(merge sort)

-> 재귀용법을 활용한 정렬 알고리즘

• 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다

2. 알고리즘 이해

• data_list = [1,9,3,2]
  • [1,9]       [3,2]
  • [1] [9]
  • 다시 정렬해서 합침   [1, 9]
  • [3] [2]
  • 다시 정렬해서 합침   [2, 3]
  • [1, 9]    [2, 3] 합침
    • [1] 
    • [9] > [2]   =>  [1 , 2] 
    • [9] > [3]    => [1, 2, 3]
    • [1, 2, 3, 9]

3. 구현

<mergesplit 함수 만들기>

• 리스트 개수가 1개 -> 해당 값 리턴
• 아니면                      -> 리스트 앞, 뒤 2개로 나누기
• left = mergesplit(앞)
• right = mergesplit(뒤)
• merge(left, right)

def mergesplit(data):
	if len(data) <= 1:
    	return data
    m = int(len(data) / 2)
    left = mergesplit(data[:m])
    right = mergesplit(data[m:])
    return merge(left, right)

<merge 함수 만들기>

• 목표: left 와 right 의 리스트 데이터를 정렬해서 sorted_list 라는 이름으로 return 하기
• left와 right는 이미 정렬된 상태 또는 데이터가 하나임

• 리스트 변수 하나 만들기 -> sorted
• left_idx , rigth_idx = 0
• while left_idx < len(left)   or  right_idx < len(right):
  • 만약, left_idx 나 right_idx 가 이미  left 또는 right 리스트를 다 순회했다면, 
    그 반대쪽 데이터를 그대로 넣고, 해당 인덱스 1 증가
  • if left[left_idx] < right[right_idx]:
         sorted.append(left[left_idx])
         left_idx += 1
  • else:
         sorted.append(right[right_idx])
         rigth_idx += 1

def merge(left, right):
	merged = list()
    left_p , right_p = 0, 0
    
    #left/right 둘 다 존재
    while len(left) > left_p and len(right) > right_p:
    	if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    #left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    #right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

최종 코드

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    #left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    #left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    #right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged


def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

import random

data_list = random.sample(range(100), 10)
mergesplit(data_list)

>>>[13, 17, 28, 30, 36, 45, 48, 65, 70, 73]

4. 알고리즘 분석

• 따라서, 각 단계는 항상 O(n) 
• 단계는 항상 𝑙𝑜𝑔2𝑛개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제
• 따라서, 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)

문제

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

1. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
2. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
3. 벽돌들의 높이는 같을 수도 있다.
4. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
5. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

입력

첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.

출력

탑을 쌓을 때 사용된 벽돌의 수를 빈칸없이 출력하고, 두 번째 줄부터는 탑의 가장 위 벽돌부터 가장 아래 벽돌까지 차례로 한 줄에 하나씩 벽돌 번호를 빈칸없이 출력한다.

예제 입력 1

5

25 3 4

4 4 6

9 2 3

16 2 5

1 5 2

예제 출력 1

3

5

3

1

문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

예제 입력 1 복사

3 5 10

5 3 7

예제 출력 1 복사

10

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력 1

ACAYKP

CAPCAK

예제 출력 1

4

두 수열이 주어졌을 때,  두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는다

가장 긴 공통 부분 수열(LCS) : 동적 프로그래밍 문제

두 수열 길이가 N 미만 일 때, 시간복잡도O(N2)으로 문제 해결 가능

두 문자열의 길이를 조금씩 늘려가며 확인하여, 공통 부분 수열 최대 길이 계산

D[i][j] = 1. D[i-1][j-1] + 1                   //if  X[i] = Y[j]

                2. max(D[i][j-1], D[i-1][j]  //if  X[i] /= Y[j]

x = input()
y = input()

dp = [[0]*(len(y)+1) for _ in range(len(x)+1)]

for i in range(1, len(x) + 1):
    for j in range(1, len(y)+1):
        if x[i-1] == y[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(dp[len(x)][len(y)])

문제

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