-
오늘의 계획
-
대표적인 관계형 DB인 MYSQL 강의 듣기
- 섹션 1. Database 2 - MySQL 서론 -
동적 프로그래밍 알고리즘 공부 및 문제 풀이
-
-
오늘의 회고
- 인프런 DataBase 강의 수강 - 관계형 데이터베이스는 데이터를 표의 형태로 정리정돈 가능하고, 정렬 검색과 같은 작업을 빠르고 편리하고 안전하게 할 수 있음. 코드를 통해 데이터를 조작할 수 있음. - 강의를 들으며 예전에 깔아놓았던 버전의 bitnami로 MySQL 실습을 진행하던 도중 MySQL 비밀번호를 잊어버려서 일부분 하지 못하였다. 다음주 모각코 모임 전 까지 해오도록 하겠다.- 동적 프로그래밍 알고리즘 문제 : 프로그래머스 LEVEL 3(정수 삼각형) - 동적 프로그래밍 알고리즘 : 동적 프로그래밍은 큰 문제를 작은 문제로 나누어 해결하는 방식이다. 따라서 이미 해결한 작은 문제들에 대해서는 다시 수행하지 않고, 다른 곳에 저장해 두었다가 나중에 그 값을 사용하는 형태로 해결한다.  **-해결 방법** : 우선 반복문을 통해 삼각형에서 좌측 끝과 우측 끝 그리고 내부의 경우 3가지로 나누어 해결하였다. 좌측 끝과 우측 끝의 경우 바로 위 까지의 합과 현재 triangle에서의 값을 더하고, 내부일 경우 좌측에서 오는 경우와 우측에서 오는 경우로 나누어 두 값중 큰 값을 선택하도록 하였다. 이중 for문에서 내부 반복문의 종료 전, 현재까지의 answer과 비교하여 큰 값을 선택하도록 하였다. 공간의 절약을 위해 이차원 배열도 동적으로 할당하였다. - 코드
#include <string>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;
int solution(vector<vector<int>> triangle) {
int height = triangle.size();
int answer = triangle[0][0];
int** dp = new int* [height]; //공간 절약을 위한 동적 할당
for (int i = 0; i < height; ++i) {
dp[i] = new int[height];
memset(dp[i], 0, sizeof(int) * height);
}
dp[0][0] = answer;
if (height == 1) return answer;
for (int i = 1; i < height; i++) { //세로
for (int j = 0; j <= i; j++) { //가로
if (j == 0) { //좌측 끝
dp[i][j] = dp[i - 1][j] + triangle[i][j];
}
else if (j == i) { //우측 끝
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
}
else { //내부
//내부의 경우 왼쪽에서 오는 경우와 오른쪽에서 오는 경우 중 큰 값을 선택
dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - 1]
? dp[i - 1][j] : dp[i - 1][j - 1])
+ triangle[i][j];
}
answer = (dp[i][j] > answer ? dp[i][j] : answer); //큰 값으로 교체
}
}
for (int i = 0; i < height; ++i) {
delete[] dp[i];
}
delete[] dp;
return answer;
}