[ダイナミックプランニング]整数三角形
[プログラマ]整数三角形
三角形の頂部から底部までの経路では,通過する数字の和が最大の場合を見つけようとする. の下のセルに移動すると、1つのセルの右または左側だけが対角線方向に移動します. 解関数を記述し、を通過した数値の最値を返します. int[][三角形:三角形情報を含む2 D配列
最も効率的なコード
[2021.01.26]
[2021.01.26]
ドアの外に出る場合は、前より減った結果がほぼ目で確認できます.
しかし、効率テストは8回、9回、10回(?)ジェジュンは効率的ではありません.
[2021.01.26]
上記の特殊な状況を除いて,時間的複雑度は著しく減少した.
特殊な状況にはいったいどんな状況があるのだろうか.
これまで、for文の内容→for文の数が最小限でなければならず、その中の内容も最小限でなければならない点が異なっていた.
[2021.01.27]
[効率]
-冗長for文:O(n^2)-for文:O(1)+for文:O(1)結論はfor文が少なければ少ないほどよいが,for文を追加してもfor文を繰り返す内容物を減らすことが最も有効である.
|問題説明|
- 삼각형의 높이 : 1 이상 500 이하
- 삼각형을 이루고 있는 숫자 : 0 이상 9,999 이하, 정수
||トラブルシューティング|
1) DP : O(n^2)
|コード|
最も効率的なコード
[2021.01.26]
class Solution {
public int solution(int[][] triangle) {
int answer = 0;
for(int i=1; i<triangle.length; i++) {
for(int j=0; j<triangle[i].length; j++) {
if(j == 0) triangle[i][j] += triangle[i-1][j];
else if(j == triangle[i].length - 1) triangle[i][j] += triangle[i-1][j-1];
else triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
if(i == (triangle[i].length - 1) && triangle[i][j] > answer) answer = triangle[i][j];
}
}
return answer;
}
}
[2021.01.26]
- 시간복잡도를 줄이는 방법은 무엇이 있을까
- 모든 O(n^2)동안 한 번씩 거쳐갈 if(i == (triangle[i].length - 1) && triangle[i][j] > answer) answer = triangle[i][j]; 이 코드를 따로 빼준다면 어떠한 변화가 있을까
class Solution {
public int solution(int[][] triangle) {
int answer = 0;
for(int i=1; i<triangle.length; i++) {
for(int j=0; j<triangle[i].length; j++) {
if(j == 0) triangle[i][j] += triangle[i-1][j];
else if(j == triangle[i].length - 1) triangle[i][j] += triangle[i-1][j-1];
else triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
}
}
for(int i=0; i<triangle[triangle.length-1].length; i++) {
if(triangle[triangle.length-1][i] > answer) answer = triangle[triangle.length-1][i];
}
return answer;
}
}
ドアの外に出る場合は、前より減った結果がほぼ目で確認できます.
しかし、効率テストは8回、9回、10回(?)ジェジュンは効率的ではありません.
[2021.01.26]
- for문의 조건문을 for문 3개로 나눴을 경우
class Solution {
public int solution(int[][] triangle) {
int answer = 0;
for(int i=1; i<triangle.length; i++) {
triangle[i][0] += triangle[i-1][0];
}
for(int i=1; i<triangle.length; i++) {
triangle[i][triangle[i].length - 1] += triangle[i-1][triangle[i].length - 2];
}
for(int i=1; i<triangle.length; i++) {
for(int j=1; j<triangle[i].length-1; j++) {
triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
}
}
for(int i=0; i<triangle[triangle.length-1].length; i++) {
if(triangle[triangle.length-1][i] > answer) answer = triangle[triangle.length-1][i];
}
return answer;
}
}
上記の特殊な状況を除いて,時間的複雑度は著しく減少した.
特殊な状況にはいったいどんな状況があるのだろうか.
これまで、for文の内容→for文の数が最小限でなければならず、その中の内容も最小限でなければならない点が異なっていた.
[2021.01.27]
class Solution {
public int solution(int[][] triangle) {
int answer = 0;
for(int i=1; i<triangle.length; i++) {
triangle[i][0] += triangle[i-1][0];
triangle[i][triangle[i].length - 1] += triangle[i-1][triangle[i].length - 2];
}
for(int i=1; i<triangle.length; i++) {
for(int j=1; j<triangle[i].length-1; j++) {
triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
}
}
for(int i=0; i<triangle[triangle.length-1].length; i++) {
if(triangle[triangle.length-1][i] > answer) answer = triangle[triangle.length-1][i];
}
return answer;
}
}
[効率]
-冗長for文:O(n^2)
Reference
この問題について([ダイナミックプランニング]整数三角形), 我々は、より多くの情報をここで見つけました https://velog.io/@yerin6860/동적계획법-정수삼각형テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol