[알고리즘] LIS - 최장 증가 부분 수열(dp,이진탐색,수열 복원)
LIS (최장 증가 부분 수열: Longest Increasing Subsequence)LIS란 최장 증가 부분 수열로 어떤 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 의미한다.여기서 부분 수열이란 원소의 순서를 유지한 채, 일부 원소를 골라 만든 수열이다.수열: [10, 20, 10, 30, 20, 50]LIS: [10, 20, 30, 50] → 길이 4구현 방법일반적으로 DP와 이진 탐색을 이용해서 구현할 수 있다.DP: O(n²)이진 탐색: O(n log n)DP로 구현하기int[] dp = new int[n];Arrays.fill(dp, 1); // 최소 길이 1for (int i = 0; i i 번째 까지 반복하면서 이전 인덱스 j 들을 확인한다.arr[i]가 arr..
2025. 4. 21.
[Spring Cloud] MSA 서버 간 호출방식 비교 (RestTemplate, FeignClient, WebClient, RestClient)
MSA 프로젝트를 진행하면서, 서비스 간 통신이 필요한 상황이 발생했다. 이를 해결하기 위해 HTTP 클라이언트를 찾아본 결과 RestTemplate, FeignClient, WebClient, RestClient 네 가지 방식이 존재했다. 각 방식의 특징과 장단점을 비교한 후, 우리의 요구사항에 가장 적합한 방법을 선택했다.우리의 경우 MSA에서 서비스 간 호출이 목적이므로, FeignClient를 사용하기로 결정했다. RestTemplate (Spring 5 이전 사용)개발이 중단되었으며, RestClient 사용을 권장한다.RestTemplate은 Spring 5 이전까지 사용되던 동기식 HTTP 클라이언트로,Spring Boot 3.2 이상에서는 RestClient 사용이 권장된다.특징동기 방식(..
2025. 2. 8.
