백준 2003 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 전 나의 생각 N개의 수로 된 수열이 주어진다. 이 수열의 i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수를 구해야 한다. 조건 - N(1 ≤ N ≤ 10,000) - M(1 ≤ M ≤ 300,000,000) - A[x]는 30,000을 넘지 않는 자연수 과정 N, M, A[x]는 int의 범위를 벗어나지 않기 때문에 데이터 타..
알고리즘 및 자료구조/이분탐색
백준 1644 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 전 나의 생각 자연수 N이 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 4,000,000) 과정 N은 1이상 400만 이하의 값의 범위를 가지기 때문에 데이터 타입을 int로 설정한다. 소수들을 더해줄 누적합의 공간은 400만을 크게 벗어나지 않을 것이기 때문에 데이터 타입을 int로 설정한다. -> 목표로하는 소수의 합은 N이기 때문 소수를 구할 때 최적화 된 방법없이 2중 for문을 사용하면 400만 * 400만의 계산 횟..
백준 2512 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 풀이 전 나의 생각 예산이 담긴 M의 배열이 주어질 때 국가예산의 총액에서 최대로 예산을 배정할 수 있는 상한액을 구해야한다. 조건 - N은 3 이상 10,000 이하 - N개의 정수는 모두 1 이상 100,000 이하 - M은 N 이상 1,000,000,000 이하 과정 N과 M은 10억 이하기 때문에 데이터 타입은 int로 설정한다. 지방의 수 N이 10000이 주어지고 모..
백준 12012 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 전 나의 생각 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구해야한다. 조건 - (1 ≤ N ≤ 1,000,000) - (1 ≤ Ai ≤ 1,000,000) 과정 Ai는 양수이며 100만의 크기를 갖기 때문에 Ai를 담는 배열의 데이터 타입은 int로 설정한다. 수열 A의 크기 N은 100만이지만 2중 for 문만을 이용한 탐색을 진행한다면 100만 * 100만의 계..
백준 7453 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 전 나의 생각 정수로 이루어진 크기가 같은 배열 A, B, C, D가 주어지는데 이 때 A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구해야한다. 조건 - n (1 ≤ n ≤ 4000) - 배열에 들어있는 정수의 절댓값은 최대 2^28 과정 n은 4000까지 주어지지만 a, b, c, d 총 4개의 값을 확인하며 탐색..
백준 2473 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 전 나의 생각 산성 용액과 알칼리성 용액이 주어질 때 세 용액을 합해서 나온 값이 0에 가장 가까운 용액들을 구해야한다. 조건 - N개의 정수 모두 -1,000,000,000 이상 1,000,000,000 이하 - N은 3 이상 5,000 이하의 정수 - 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다. 과정 1. N개의 정수 즉..
백준 2143 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 전 나의 생각 배열 A, B가 주어질 때 A의 부 배열 합에 B의 부 배열 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구해야 한다. 조건 - 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n) - 부 배열의 합은 A[i]+…+A[j]를 의미한다...
백준 2110 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 전 나의 생각 도현이의 집 N개의 좌표에 공유기를 설치할 것이다. 단, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 설치하고 이 때 가장 인접한 두 공유기 사이의 거리를 최대로 하는 값을 구해야한다. 조건 - N (2 ≤ N ≤ 200,000) - C (2 ≤ C ≤ N) - xi (0 ≤ xi ≤ 1,000,000,00..
