https://school.programmers.co.kr/learn/courses/30/lessons/43105
|
#include <vector> int path(std::vector<std::vector<int>>& triangle, int x, int y); int cache[500][500]; int solution(std::vector<std::vector<int>> triangle) { int path(std::vector<std::vector<int>>& triangle, int x, int y) { return ret = std::max(path(triangle, x+1, y), path(triangle, x+1, y+1)) + triangle[x][y]; |
정확성은 다 통과하는데 효율성에서 걸림
cache 때문에 걸리는거 같은데 뭔가 좋은 방법이 있을까?
좋은 방법이 떠오르질 않는다! 그냥 소스를 싹 다 갈아 엎어야 하나 ㅜㅜ
172102
max 함수때문일거같은데 max가 전체 탐색도는거라
집에가게해줘
오홍! 변수에 넣고 삼항 연산자로 해봐야겠다!
샤이닝
input 보니깐 합계가 0일 수도 있는데, if (ret != 0) 이렇게 하면 입력값이 아래 0이면 계속 파고들어서 시간 초과 나올 것 같음
cache의 초기값을 -1로 해보셈
샤이닝
돌려봤는데 이 로직으론 시간이 좀 빡빡한가 봄
if( x >= lineCnt )도 if( x == lineCnt)로 바꾸면 통과됨 ( 굳이 equal 연산으로 fast return 할거니깐 이럴 땐 equal로 비교하는게 성능이 더 빠름)
집에가게해줘
만일을 위해 항상 >=식으로만 비교해서 그건 몰랐네..!
개붕이는끝
재귀호출 말고 반복문으로 가능함. 아마도...?
심보고약한놈
방금해봤는데 반복문으로는 통과하는데 메모이제이션으로는 통과가 안되네
개붕이는끝
함수 호출이 은근 시간 많이 먹음.
1. 스택 할당하고
2. 할당한 스택에 리턴 어드레스, 매개변수 복사하고
3. 점프
까지 해야함
반복문은
1. 증감
2. 조건 점프
가 다라 호출보다 빠름
집에가게해줘
재귀나 반복이나 거기서 거기지 뭐.. 라는 생각도 있지만 이중반복문 보다 재귀로 하는게 소스가 훨씬 깔끔해서 사용한거였는데 경우의 수가 너무 많아서 그런건가.. 반복이 더 호율이 좋은가 보네 ㅜㅜ
심보고약한놈
아마 함수호출할때마다 triangle 주소값으로 4byte 씩 쌓여서 그런것 같은데 전역변수로 옮기고 해보셈. 하기 귀찮다
RX7900XTX
근데 이거 재귀로 풀어야 됨??? 방금 풀어봤는데 그냥 2차 반복문으로 다이네믹 프로그래밍으로 해결되는뎁???
---- [ 코드 ] -----
int DP[500][500] = { 0, };
int solution(vector<vector<int>> triangle)
{
int answer = 0;
int iRepeat = triangle.size();
DP[0][0] = triangle[0][0];
for (int i = 1; i < iRepeat; ++i)
{
for (int s = 0; s < triangle[i].size(); ++s)
{
// 인덱스가 같은 곳, 인덱스가 - 1인 곳(음수일 수도 있으니 한 번 체크)
DP[i][s] = max(DP[i][s], DP[i - 1][s] + triangle[i][s]);
if (0 <= s - 1)
DP[i][s] = max(DP[i][s], DP[i - 1][s - 1] + triangle[i][s]);
}
}
for (int i = 0; i < iRepeat; ++i)
answer = max(answer, DP[iRepeat - 1][i]);
return answer;
}
RX7900XTX
if (0 <= s - 1)이거 하기 싫으면 배열 크기 1개 키워서 하는것도 방법임
int DP[501][501] = { 0, };
int solution(vector<vector<int>> triangle)
{
int answer = 0;
int iRepeat = triangle.size();
DP[0][1] = triangle[0][0];
for (int i = 1; i < iRepeat; ++i)
{
for (int s = 0; s < triangle[i].size(); ++s)
{
DP[i][s + 1] = max(DP[i][s + 1], DP[i - 1][s + 1] + triangle[i][s]);
DP[i][s + 1] = max(DP[i][s + 1], DP[i - 1][s] + triangle[i][s]);
}
}
for (int i = 1; i <= iRepeat; ++i)
answer = max(answer, DP[iRepeat - 1][i]);
return answer;
}
RX7900XTX
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> triangle)
{
int answer = 0;
int iRepeat = triangle.size();
for (int i = iRepeat - 1; i > 0; --i)
{
for (int s = 0; s < i; ++s)
{
triangle[i - 1][s] += max( triangle[i][s], triangle[i][s + 1]);
}
}
answer = triangle[0][0];
return answer;
}
이렇게되 되네
원리가 그냥 삼각형 맨 바닥부터 가장 아래 큰 값을 위 값에 더라는 방식임 그래서 맨 위 0, 0에는 최대 값이 있는 원리네
#include <algorithm> 쓰기 싫으면
triangle[i - 1][s] += (triangle[i][s] >= triangle[i][s + 1]) ? (triangle[i][s]) : (triangle[i][s + 1]);
이렇게 하셈
집에가게해줘
재귀로 만들면서 아래에서 올라가는 형태로 for문 돌리면 되겠다.. 싶긴 했는데
재귀가 코드가 깔끔해서 어떻게든 재귀로 해결 볼라했지만 포기함 ㅜㅜ
RX7900XTX
재귀로 하고 싶다면 마지막에 역으로 계산하는거 있잖음?
그거처럼 역순으로 stack 최소화하면 될 것 같음 ㅇㅇ
집에가게해줘
[결론]
1. max를 빼고 삼항 연산자로 변경
2. triangle 주소 값 전달이 아닌, 전역 변수로 변경
3. 비교 연산자 >= 사용 대신 == 사용
위 3개 전부 해봤지만 시간 초과가 여전히 4개 있음. 결국 재귀 호출을 빼는 수 밖에 없는 듯 함
샤이닝
위에도 적었는데
if (ret != 0)
return cache[x][y];
요 부분 검증이 잘못 되어서 고쳐야함
ret ! = 0으로 검증하면 0인 구간은 처음보는 구간이라고 생각해서 중복으로 확인하러 들어가게 됨.
극단적으로 제일 상단 제외하고 전부 0인 삼각형으로 인풋값이 들어온다고 생각해보셈
집에가게해줘
너 말이 맞음 0~9999기 때문에 -1 초기화를 하는게 맞음
높이가 1~500인데 값도 자연스레 1~9999로 나 혼자 착각한 듯..
ye
집에가게해줘
로직 자체를 바꿔 버리면 통과 하는건 나도 알고 있었는데.. 코드도 깔끔하고 괜한 고집이 생겨서
"내가 방법을 몰라서 그렇지 이 로직으로도 통과할 수 있다!!" 라는 생각에 글 올려 본거...
하지만 포기했음 ㅋㅋㅋㅋ 결국 이중 for문으로 해결 봄 ㅜㅜ
스비니
사실 이런 건 문제 설계가 조금 이상한 게 아닌가 싶음..
재귀 + 메모이제이션 기법은 결국 DP랑 동일한 개념으로부터 출발하는 건데
재귀를 활용했을 때 "애매하게" 시간이 초과되도록 설계하는 건 좀 연습문제로서 적절하지 못한 듯
숨은음은
백트래킹, 메모이제이션, 재귀 등은 최적화 계산이 없는 경우 때만 빠른 거임.
저런 식으로 이전 값을 미리 저장해서 사용하면 되는 경우에는 재귀나 메모이제이션, 백트래킹 쓰면 안 됨
예를 들자면 피보나치 수열은 재귀로도 충분히 풀 수 있지만
이전 값을 또 계산할 필요가 전혀 없기 때문에 동적계획법으로 푸는 게 최적화임.
동적계획법은 어렵게 생각할 필요 없이
f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
이런 식으로 이전 항목으로 다음 항목을 구할 수 있는 "점화식"이 존재할 때
동적계획법 쓰는 거임