일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 세그먼트 트리
- java
- 플로이드-와샬
- 투 포인터
- JUnit 5
- BFS
- 수학
- 유니온 파인드
- 위상정렬
- 알고리즘
- Kotlin
- 에라토스테네스의 체
- 후니의 쉽게 쓴 시스코 네트워킹
- 이분탐색
- Network
- mst
- 백준
- swea
- dfs
- 문자열
- 프로그래머스
- 구현
- 시뮬레이션
- Effective Java
- 그리디
- 스택
- 동적계획법
- 완전탐색
- 백트래킹
- CS
목록동적계획법 (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..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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)의 값 중 최소값이..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 N개의 타일로 구성된 직사각형의 둘레를 구하기에 앞서, 각 타일들의 길이가 어떻게 되는지를 먼저 살펴봐야한다. 타일의 한 변의 길이는 1, 1, 2, 3, 5, 8, ... 이런 식으로 변한다. 그림을 잘 살펴보면 결국 한 변의 길이는 피보나치 수열과 일치함을 알 수 있다. 한 변의 길이를 피보나치 수열로 구할 수 있다는 것을 알게 되었으므로 이제 N개의 타일로 구성된 직사각형의 둘레를 구해보자. 위의 두 그림에서 빨간색 선의 길이는 동일하다는 것을 알 수 있다. 따라서 N개의 타일로 구성된 직사각형의 ..