반응형 전체 글163 99클럽 코테 스터디 21일차 TIL - DP (프로그래머스 '도둑질') 항해99 코테 스터디 21일차 문제인 프로그래머스의 '도둑질'은 원형으로 이어진 집들을 도둑질하여 얻을 수 있는 가장 큰 금액을 구하는 문제이다. 난이도는 레벨4이며 다이나믹 프로그래밍을 통해 해결할 수 있다. 오늘의 문제 - 도둑질 문제 정보문제 키워드- DP난이도- Level 4 문제 요약모든 집은 원형으로 이어져 있으며, 연속된 두 집을 터는 경우 경보가 울린다.경보가 울리지 않고 도둑질을 할 때, 얻을 수 있는 가장 큰 금액을 구하여라. 문제 풀이 과정 원형으로 이어져 있으므로 첫번째 집을 터냐 마냐에 따라서 마지막 집을 털 수 있는지가 달라진다.따라서 첫번째 집을 터는 경우와 안 터는 경우로 나누어서 DP 배열 값들을 구해야 한다.dp[i] = (dp[i-2] + money[i], dp[i-1.. 2024. 6. 10. 99클럽 코테 스터디 20일차 TIL - DP (프로그래머스 '사칙연산') 항해99 코테 스터디 20일차 문제인 프로그래머스의 '사칙연산'은 덧셈과 뺄셈만으로 주어진 식에 괄호를 추가하여 구할 수 있는 최댓값을 반환하는 문제다. 난이도는 레벨4이며 DP를 통해 해결할 수 있다. 오늘의 문제 - 사칙연산 문제 정보문제 키워드- Dynamic Programming난이도- Level 4 문제 요약숫자와 연산자(+ 또는 -)가 번갈아 들어있는 리스트가 주어졌을 때, 괄호를 원하는 대로 추가하여 나올 수 있는 결과 중 최대값을 구하시오. 문제 풀이 과정 계속 헤매다가 도저히 떠오르지 않아서 좋은 해설글을 참고했다.가장 중요한 포인트는, 뺄셈 연산의 최댓값을 구하기 위해 최솟값도 가지고 있어야 한다는 부분이다.이를 이용해 모든 구간의 최댓값과 최솟값을 구해가면서 최종적으로 전체 식의 최.. 2024. 6. 8. 99클럽 코테 스터디 19일차 TIL - DP (프로그래머스 '정수 삼각형') 항해99 코테 스터디 19일차 문제인 프로그래머스의 '정수 삼각형'은 정수로 이루어진 삼각형을 한층씩 타고 내려가면서 맨 밑층까지 도달했을 때 구할 수 있는 가장 큰 합을 구하는 문제다. 난이도는 레벨3이며 동적계획법을 통해 해결할 수 있다. 오늘의 문제 - 정수 삼각형 문제 정보문제 키워드- DP난이도- Level 3 문제 요약한변의 길이가 N인, 정삼각형 모양의 배열이 주어진다. 각 원소의 값은 모두 0 이상의 9999 이하의 정수이다.맨 윗칸에서 한칸씩 아래로 내려가며 합을 구해가는데, 아래로 내려갈 때는 바로 왼쪽 대각선 또는 오른쪽 대각선으로만 이동할 수 있다. 이렇게 맨 밑층까지 내려갔을 때 구해진 합들 중 최대값을 구하여라. 문제 풀이 과정 이전까지의 합을 이용해 다음 합을 구할 수 있는,.. 2024. 6. 7. 99클럽 코테 스터디 18일차 TIL - DP (프로그래머스 'N으로 표현') 항해99 코테 스터디 18일차 문제인 프로그래머스의 'N으로 표현'은 주어진 숫자 N과 사칙연산을 이용해 목표 숫자를 만드는 데 N이 최소 몇개 사용되는지를 구하는 문제다. 난이도는 레벨3이며 DP를 통해 해결할 수 있다. 오늘의 문제 - N으로 표현 문제 정보문제 키워드- DP난이도- Level 3 문제 요약1~9 사이의 정수 N과 목표 숫자 number가 주어진다.N과 사칙연산을 가지고 number를 만들 때, 필요한 N의 최소 갯수를 구하라. 문제 풀이 과정 N의 개수마다 만들 수 있는 숫자들을 dp 맵에 저장한다.dp[cnt]를 구할 때, dp[cnt-1] (op) dp[1], dp[cnt-2] (op) dp[2], …를 이용한다.코드import java.util.*;class Solution .. 2024. 6. 6. 이전 1 ··· 10 11 12 13 14 15 16 ··· 41 다음 반응형
