exp_blog

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

문제

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

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

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