목록알고리즘 (76)

키베이루's diary

[C++] 백준 1309번 동물원

1) 문제설명 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 2) 아이디어 처음에는 2차원 배열로 dp를 설정하여 마릿수 / n층으로 표를 그려 규칙을 찾으려고 했으나 규칙을 찾기가 매우 어려웠다. 따라서 이를 해결하기 위해 dp [n층][사자를 배치하지 않음/ 사자를 왼쪽에 배치/ 사자를 오른쪽에 배치]로 나누어서 생각하였다. 처음 dp [1][0] = 1층에 사자를 배치하지 않는 경우의 수는 = 1이다 마찬가지로 dp [1][1] = 1층에 사자를 왼쪽 배치할 경우의 수 = dp [1][2] = 1층에 사자를 오른쪽 배치할 경우의 수 = 1 이후 2층에 사자를 배치할 경우..
알고리즘/DP 2022. 7. 11. 12:30
[C++] 백준 15988번 1, 2, 3 더하기 3

1) 문제설명 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2) 아이디어 1을 만들기 위해 필요한 1,2,3의 값은 dp [1] = 1 (1) 2를 만들기 위해 필요한 1,2,3의 값은 dp [2] = 2 (1+1) (2) 3을 만들기 위해 필요한 1,2,3의 값은 dp [3] = 4 (1+1+1) (1+2) (2+1) (3) 이때 4를 만들기 위해 필요한 1,2,3의 값을 살펴보면 1+1+1+1 -> (1+1+1 +1) 1+2+1 -> (1+2 +1) 2+1+1-> (2+1 +1) 3+1 ..
알고리즘/DP 2022. 7. 11. 10:59
[C++] 백준 11660번 구간 합 구하기 5

1) 문제설명 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2) 아이디어 표를 그리면서 생각하였다. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 입력받은 배열(표)에서 먼저 누적합을 구한다. sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i][j] - sum[i - 1][j - 1]; // 누적합 1 3 6 10 3 8 15 24 6 15 27 4..
알고리즘/DP 2022. 7. 9. 13:29
[C++] 백준 2559번 수열

1) 문제설명 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 2) 아이디어 입력받은 배열의 누적합을 sum배열에 저장한다. 누적합에서 k번째 이후만큼을 빼주면 k일의 연속적인 날짜의 수의 누적합이 나온다. 이후 k일의 연속적인 날짜의 수의 누적 합의 최댓값을 출력한다. 3) 코드 #include #include #include #include #include #include #include #include334 using name..
알고리즘/기타 2022. 7. 8. 13:38
[C++] 백준 11659번 구간 합 구하기 4

1) 문제설명 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 2) 아이디어 for문을 2번 사용하여 구간의 합을 구 할 경우 O(N^2)의 시간이 걸리기 때문에 O(N+M)의 시간 안에 문제를 해결해야 한다. 구간의 합을 배열로 설정한 후 미리 구하여 b번째의 합에서 a-1번째의 합까지를 빼면 구간 a~b까지의 구간의 합을 구할 수 있다. 3) 코드 #include #include #include #include #in..
알고리즘/기타 2022. 7. 6. 12:30
[C++] 백준 1920번 수 찾기

1) 문제설명 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 2) 아이디어 입력받은 배열을 오름차순으로 배열하고 이진 탐색으로 찾는다. 이번에는 이진 탐색을 직접 구현하지 않고 STL을 사용해서 해결하였다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr..
알고리즘/기타 2022. 7. 5. 09:51
[C++] 백준 10815번 숫자 카드

1) 문제설명 2) 아이디어 상근이가 가지고 있는 숫자 카드를 오름차순으로 정렬하고 이분 탐색을 통해 숫자카드를 가지고 있으면 1을 출력, 가지고 있지 않으면 0을 출력한다. 기본적인 이분 탐색 알고리즘을 알고 있다면 쉽게 풀 수 있다. printf, scanf 함수를 사용해서 시간 초과가 나지 않도록 주의한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr[500001]; int brr[500001]; int search(int start, int end, int key) { if (start == end) { if (arr[start] == key) { //..
알고리즘/기타 2022. 7. 5. 08:37
[C++] 백준 14501번 퇴사

1) 문제설명 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2) 아이디어 DP문제를 1부터 차근차근 시도하다가 끝부분에서 Ti가 N을 넘어버리면 안 되기 때문에 구현에 어려움을 느꼈다. 또한 상담에 걸리는 일수에 따라 최댓값이 바뀌는 것에 대한 점화식도 생각해야 했다. 그래서 반대로 끝에서부터 차근차근 생각하였다. 문제에 있는 표를 끝에서 부터 살펴보면 DP [7] = 0 -> Ti 가 2기 때문에 범위(N)를 넘어가 버린다. DP [6] = 0 -> Ti 가 4기 때문에 범위(N)를 넘어가 버린다. DP [5] = 15 -> Ti가 범위를 넘어가지 않는다. DP [4] = 2..
알고리즘/DP 2022. 6. 24. 08:04
Prev 1 2 3 4 5 6 7 ··· 10 Next