Coding Test/Greedy (3) 썸네일형 리스트형 [Leetcode] 53번 - Maximum Subarray 1. 문제 파악문제 링크: https://leetcode.com/problems/maximum-subarray/description/문제 정의: 배열 요소의 총합이 제일큰 subarray의 총합을 구해라.시간복잡도: 입력크기가 10^5 이기 때문에 시간복잡도는 O(nlogn)이햐여야한다.2. 문제 풀이1. 문제 접근 과정처음에 subarray에서 최대값을 구하는 문제라 슬라이딩 윈도우로 접근했다.하지만 슬라이딩 윈도우로 풀리지 않았다.문제의 핵심은 '배열을 순회하면서 총합이 양수이기만해도 최대값의 크기는 커진다'라는 것을 발견했다.그다음 그리디 문제처럼 최적의 해를 찾아서 푸는 알고리즘을 도출하였다.2. 핵심 문제 풀이문제의 핵심은 '배열을 순회하면서 총합이 양수이기만해도 최대값의 크기는 커진다' 라는 .. [Leetcode] 406번 - 키에 따른 대기열 재구성 1. 문제 파악문제 링크: https://leetcode.com/problems/queue-reconstruction-by-height/description/문제 정의: 자기 보다 키큰 사람의 수(k)에 맞춰서 큐에 저장해라.입력크기: 1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?이 문제는 '내 앞에 나보다 키가 크거나 같은 사람이 k명 있어야 한다' 라는 점이다. 따라서 핵심은 키 큰 사람부터 위치를 확정하면 나중에 작은 사람을 끼워 넣어도 조건이 깨지지 않는다는 점이다. 큰 키부터 배치해놓으면, 이후에 들어오는 사람은 그보다 작거나 같은 키이므로, 앞에 큰 사람의 수는 변하지 않는다. 따라서 먼저 키(h) 큰 사람 순으로 배치해놓는다. .. [Leetcode] 122번 - 주식을 사고팔기 가장 좋은 시점 II 1. 문제 파악문제 링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/문제 정의: 최대 한 주까지만 보유하면서 매일 주식을 매수 또는 매도를 반복해서 최대 이익을 낼수있는 값을 찾아라1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?그리디 알고리즘은 '순간의 최적 선택을 반복하여 전체 최적을 찾는 방법'이다.순회중 산 값을 지정하고 보다 작은 값 있으면 업데이트한다.산값 보다 큰값이 있으면 팔고 판값을 이익에 누적한다. 그리고 판값을 산값으로 업데이트한다.input: 3 1 4 2 3 6output: 3 + 1 + 3 = 7input: 7 1 5 3 6.. 이전 1 다음