일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- Ainimation Blending
- 프리팹
- raycasting
- Unity
- Parallax
- Scrooling
- Object Pooling
- Object Poling
- 유니티
- 플레이어 이동
- 패럴렉스
- rigidbody
- Vector3
- CSharp #자료구조
- 2D슈팅게임
- LayerMark
- Hpbar
- Prefabs
- Hp바
- apk
- raycast
- 일시정지
- Blend Type
- rotation
- Animation State Machine
- 오브젝트 풀링
- Transform
- 플레이어 방향전환
- joystick
- 스크롤링
- Today
- Total
주녘공부일지
[프로그래머스 C#] Lv.3 연속 펄스 부분 수열의 합 본문
https://school.programmers.co.kr/learn/courses/30/lessons/161988
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 정답코드 및 핵심 아이디어, 유의사항
문제 이름 그대로 연속 펄스 부분 수열의 최대 합을 구하는 문제- 펄스 부분 수열이 적용된 경우에 따른 배열을 분리해 각 배열의 연속 부분 수열의 최대합을 구하면 됨
1) 펄스 부분 수열은 2가지 경우가 존재
- 인덱스를 기준으로 홀수에만 -1을 곱해준 경우와 짝수에만 -1을 곱해준 경우
2) 연속 부분 수열의 최대합을 구하는 방법
- 오른쪽 인덱스를 기준으로 하나씩 더해가며 음수가 되지 않는 경우라면 무조건 포함해야 함즉, dp로 간단하게 풀 수 있음 https://godgjwnsgur7.tistory.com/109
[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation
1. 동적 계획법(DP : Dynamic Programming) 복잡한 하나의 큰 문제를 여러 개의 작은 문제로 나누어 해결하는 문제해결 방법 중 하나 - 작은 문제의 연산 결과를 저장해놓았다가 다시 큰 문제를 해결할
godgjwnsgur7.tistory.com
점화식 ( 코드상으로 dp = intArray, arr = sequence )
- dp[i] = Math.Max( 0, dp[i - 1] ) + arr[i] ( 단, i > 0 / dp[0] = arr[0] )
주석 참조
using System;
using System.Linq;
public class Solution
{
public long solution(int[] sequence)
{
long answer = 0;
var sequence2 = (int[])sequence.Clone();
// 두 가지 펄스 수열을 곱한 배열
for (int i = 0; i < sequence.Length; i++)
{
sequence[i] *= (i % 2 == 0) ? 1 : -1;
sequence2[i] *= (i % 2 != 0) ? 1 : -1;
}
// 각 부분수열의 최대합을 구함
long n1 = Function(sequence);
long n2 = Function(sequence2);
answer = Math.Max(n1, n2);
return answer;
}
// 연속 부분수열의 최대합을 리턴하는 메서드
public long Function(int[] sequence)
{
var intArray = new long[sequence.Length]; // dp배열
intArray[0] = sequence[0];
// i를 오른쪽 끝 인덱스로 하는 범위 내에서의 최대합
for (int i = 1; i < intArray.Length; i++)
intArray[i] = Math.Max(0, intArray[i - 1]) + sequence[i];
return intArray.Max();
}
}
'Programmers - C# > CodingTest Lv.3' 카테고리의 다른 글
[프로그래머스 C#] Lv.3 입국심사 (0) | 2024.01.26 |
---|---|
[프로그래머스 C#] Lv.3 다단계 칫솔 판매 (1) | 2024.01.25 |
[프로그래머스 C#] Lv.3 가장 긴 팰린드롬 (0) | 2024.01.24 |
[프로그래머스 C#] Lv.3 스티커 모으기(2) (1) | 2024.01.04 |
[프로그래머스 C#] Lv.3 미로 탈출 명령어 (0) | 2023.12.13 |