dongwooklee96

from random import randint

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        done_sort = True

        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:

dongwooklee96

"""
문제 : 최장 공통 부누 수열 (Longest Common Subsequence)

- 두 문자열 (str1, str2)가 주어졌을 때 해당 두 문자열의 최장 공통 수열의 길이를 반환하라.
- 이 문제에서 언급하는 부분 수열은 연속적이지 않으나 순서대로 나열 될 수 있는 문자열을 말한다.
- 예를 들어서 'abcde' 라는 문자열에서 부분 수열을 'abc', 'ace', 'aed' 등 각 문자의 순서를 지킨 모든 부분 문자열을 말한다.

### 아이디어 (Brute-Force)

1 str1의 인덱스 i, str2의 인덱스 j를 0으로 초기화 한다.

dongwooklee96

"""
# 문제 : 동전 교환

각기 다른 액면을 가진 동전 배열과 거슬러주어야 하는 총 금액을 입력으로 받으면 잔도의 조합으로 거스름돈을 맞춰주기 위한 최소한의
동전 개수를 반환하자.

예를 들어서 [1, 5, 10, 25] 액면의 동전이 있다고 할 때, 거스름돈이 1이라면 액면 1인 동전 하나만 있으면 된다.

### 아이디어 (Brute-Force)

dongwooklee96

"""
# 문제 7.2: 동일 합으로 배열 분할 문제

양의 정수로 구성된 배열이 주어지면, 해당 배열을 두 부분으로 분할하여 동일한 합의 값을 가지는지 확인해보라.
예를 들어서, [1, 2, 3, 4]가 있고 [1, 4], [2, 3]으로 분할하면 각 분할된 배열 요소의 합이 5로 동일하다.

### 아이디어 (Brute-Force)

1. 배열의 전체 합을 2로 나눈다.
2. 전체 합이 2로 나눈 나머지가 0이 아니라면 바로 거짓(False)을 반환

dongwooklee96

"""
# 문제 : 배낭 문제

items = {물, 통조림, 라디오, 구급약}
values = {7, 5, 3, 4}
weights = {2, 1, 3, 4}

배낭에는 무게 5만큼을 넣을 수 있고, 더 이상은 넣을 수 없다.
다양한 조합이 가능한데, 그중에서 가장 가치가 높은 조합을 구하라.
"""

dongwooklee96

"""
# 문제 : 이진 트리 검증

주어진 이진 검색 트리가 이진 트리의 조건을 만족하는지 아닌지를 확인하라.

- 이진 트리는 부모 노드를 기준으로 왼쪽 노드는 부모 노드보다 작은 값이 보장되고
- 오른쪽 노드는 해당 노드보다 항상 큰 값이라는 보장이 된다.

### 아이디어 (재귀)

dongwooklee96

"""
# 문제 : 이진 트리 반전

트리의 루트를 기준으로 좌우 노드를 바꾸는 코드를 작성하라.

### 아이디어 (반복 - 스택)

1. 스택 생성
2. 루트 노드를 스택에 추가
3. 스택이 비어있을 때 까지

dongwooklee96

"""
# 문제 : 3번째 큰 수

- 배열에서 3번재로 큰 수를 찾아서 반환하도록 하자.
- 만약 3번째로 큰 수가 없다면 가장 큰 수를 반환하면 된다. 예를 들어서 배열에 [1, 2, 3] 이 있다면 1을 반환하고
3번째가 없는 배열 [2, 3] 이라면 3을 반환하면 된다.

### 아이디어 (정렬)

1. 배열을 역순으로 정렬한다.

dongwooklee96

import time
import random

import pytest

nums = list(random.randint(1, 100) for _ in range(100))


@pytest.mark.benchmark(
    min_rounds=10000000,

dongwooklee96

"""
# 문제 : 3번째 큰 수

- 배열에서 3번재로 큰 수를 찾아서 반환하도록 하자.
- 만약 3번째로 큰 수가 없다면 가장 큰 수를 반환하면 된다. 예를 들어서 배열에 [1, 2, 3] 이 있다면 1을 반환하고
3번째가 없는 배열 [2, 3] 이라면 3을 반환하면 된다.

### 아이디어 (정렬)

1. 배열을 역순으로 정렬한다.