본문 바로가기

Algorithm/DP(Dynamic Programing)

 (72)
(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..
(Python) - 백준(BOJ) 10826 : 피보나치 수 4 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 대표 dp문제였습니다. 📕 풀이방법 📔 입력 및 초기화 항 n, fibonacci수열을 저장할 일차원 배열 fibo을 선언 후 n에 입력받습니다. 📔 풀이과정 점화식은 f[n] = f[n-1] + f[n-2] (n >= 2, f[0] = 0, f[1] = 1) 입니다. 두 가지 풀이가 있습니다. 1. for loop를 2이상 ~ n이하까지 수행해 각 항의 수..

티스토리툴바