오늘의 학습 키워드
</> 동적계획법
공부한 내용 본인의 언어로 정리하기
class Solution {
public int maxProfit(int[] prices) {
if(prices.length < 2){
return 0;
}
int maxProfit = 0;
//범위 제한이 따로 나와있지 않으므로 int의 최대 수로 제한
int minPrice = Integer.MAX_VALUE;
for(int price : prices){
//prices의 값을 비교해서 다음값이 이전값 보다 커야함
if(price < minPrice){
minPrice = price;
//만족하지 않으면 이익을 maxProfit으로 전달
} else if(price - minPrice > maxProfit){
maxProfit = price - minPrice;
}
}
//끝까지 비교가 종료되면 결국 최대 이익값이 maxProfit
return maxProfit;
}
}오늘의 회고
오늘 문제도 동적계획법으로 특정 주식을 매수할 날을 정하고 미래의 다른 날에 매도할 날을 정해서 최대의 이익을 구하는 것이었다.
오늘도 메모이제이션을 이용해서 전체의 값에서 진행되는 최대의 이익값과 현재 비교되는 값이 최저가격으로 설정한 값보다 작으면 현재 값을 최저 가격으로 설정해주는 식으로 풀이하였다.
그리고 당일거래는 이윤이 나지 않으므로 prices가 2개 미만일 경우 0을 반환해주는 제한사항을 추가하였다.
if(prices.length < 2){
return 0;
}그리고 최대이윤 값을 초기화하고 최저값은 비교하는 값이 참이 되기위해서 int의 최대값으로 설정해주도록 하였다.
int maxProfit = 0;
int minPrice = Integer.MAX_VALUE;이제 prices의 값을 비교하면서 최저값과 최대 이윤을 저장하면서 진행해준다.
for(int price : prices){
if(price < minPrice){
minPrice = price;
} else if(price - minPrice > maxProfit){
maxProfit = price - minPrice;
}
}이렇게 비교를 최종 순서까지 비교를 하게되면 최대이윤의 값이 maxProfit으로 설정이 된다. 그래서 그 값을 반환해준다면 해결이 된다.
return maxProfit;오늘로 코테 스터디가 마지막인데 그동안 공부하고 매일 TIL을 작성하는 습관을 들여서 이 프로그램이 고맙고 끝나서 한편으로 아쉬운 마음도 있지만 이 기세를 몰아 꾸준함의 힘으로 더 발전을 할 수 있음에 더 감사하다.
AI 코드리뷰
현재 코드의 장점
- 간결하고 이해하기 쉬운 구조입니다.
- 한 번의 반복문으로 문제를 해결하여 효율적입니다.
- 최소 가격과 최대 이익을 동시에 추적하는 방식이 효과적입니다.
현재 코드의 단점
- Integer.MAX_VALUE를 사용하는 것은 극단적인 경우 오버플로우를 일으킬 수 있습니다.
- 입력값에 대한 유효성 검사가 부족합니다 (예: 음수 가격).
시간 복잡도
- 시간 복잡도: O(n), 여기서 n은 prices 배열의 길이입니다.
- 공간 복잡도: O(1), 추가적인 공간을 사용하지 않습니다.
개선된 코드 제안
class Solution {
private static final int MIN_PRICE = 0;
private static final int MAX_PRICE = 10000; // 적절한 상한값 설정
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int maxProfit = 0;
int minPrice = MAX_PRICE; // 가능한 최대 가격으로 초기화
for (int price : prices) {
if (price < MIN_PRICE || price > MAX_PRICE) {
throw new IllegalArgumentException("Invalid price: " + price);
}
if (price < minPrice) {
minPrice = price;
} else {
maxProfit = Math.max(maxProfit, price - minPrice);
}
}
return maxProfit;
}
}개선된 코드의 장점
- 가격 범위에 대한 상수를 정의하여 코드의 가독성과 유지보수성을 향상시켰습니다.
- 입력값에 대한 유효성 검사를 추가하여 더 안전한 코드가 되었습니다.
- Math.max()를 사용하여 조건문을 간소화했습니다.
- null 체크를 추가하여 NullPointerException을 방지했습니다.
개선된 코드의 단점
- 유효성 검사로 인해 약간의 성능 저하가 있을 수 있습니다 (하지만 안정성 향상의 이점이 더 큽니다).
- 가격 범위에 대한 상수가 하드코딩되어 있어, 다른 범위를 가진 문제에 적용할 때 수정이 필요합니다.
시간 복잡도
- 시간 복잡도: 여전히 O(n)입니다. 유효성 검사가 추가되었지만, 이는 상수 시간 연산이므로 전체 시간 복잡도에 영향을 주지 않습니다.
- 공간 복잡도: O(1)로 변함없습니다.
이 개선된 버전은 원래 코드의 효율성을 유지하면서도 더 안전하고 유지보수가 쉬운 코드를 제공합니다. 실제 사용 시에는 MIN_PRICE와 MAX_PRICE 값을 문제의 구체적인 제한사항에 맞게 조정해야 합니다.
내일 공부할 것
이제 새로 낮은 단계부터 순차적으로 다시 문제를 풀어봐야겠다.
문제
