본문 바로가기

알고리즘 문제풀이/leetcode142

[leetcode 279] Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. 주어진 n을 제곱수의 합으로 표현할 때 가장 적은 숫자의 제곱수 - 풀이: dp[n]은 return값이다. bottom-up으로 update해나간다. dp[i] = i로 초기화하고 i보다 작거나 같은 제곱수를 빼서 값을 update한다. 제곱수는 dp[j*j] = 1 .. 2020. 10. 8.
[leetcode 309] Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After.. 2020. 10. 7.
[leetcode 322] Coin Change You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanati.. 2020. 10. 7.
[leetcode 338] Counting Bits 주어진 num까지 각각의 숫자를 이진수로 변환시켰을 때 1의 개수를 기록한 배열을 return Example 1: Input: 2 Output: [0,1,1] Example 2: Input: 5 Output: [0,1,1,2,1,2] ex2에서 0부터 5까지 각각을 이진수로 변환 0, 1, 10, 100 ... 그 때 1의 숫자를 세서 배열에 저장한다. 풀이 - dp - dp 치곤 쉬웠다. - 표를 적다보면 규칙이 발견된다. 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 2 1 2 2 3 1 2 2 3 2 1)2의 제곱수는 무조건 1이다. 2) 2의제곱수 사이에 있는 수는( 2 2020. 10. 7.

티스토리툴바