Dynamic Programming
-
[Algo Rhythm🕺💃] BOJ 2225 - 합분해Algo Rhythm🕺💃/BOJ 2021. 7. 22. 22:15
💫문제 분석 입력으로 주어지는 두 정수를 각각 라고 하자. 그리고 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 라고 하자. 마지막으로 N을 만들기 위해 더해지는 K개의 정수들을 순서대로 라고 하자. 의 규칙을 파악하기 위해 를 구하는 과정을 분석해보자. 은 아래와 같이 6이다. 이때 과 나머지 의 관계를 파악해보자. 일때 를 구하는 것은 을 구하는 것과 같다. (1이 적힌 파란 원으로 표시함) 일때 를 구하는 것은 ..
-
[Algo Rhythm🕺💃]BOJ 14501 - 퇴사Algo Rhythm🕺💃/BOJ 2021. 3. 11. 00:41
문제분석 백준이는 번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 단순히 생각하면 i번째 날의 일을 하는 경우와 안 하는 경우로 나눠서 모든 경우를 살핀 뒤 그 중 최대의 이익을 구하면 될 것 같다. 사실 그래도 된다. 하지만 조금 더 생각해보면 보다 더 효율적인 방법이 있다는 것을 알 수 있다. 앞서 말했듯이 백준이는 i번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 자세히 말하면 만약 i번째 날의 일을 한다면 번째 날의 일부터 하느냐 마느냐를 선택할 수 있고 만약 i번째 날의 일을 하지 않는다면 번째 날의 일부터 하느냐 마느냐를 선택할 수 있다. 즉, 백준이가 i번째 날의 일을 하느냐 마느냐를 결정..
-
[Algo Rhythm🕺💃] BOJ 17626. Four SquaresAlgo Rhythm🕺💃/BOJ 2020. 8. 24. 15:06
📚 문제 설명 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램..
-
[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 등굣길Algo Rhythm🕺💃/Programmers 2020. 8. 6. 15:21
📚 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. m과..
-
[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 정수 삼각형Algo Rhythm🕺💃/Programmers 2020. 8. 4. 15:40
📚 문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 🎯 어떻게 풀었나 1. DFS (50/ 100) - 효율성 통과 🙅♀️🙅♂️🙅 class Solution { public int solution(int[]..
-
[Algo Rhythm🕺💃] LeetCode - Number of Substrings With Only 1sAlgo Rhythm🕺💃/LeetCode 2020. 7. 19. 17:34
📚 Problem description Given a binary string s (a string consisting only of '0' and '1's). Return the number of substrings with all characters 1's. Since the answer may be too large, return it modulo 10^9 + 7. Example 1: Input: s = "0110111" Output: 9 Explanation: There are 9 substring in total with only 1's characters. "1" -> 5 times. "11" -> 3 times. "111" -> 1 time. Example 2: Input: s = "101"..