LIS 알고리즘 - DP(동적계획법) LIS 알고리즘 - DP(동적계획법)LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.이 문제는 기본적으로 배열에서 연속적이지 않지만, 각 숫자가yarisong.tistory.com 저번에 이어 LIS알고리즘을 이용하여 가장 갈게 증가하는 부분 수열을 찾는 알고리즘 중 이분 탐색을 이용한 방법을 알아보자 1.LIS 알고리즘-이분탐색 이분탐색의 경우 시간 복잡도는 O(nlogn)을 가진다. 이분탐색을 이용하는 경우에는 실제 LIS가 아닌 LIS의 길이를 구하는데 중점을 두는 알고리즘이다.이분탐색은 배열이 정렬되었다는 특징을 이용하여 탐색 범위를 절반씩 줄..
전체 글
LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 가장 길게 증가하는 부분 수열을 찾는 알고리즘이다.이 문제는 기본적으로 배열에서 연속적이지 않지만, 각 숫자가 이전의 숫자보다 커지는 수열을 찾는 문제이다.LIS 문제는 여러 방법으로 해결할 수 있지만, 대표적인 두 가지 방법은 동적 계획법(DP) 과 이분 탐색을 이용한 방법이다. 1. LIS 알고리즘 DP(동적계획법) 동적 계획법을 이용한 LIS 문제 해결은 O(n²) 시간 복잡도를 가진다. 다음과 같은 배열이 주어졌을 때 {50, 3, 20, 10, 2, 1} DP를 적용한 계산 과정을 살펴보자. 먼저 간단하게 알고리즘을 살펴보면 다음과 같다.LIS[i]: 인덱스 i까지의 수열에서 끝나는..
WebClient로 API를 호출할 때 아래와 같은 에러가 발생"org.springframework.core.io.buffer.DataBufferLimitException: Exceeded limit on max bytes to buffer : xxxxxx" 1. 발생원인 및 해결 방법1) 발생원인 WebClient 응답 시 기본 버퍼 사이즈인 256K를 초과하여 발생한 에러이다. 2) 해결책WebClient codec의 maxInMemorySize에 값을 설정해주면 된다.값 설정 시에는 본문 크기에 약간의 여유를 두는 것이 좋으며 만약 4MB의 응답이라면 약5~6MB정도로 설정하여 응답 처리 중에 추가적인 메모리 사용을 고려해주는 것이 좋다.WebClient webClient = WebClient...
1. 부스팅 알고리즘이란? 부스팅 알고리즘은 여러 개의 약한 학습기(weak learner)를 순차적으로 학습-예측하면서 잘못한 데이터나 학습 트리에 가중치 부여를 통해 오류를 보완하면서 학습하는 방식이다. 약한 학습기는 단독으로는 예측 성능이 그리 뛰어나지 않은 모델을 의미한다. 그러나 무작위 추정보다는 약간 더 나은 성능을 가진 학습 모델을 의미한다. 단일 모델로 사용할 경우 예측이 부정확할 수 있지만, 여러 개의 약한 학습기를 결합하여 더 강력한 예측 성능을 발휘할 수 있는 강한 학습기를 만들 수 있다. 2. 부스팅 알고리즘의 장점과 단점 부스팅 알고리즘의 장점높은 예측 성능 : 여러 약한 학습기를 결합하여 강력한 예측 모델을 만들 수 있다.유연성 : 분류, 회귀 등 다양한 머신러닝 문제에 적용 가..
1. 앙상블 학습-보팅(Voting) 보팅은 여러 개의 분류기가 투표를 통해 최종 예측 결과를 결정하는 방식으로 서로 다른 알고리즘을 가진 분류기를 결합하는 형태이다. 2. 보팅 - Soft Voting & Hard Voting Hard Voting은 다수의 Classifier 간 다수결로 최종 Class를 결정한다.아래 그림에서 Classifer1~4가 있다고 가정한다. Classifier1, 3, 4는 클래스 값 ①로 예측을 하고 Classifier2는 클래스 값 ②로 예측을 하게 되면 다수결로 최종 클래스값 ①로 예측하게 된다. Soft Voting은 다수의 classifier들의 class 확률을 평균하여 결정한다.아래 그림에서 Classifer1~4가 있다고 가정한다. 각각의 Classif..
1. 앙상블 학습 앙상블 학습을 통한 분류는 여러 개의 분류기(Classifier)를 생성하고 그 예측을 결합함으로써 보다 정확한 최종 예측을 도출하는 기법이다.앙상블 학습의 목표는 다양한 분류기의 예측 결과를 결합함으로써 단일 분류기보다 신뢰성이 높은 예측값을 얻는 것이다. 앙상블의 특징을 살펴보면 아래와 같다.단일 모델의 약점을 다수의 모델들을 결합하여 보완뛰어난 성능을 갖진 모델들로만 구성하는 것보다 성능이 떨어지더라도 서로 다른 유형의 모델을 섞는 것이 오히려 전체 성능에 도움이 될 수 있다.랜덤 포레스트 및 뛰어난 부스팅 알고리즘들은 모두 결정 트리 알고리즘을 기반 알고리즘으로 적용함결정 트리의 단점인 과적합(오버피팅)을 수십~수천개의 많은 분류기를 결합해 보완하고 장점인 직관적인 분류 기준은..