목록동적계획법 (22)

반갑습니다!

[프로그래머스] 정수 삼각형

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 동적계획법으로 해결하였다. 맨 아랫줄에서 시작해서 맨 윗줄이 될 때까지 최댓값을 더하면서 값을 갱신해주면 된다. 코드 C++ #include #include #include using namespace std; int solution(vector triangle) { for(int i=triangle.size()-2; i>=0; i--) for(int j=0; j= 0; i--) for (int j = 0; j < triangle[i].length; j++) triangle[i][j] = Math.max..
알고리즘 문제 풀이 2020. 4. 9. 16:14
[프로그래머스] 땅따먹기

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 동적계획법 문제이다. dp[i][j]는 i-1번째 열에 저장된 값 중 dp[i-1][j]를 제외한 값 중에서 최대값에 land[i][j]를 더한 값이 되어야한다. 코드 C++ #include #include #include using namespace std; int solution(vector land) { int answer = 0; vector dp(land.size(), vector(land[0].size(), 0)); for (int i = 0; i < land[0].size(); i++) dp..
알고리즘 문제 풀이 2020. 4. 9. 02:18
[프로그래머스] 가장 큰 정사각형 찾기

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2차원 배열이 들아온다고해서 2x2 사이즈 이상이라고 생각했다가 테스트케이스 1번이 계속 틀려서 한참을 헤맸다... [[1]] 인 경우가 있을 수 있다는 것을 간과하였다.. 풀이 동적계획법으로 해결할 수 있다. board[i-1][j], board[i][j-1], board[i-1][j-1] 중 최소값에 1을 더해준 수를 board[i][j]에 대입해주면서 board를 갱신하여 해결하였다. 예를 보면서 확인해보자 (1, 1) 위치에서 탐색을 시작한다. (0, 0), (0, 1), (1, 0)의 값 중 최소값이..
알고리즘 문제 풀이 2020. 4. 9. 01:25
[프로그래머스] 멀리 뛰기

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 n번째 칸에 이동하는 방법 수는 n-1번째 칸에서 1칸 이동한 수와 n-2번째 칸에서 2칸을 한번에 이동한 수와 같다. 따라서 n번째 칸에 이동한 방법의 수를 dp[n]이라 하면 dp[n] = dp[n-1] + dp[n-2]가 성립한다. 코드 C++ #include #include using namespace std; long long dp[2001]; long long solve(int idx){ if(dp[idx] != -1) return dp[idx]; return dp[idx] = (solve(i..
알고리즘 문제 풀이 2020. 4. 7. 14:05
[프로그래머스] 타일 장식물

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 N개의 타일로 구성된 직사각형의 둘레를 구하기에 앞서, 각 타일들의 길이가 어떻게 되는지를 먼저 살펴봐야한다. 타일의 한 변의 길이는 1, 1, 2, 3, 5, 8, ... 이런 식으로 변한다. 그림을 잘 살펴보면 결국 한 변의 길이는 피보나치 수열과 일치함을 알 수 있다. 한 변의 길이를 피보나치 수열로 구할 수 있다는 것을 알게 되었으므로 이제 N개의 타일로 구성된 직사각형의 둘레를 구해보자. 위의 두 그림에서 빨간색 선의 길이는 동일하다는 것을 알 수 있다. 따라서 N개의 타일로 구성된 직사각형의 ..
알고리즘 문제 풀이 2020. 4. 6. 12:45
이전 Prev 1 2 3 4 5 Next 다음