백준 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개의 정수 즉..
백준 10773 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 전 나의 생각 재현이가 0을 외칠 때마다 최근에 재민이가 쓴 수를 지우고 나온 장부의 최종 합의 값을 구해내야한다. 조건 - (1 ≤ K ≤ 100,000) - 정수는 0에서 1,000,000 사이의 값 과정 K가 10만회 까지 나올 수 있으니 1중 for문을 사용하여 해결하면 될 것 같다. 주어지는 정수는 int 타입으로 충분할 것 같다. ..
백준 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..
백준 1253 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 전 나의 생각 N개의 수에서 어떤 수가 다룬 수 두 개의 합으로 나타낼 수 있다면 "좋다" 라고 한다. 따라서 "좋다"를 만족하는 좋은 수가 몇 개인지 구해야한다. 조건 N(1 ≤ N ≤ 2,000) |Ai| ≤ 1,000,000,000, Ai는 정수 Solution 조건으로 알 수 있는 것은 일반적인 탐색 방법인 3중 for문을 이용한 방법은 2000 * 2000 * 2000의 계산 횟수로 시간 제한을 ..
