백준 9012 괄호 (파이썬)

항상 최적의 해를 구하는 동적 계획법과는 다르게 그리디 알고리즘은 현재 단계에서 선택할 수 있는 최적의 선택만을 하여 답을 구성해나가는 방식이다. 그러나 이 방식은 결론적으로 최적의 해를 구한다고 단정지을 수 는 없다.
그리디 알고리즘과 동적 계획법은 상호보완적인데 그리디 알고리즘은 빠른 계산 속도 을 가지고 동적 계획법은 최적의 해 를 구한다는 점에서 장점이 있다.
그리디는 아래 두 가지 조건이 성립되어야 잘 작동할 수 있다.
- 탐욕스러운 선택 조건 (Greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는 조건
- 최적 부분 구조 조건(Optimal Substructure) : 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이다는 조건
그리디 알고리즘이 적용되는 대표적인 예시가 몇 가지 있다. 참고 사이트 두번째 링크에서 확인해볼 수 있다.
1. 활동 선택 문제 (The Activity-Selection Problem)
2. 분할가능 냅색 문제 (The Fractional Knapsack problem)

동적계획법 (Dynamic Programming)

22 Mar 2021 in Dev on Algorithm

동적계획법이란 (Dynamic Programming)

동적계획법이란 전체 문제를 subproblmes로 단순화하고 재귀적 구조를 활용하여 병합해나가며 전체 문제를 해결하는 방법이다.
분할정복 알고리즘(Divide & Conquer)은 subproblems가 여러번 계산되지만 동적계획법은 딱 한번만 계산하고 그 답을 배열에 저장해두기에(Memoization) 매번 다시 계산하는 불필요한 작업을 피한다.
중복 계산을 줄이기에 시간복잡도가 분할정복 알고리즘보다는 적다.

최적해를 구할 수 있도록 전체 문제를 작은 문제로 단순화한다
최적해를 구할 수 있는 재귀적 구조를 찾는다
일반적으로 Bottom-up방법으로 최적해를 계산한다 (작은 문제 해결방법으로 전체 문제 해결)

[Learning Evaluations - Interval Target] (Root Average Squared Error, Relative Error)

16 Mar 2021 in Dev on Machine Learning

Supervised model(target variable이 있는 모델)이 좋은 모델인지 아닌지 판단하는 방법에는 여러가지가 있다.
앞으로 소개할 learning evaluations은 어떤 모델을 사용하는 것이 좋을지 판단해주는 지표들이다.
다양한 지표들이 있기에 타겟의 유형별(Interval, Binary, Nominal)로 나누어 글을 써보려고 하는데 이 글은 Interval 타겟 의 learning evalutations이다.

자세한 설명에 앞서 짤막한 요약은 아래 표와 같다.

Interval	Binary	Nominal
RASE Relative Error	AUC RASE Misclassification Rate F1 Score Receiver Operating Characteristic Curve Lift Curve Kolmogorov-Smirnov Curve Precision-Recall Curve	AUC RASE Misclassification Rate