본문 바로가기

Algorithm/DP(Dynamic Programing)

 (68)
(Python3) - LeetCode (Hard) : 1639. Number of Ways to Form a Target String Given a Dictionary https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionarytop down dp로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화MOD, 한 단어의 길이 word_len, target의 길이 target_len, 각 단어의 열별 알파뱃의 빈도수를 저장할 해시맵인 freq_map, j번째 타겟의 문자를 만들기 위해 k번째 열의 word를 선택할 경우 만들 수 있는 문자들의 경우의 수를 의미하는 total_ways를 선언 후 적절히 초기화합니다.📔 풀이과정words의 길이가 모두 같기 때문에 단어들을 선택할 때 열별로 선택여부를 결정할 수 있습니다. words = ["abba", "baab", "abc..
(Python3) - LeetCode (Medium) : 3152. Special Array II https://leetcode.com/problems/special-array-ii부분합으로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 어떤 그룹에 속해있는지 저장하기 위해 prefix_sum을 선언 후 nums의 길이만큼 초기화해줍니다.  같은 홀짝 쌍 누적 기록:prefix_sum 배열을 초기화하고, nums의 인접한 원소를 비교하여 홀짝이 같은 경우를 누적합니다.예: nums = [3, 4, 1, 2, 6]이라면 prefix_sum = [0, 0, 0, 0, 1]→ 인덱스 4에서 2와 6이 같은 홀짝이므로 prefix_sum[4] = 1 2. 정답을 저장할 빈 배열 answer를 초기화합니다.  📔 풀이과정 1. 각 쿼리에 대해, query[0]부터 query[1] 구간에서 같은 홀..
(Python3) - 백준(BOJ) 21758 : 꿀 따기 https://www.acmicpc.net/problem/21758누적합 문제였습니다.📕 풀이방법📔 입력 및 초기화전체 칸 수 n과 각 칸의 꿀 양 honey를 선언 후 입력받습니다.📔 풀이과정왼쪽부터 i까지 꿀을 채취했을 때 누적량을 계산해서 최댓값을 반환하는 함수 max_honey를 구현해줍니다.n이 10만이므로 단순 brute force로 두 마리의 벌과 벌통을 삼차원 for loop로 계산하면 시간초과입니다. 따라서 O(n)또는 O(nlogn)의 시간복잡도를 가진 알고리즘으로 해결해야 함을 알 수 있습니다. 벌통과 꿀벌의 배치를 보시면 3가지 경우가 있음을 알 수 있습니다.1. 가장 왼쪽에 벌통이 있는경우마지막 위치에 꿀벌 한 마리가 있는 것이 가장 많은 꿀을 채취할 수 있습니다. 2. 가..
(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 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 생성자에 ..

티스토리툴바