본문 바로가기

Algorithm/DP(Dynamic Programing)

(64)
(C++) - LeetCode (easy) 746. Min Cost Climbing Stairs https://leetcode.com/problems/min-cost-climbing-stairs/description/ Min Cost Climbing Stairs - LeetCode Can you solve this real interview question? Min Cost Climbing Stairs - You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the ste leetcode.com dp 문제였습니다. 📕 풀이방법 📔 풀이과정..
(C++) - LeetCode (easy) 724. Find Pivot Index https://leetcode.com/problems/find-pivot-index/description/ Find Pivot Index - LeetCode Can you solve this real interview question? Find Pivot Index - Given an array of integers nums, calculate the pivot index of this array. The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of leetcode.com 누적합을 이용하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 누적합을 ..
(C++) - LeetCode (easy) 509. Fibonacci Number https://leetcode.com/problems/fibonacci-number/description/ Fibonacci Number - LeetCode Can you solve this real interview question? Fibonacci Number - The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0 leetcode.com top down dp로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초..
(C++) - LeetCode (easy) 303. Range Sum Query - Immutable https://leetcode.com/problems/range-sum-query-immutable/description/ Range Sum Query - Immutable - LeetCode Range Sum Query - Immutable - Given an integer array nums, handle multiple queries of the following type: 1. Calculate the sum of the elements of nums between indices left and right inclusive where left sumRange(left,right); */ *더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.
(C++) - LeetCode (easy) 1137. N-th Tribonacci Number https://leetcode.com/problems/n-th-tribonacci-number/description/ N-th Tribonacci Number - LeetCode N-th Tribonacci Number - The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given n, return the value of Tn. Example 1: Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 leetcode.com dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 생성자에 ..
(C++) - LeetCode (easy) 263. Ugly Number https://leetcode.com/problems/ugly-number/description/ Ugly Number - LeetCode Ugly Number - An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return true if n is an ugly number. Example 1: Input: n = 6 Output: true Explanation: 6 = 2 × 3 Example 2: Input: n = 1 Output: true leetcode.com dp방식으로 해결했습니다. 📕 풀이방법 📔 풀이과정 ugly number를 만들기 위해 1부터 시작..
(C++) - LeetCode (easy) 70. Climbing Stairs https://leetcode.com/problems/climbing-stairs/ Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. vector v를 선언해 크기를 46개로 정하고 0으로 초기화해줍니다. 2. 계단 1번째에 오르기 위한 경우의 수는 1, 2번째는 2입니다. 이에 맞게 값을 할당해줍니다. 📔 풀이과정 계단 i번째에 오르기 위한 경우의 수는 i-1번째에 오르기 위..
(C++) - 백준(BOJ) 20438 : 출석체크 https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 누적합 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 학생 수 n, 조는 인원 k, 출석코드를 받은 학생 수 q, 구간 개수 m, 구간 s와 e, 정답을 출력할 ans, 학생 vector, map sleep, attend를 선언후 입력받습니다. 📔 풀이과정 * 5000의 학생 수에 대해 50000개의 구간이 들어온다면 brute force로 탐색 시 2..