Skip to content

Instantly share code, notes, and snippets.

View dongwooklee96's full-sized avatar
🐘
Focusing

Lee Dong Wook dongwooklee96

🐘
Focusing
View GitHub Profile
@dongwooklee96
dongwooklee96 / main.py
Created August 24, 2021 07:26
정렬
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]:
"""
문제 : 최장 공통 부누 수열 (Longest Common Subsequence)
- 두 문자열 (str1, str2)가 주어졌을 때 해당 두 문자열의 최장 공통 수열의 길이를 반환하라.
- 이 문제에서 언급하는 부분 수열은 연속적이지 않으나 순서대로 나열 될 수 있는 문자열을 말한다.
- 예를 들어서 'abcde' 라는 문자열에서 부분 수열을 'abc', 'ace', 'aed' 등 각 문자의 순서를 지킨 모든 부분 문자열을 말한다.
### 아이디어 (Brute-Force)
1 str1의 인덱스 i, str2의 인덱스 j를 0으로 초기화 한다.
@dongwooklee96
dongwooklee96 / main.py
Created August 20, 2021 18:20
동전교환
"""
# 문제 : 동전 교환
각기 다른 액면을 가진 동전 배열과 거슬러주어야 하는 총 금액을 입력으로 받으면 잔도의 조합으로 거스름돈을 맞춰주기 위한 최소한의
동전 개수를 반환하자.
예를 들어서 [1, 5, 10, 25] 액면의 동전이 있다고 할 때, 거스름돈이 1이라면 액면 1인 동전 하나만 있으면 된다.
### 아이디어 (Brute-Force)
@dongwooklee96
dongwooklee96 / main.py
Last active August 12, 2021 12:45
7.2.1, 7.2.2
"""
# 문제 7.2: 동일 합으로 배열 분할 문제
양의 정수로 구성된 배열이 주어지면, 해당 배열을 두 부분으로 분할하여 동일한 합의 값을 가지는지 확인해보라.
예를 들어서, [1, 2, 3, 4]가 있고 [1, 4], [2, 3]으로 분할하면 각 분할된 배열 요소의 합이 5로 동일하다.
### 아이디어 (Brute-Force)
1. 배열의 전체 합을 2로 나눈다.
2. 전체 합이 2로 나눈 나머지가 0이 아니라면 바로 거짓(False)을 반환
"""
# 문제 : 배낭 문제
items = {물, 통조림, 라디오, 구급약}
values = {7, 5, 3, 4}
weights = {2, 1, 3, 4}
배낭에는 무게 5만큼을 넣을 수 있고, 더 이상은 넣을 수 없다.
다양한 조합이 가능한데, 그중에서 가장 가치가 높은 조합을 구하라.
"""
"""
# 문제 : 이진 트리 검증
주어진 이진 검색 트리가 이진 트리의 조건을 만족하는지 아닌지를 확인하라.
- 이진 트리는 부모 노드를 기준으로 왼쪽 노드는 부모 노드보다 작은 값이 보장되고
- 오른쪽 노드는 해당 노드보다 항상 큰 값이라는 보장이 된다.
### 아이디어 (재귀)
"""
# 문제 : 이진 트리 반전
트리의 루트를 기준으로 좌우 노드를 바꾸는 코드를 작성하라.
### 아이디어 (반복 - 스택)
1. 스택 생성
2. 루트 노드를 스택에 추가
3. 스택이 비어있을 때 까지
"""
# 문제 : 3번째 큰 수
- 배열에서 3번재로 큰 수를 찾아서 반환하도록 하자.
- 만약 3번째로 큰 수가 없다면 가장 큰 수를 반환하면 된다. 예를 들어서 배열에 [1, 2, 3] 이 있다면 1을 반환하고
3번째가 없는 배열 [2, 3] 이라면 3을 반환하면 된다.
### 아이디어 (정렬)
1. 배열을 역순으로 정렬한다.
@dongwooklee96
dongwooklee96 / main.py
Created August 3, 2021 14:44
set vs dict
import time
import random
import pytest
nums = list(random.randint(1, 100) for _ in range(100))
@pytest.mark.benchmark(
min_rounds=10000000,
"""
# 문제 : 3번째 큰 수
- 배열에서 3번재로 큰 수를 찾아서 반환하도록 하자.
- 만약 3번째로 큰 수가 없다면 가장 큰 수를 반환하면 된다. 예를 들어서 배열에 [1, 2, 3] 이 있다면 1을 반환하고
3번째가 없는 배열 [2, 3] 이라면 3을 반환하면 된다.
### 아이디어 (정렬)
1. 배열을 역순으로 정렬한다.