[프로그래머스]탐욕법(Greedy) : 섬 연결하기 (level 3)(c++)
https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr #include #include #include using namespace std; // 노드x가 포함된 트리의 루트노드 가져오기 int get_root(vector &parent, int x) { // x가 노드x의 부모라면 if (x == parent[x]) { return x; } /* 다른 노드가 노드x의 부모라면, 루트노드를 찾을 때까지 재귀함수 호출. 마지막에 노드x의 부모에 해당 루트노드 저장후 반환 */ return parent[x] = get..
2020. 6. 18.
[프로그래머스]동적계획법(Dynamic Programming) : 정수 삼각형 (level 3)(c++)
https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr #include #include #include using namespace std; const int MAX = 500; int D[MAX + 1][MAX + 1]; int solution(vector triangle) { int N = triangle.size(); /* 점화식 : D[i][j] = tri[i][j]로 올 수 있는 경로의 i - 1번째 최대값 + tri[i][j] */ for (int i = 1; i
2020. 6. 17.
