목록알고리즘 (1)
코딩.zip
[SW Expert - 1859번] 백만 장자 프로젝트
미래를 보는 능력을 가진 사람이 다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주기 1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다. 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다. 3. 판매는 얼마든지 할 수 있다.ex. 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있음📚 풀이법문제 : 최대 이익 구하기주의사항 : 배열의 길이가 최대 1,000,000 이기에 시간 복잡도 중요 -> O(N) 풀이방법 : 미래를 알고 있다는 전제가 있으므로 뒤에서부터 순회하며 현재 가격과 미래 가격의 최댓값을 비교최대 가격 > 현재 가격 이라면 '최대가격-현재가격' 결..
알고리즘
2025. 1. 11. 16:30