목록2024/02/27 (4)
미소를뿌리는감자의 코딩
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1. 접근 방법 처음에는, DFS로 구현, memoization을 이용했지만, 왜인지 모르겠지만, 초반에 에러가 나서 다른 방법을 찾아보게 되었다. (아직도 이유를 모르겠다.) dp[0], 즉 첫 계단에서의 최댓값 수는, nums[0] 일 것이다. 하나의 경우의 수밖에 없기 때문이다. n 이 1 보다 크다면, dp[1] 의 최댓값은 첫 번째 계단을 밟고, 두 번째 계단을 밟는 것이 될 것입니다. 세 번째 계단..
https://leetcode.com/problems/house-robber/description/ House Robber - LeetCode Can you solve this real interview question? House Robber - You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent ho leetcode.com 1. 접근 방법 이번 문제는 memoization을 이용하는 문제이다. 처음에 memo..
https://leetcode.com/problems/climbing-stairs/description/ Climbing Stairs - LeetCode Can you solve this real interview question? Climbing Stairs - You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example 1: Input: n = 2 Outpu leetcode.com 1. 접근 방법 이 문제를 보자마자 뭔가 규칙의 냄새가 났다. 따라서 각 계단의 ..
https://leetcode.com/problems/maximum-subarray/description/ Maximum Subarray - LeetCode Can you solve this real interview question? Maximum Subarray - Given an integer array nums, find the subarray with the largest sum, and return its sum. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has t leetcode.com 1. 접근 방법 우선, nums 리스트의 앞과 뒤에서 양수가 처음 나오는 in..