본문 바로가기

Algorithm/DP(Dynamic Programing)

 (72)
(Python3) - LeetCode (Medium) : 2017. Grid Game https://leetcode.com/problems/grid-game누적합을 이용한 문제였습니다.📕 풀이방법📔 입력 및 초기화열 개수 colLength, 첫 번째와 두 번째 행의 누적합을 구할 prefix_row0, prefix_row1, 정답 변수 result를 선언 후 적절히 초기화합니다.📔 풀이과정📑 robot1의 역할:robot1은 게임에서 최대한 많은 점수를 가져가는 것이 목표입니다.하지만 단순히 점수를 많이 가져가는 것만이 아니라, robot2가 가져갈 점수를 최소화해야 합니다.따라서 robot1은 경로를 선택할 때 robot2가 가져갈 수 있는 점수의 최댓값을 최소화하는 방식으로 움직입니다.📑 robot2의 역할:robot2는 robot1이 지나간 후 남은 점수 중에서 최대한 많..
(Python3) - LeetCode (Medium) : 2270. Number of Ways to Split Array https://leetcode.com/problems/number-of-ways-to-split-arrayprefix sum 문제였습니다.📕 풀이방법📔 입력 및 초기화1. length 선언 후 nums의 길이를 저장합니다.2. 누적합을 저장할 배열 sums를 선언 후 length만큼 0으로 초기화합니다. 3. valid_splits를 선언 후 0으로 초기화합니다. 4. sums의 누적합을 구해 갱신해줍니다.📔 풀이과정0에서 length - 2까지 for loop를 수행하며 split된 left_sum, right_sum을 구해줍니다. 0부터 i까지의 합이 sum[i], i+1부터 끝까지의 누적합은 sum[length-1] - sum[i]가 되므로 O(n)만에 valid 한 splits인지 구할 수 ..
(Python3) - LeetCode (Medium) : 2559. Count Vowel Strings in Ranges https://leetcode.com/problems/count-vowel-strings-in-rangesprefix sum(누적합) 문제였습니다.📕 풀이방법📔 입력 및 초기화정답 배열 ans, 각 단어별 vowel str이 모음인지 여부를 저장할 배열 is_word_vowel을 선언 후 빈 배열로 초기화합니다.📔 풀이과정1. 각 단어의 처음과 끝이 모음인지 여부를 반환하는 함수 is_vowel_str을 선언 후 각 단어별로 호출해 결과를 is_word_vowel에 append해줍니다. 2. 누적합 vowel_str_sum을 선언 후 word의 길이만큼 순회하며 i번째 index까지의 vowel str개수를 구해 저장합니다. 3. queries정보를 순회하며 다음을 진행합니다.  3-1. 각 que..
(Python3) - LeetCode (Medium) : 2466. Count Ways To Build Good Strings https://leetcode.com/problems/count-ways-to-build-good-strings dp 문제였습니다.📕 풀이방법📔 입력 및 초기화MOD를 선언 후 10**9 + 7로 초기화합니다.📔 풀이과정어떤 문자열 i길이를 만들기 위해 0을 zero개와 1을 one개를 사용할 때 다음과 같은 점화식을 세울 수 있습니다.$${D[i] = D[i-one] + D[i-zero]}$$ 1. 빈 문자열을 만드는 경우는 1이므로 dp[0]은 1로 초기화하고 1에서 high까지 for loop또는 재귀함수를 수행하며 각자 길이를 만드는 경우의 수를 구해줍니다. 2. low에서 high까지 다시 dp 값을 answer에 누적해 더해준 후 MOD연산을 적용해 갱신합니다.📔 정답 출력 | 반환a..
(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 문제였습니다. 📕 풀이방법 📔 풀이과정..

티스토리툴바