계단 오르기 문제
문제 설명
당신은 계단을 오르고 있습니다. 꼭대기에 도달하려면 n 계단이 필요합니다.
한 번에 1계단 또는 2계단을 오를 수 있습니다. 그렇다면 꼭대기까지 오르는 서로 다른 방법의 수는 몇 가지일까요?
예시 1
입력: n = 2
출력: 2
설명: 꼭대기까지 오르는 방법은 두 가지입니다.
1.
1계단 + 1계단
2.
2계단
예시 2
입력: n = 3
출력: 3
설명: 꼭대기까지 오르는 방법은 세 가지입니다.
1.
1계단 + 1계단 + 1계단
2.
1계단 + 2계단
3.
2계단 + 1계단
제약 조건
•
1 <= n <= 45
주식 사고팔기 최적 시점 (Best Time to Buy and Sell Stock)
문제 설명
당신에게 prices 라는 배열이 주어집니다.
여기서 prices[i]는 i번째 날의 주식 가격을 나타냅니다.
당신은 한 번만 주식을 사고, 이후의 어떤 날에 그 주식을 팔아 이익을 최대화하려고 합니다.
가능한 거래로 얻을 수 있는 최대 이익을 반환하세요.
만약 어떤 방법으로도 이익을 얻을 수 없다면 0을 반환하세요.
예시 1
입력: prices = [7,1,5,3,6,4]
출력: 5
설명:
•
2번째 날(가격 = 1)에 매수하고,
•
5번째 날(가격 = 6)에 매도하면,
•
이익은 6 - 1 = 5입니다.
주의: 2번째 날에 사고 1번째 날에 파는 것은 불가능합니다. (항상 "사고 → 판다" 순서여야 함)
예시 2
입력: prices = [7,6,4,3,1]
출력: 0
설명:
이 경우, 어떤 거래도 이익을 만들 수 없으므로 최대 이익은 0입니다.
제약 조건
•
1 <= prices.length <= 10^5
•
0 <= prices[i] <= 10^4
최대 부분 배열 (Maximum Subarray)
문제 설명
정수 배열 nums가 주어집니다.
이 배열에서 연속된 부분 배열(subarray) 중 합이 가장 큰 것을 찾아, 그 합을 반환하세요.
예시 1
입력: nums = [-2,1,-3,4,-1,2,1,-5,4]
출력: 6
설명: 부분 배열 [4,-1,2,1]의 합이 6으로, 가장 큽니다.
예시 2
입력: nums = [1]
출력: 1
설명: 부분 배열 [1]의 합이 1로, 가장 큽니다.
예시 3
입력: nums = [5,4,-1,7,8]
출력: 23
설명: 부분 배열 [5,4,-1,7,8]의 합이 23으로, 가장 큽니다.
제약 조건
•
1 <= nums.length <= 10^5
•
10^4 <= nums[i] <= 10^4
추가 문제 (Follow up)
만약 O(n) 시간 복잡도의 해법을 알아냈다면,
분할 정복(Divide and Conquer) 접근법을 사용해 코드를 작성해보세요. 이 방법은 조금 더 미묘한 방식입니다.
집털이 (House Robber)
문제 설명
당신은 전문 도둑으로, 한 거리에 있는 집들을 털 계획을 세우고 있습니다.
각 집에는 일정 금액의 돈이 숨겨져 있습니다.
단, 제약 조건이 있습니다:
서로 인접한 두 집에는 보안 시스템이 연결되어 있어, 같은 날 밤 두 집을 동시에 털면 자동으로 경찰에 신고됩니다.
정수 배열 nums가 주어지며, nums[i]는 i번째 집에 있는 돈의 금액을 의미합니다.
경찰을 부르지 않고 오늘 밤에 털 수 있는 돈의 최대 금액을 반환하세요.
예시 1
입력: nums = [1,2,3,1]
출력: 4
설명:
•
1번 집(돈 = 1)을 털고,
•
3번 집(돈 = 3)을 털면,
총 금액 = 1 + 3 = 4
예시 2
입력: nums = [2,7,9,3,1]
출력: 12
설명:
•
1번 집(돈 = 2),
•
3번 집(돈 = 9),
•
5번 집(돈 = 1)을 털면,
총 금액 = 2 + 9 + 1 = 12
제약 조건
•
1 <= nums.length <= 100
•
0 <= nums[i] <= 400