목록알고리즘 문제풀이/백준 (178)

홍시홍의 프로그래밍

[백준 1912] 연속합

분류 : dp 요구사항 주어진 수열 중 연속으로 이루어진 수열의 최대 값 구하기 풀이 현재 값이 최대일 경우는 두가지이다 1. 이전 값들의 합과 현재 값 더했을때 2. 현재 값 둘 중 하나가 최대 값이다 점화식은 다음과 같이 된다 d[i] = max(d[i - 1] + map[i], map[i]); #include #include #include using namespace std; int map[100100]; int d[100100]; int n; int main() { scanf("%d", &n); for (int i = 1; i
알고리즘 문제풀이/백준 2020. 4. 9. 01:27
[백준 1932] 정수 삼각형

분류 : dp 요구사항 꼭대기에서 시작하여 끝까지 가는 경로 중 각 노드에 적힌 값이 최대인 값을 구하여라 풀이 dp를 사용하여 top-down형식으로 구하였다 점화식은 ref = map[floor][now] + max(func(floor - 1, now - 1), func(floor - 1, now)); 현재 위치에서의 최대값은 (현재층 -1)층의 왼쪽, 오른쪽 중 최대값을 더한 값이다 #include #include #include using namespace std; int d[550][550]; int map[550][550]; int n; int func(int floor, int now) { if (floor == 1) { return map[1][1]; } //cout
알고리즘 문제풀이/백준 2020. 4. 9. 01:12
[백준 2579] 계단 오르기

분류 : dp 요구사항 조건에 따라 계단을 올랏을 경우, n번째 계단에서의 최댓값 구하기 풀이 dp로 풀이한다 점화식을 구하여 top-down 방식으로 푼다 func(num) = max(map[num-1] + func(num-3) , func(num-2) + map[num]); 현재 자리의 최대값은 현재값 + 이전 값 + -3까지의 최대값 or 현재값 + -2까지의 최대값이다 #include #include #include using namespace std; int d[330]; int map[330]; int n; int func(int num) { if (num == 0) return 0; if (num < 0) return 0; if (num == 1) return map[1]; int &ref ..
알고리즘 문제풀이/백준 2020. 4. 9. 00:43
[백준 1981] 배열에서 이동

분류 : 이분탐색, bfs 요구사항 (1,1) ~ (n,n)이동하는데 방문한 곳의 최소, 최대 값의 차이가 최소가 되도록 하기 풀이 최대, 최소값을 내가 정해준다음 bfs를 돌린다 start, end 포인트를 잡아주어, (n,n) 방문 할 수 있는 경우 최소를 구해야 하므로 start 증가 안될 경우 수의 차이를 증가 시켜 주어야 하므로 end 증가 #include using namespace std; #define FOR(i,k) for(int i=0 ; i < k ; i++) struct go { int x; int y; }; int map1[220][220]; int n; int maxv = 0; int minv = 987654321; vector v; int dr[4] = { -1,0,1,0 };..
알고리즘 문제풀이/백준 2020. 4. 4. 02:19
Prev 1 ··· 4 5 6 7 8 9 10 ··· 45 Next