문제 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 풀이 투 포인터를 활용 Solving 문제에서 주어지는 수열에서 구간합이 M이 되는 조합의 경우의 수를 구하는 문제입니다. 그리디하게 접근하여 풀이를 하게되면 2중 for문으로 시간복잡도가 O(N^2)이 됩니다. 그리디한 풀이는 다음과 같습니다. 각 수열의 i번째 원소에서부터 i+1번 이후의 수열을 누적 누적합이 M이 되면 카운트 본격적으로 투 포인터..

문제 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수열에서 나올 수 있는 모든 부 배열을 누적합을 활용하여 구함 Map 자료구조를 활용하여 해당 누적합 값이 기존에 들어가있다면 value증가, 없다면 put A의 부 배열 개수만큼 반복문을 돌면서 목표값 T - A[i](부 배열 원소) 값이 B 부 배열 M..

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 Dijkstra를 활용한 풀이 접근법 조건 - 첫번째 컴퓨터는 슈퍼컴퓨터로써 반드시 복구해야합니다. - 슈퍼 컴퓨터로부터 나머지 N-1개의 컴퓨터까지 최단 경로로 통신이 가능해야합니다. - 양방향 그래프 풀이 간단한 데이크스트라를 통해 슈퍼 컴퓨터를 시작노드로 나머지 노드까지의 최단경로를 우선순위 큐를 통해 탐색. 탐색하는 과정에서 방문체크를 같이 진행. 이전..

문제 https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 풀이 그리디 방식을 활용한 풀이 접근법 전처리 입력이 거리순으로 들어오지 않을 수 있으니 거리를 기준으로 정렬 조건 각 사람까지의 거리의 합 마을이 없는 위치에 우체국을 세울 수 없음 마을 위치, 인구 수 입력의 범위는 최대 1,000,000,000 마을 거리의 합이 아니라 각 사람까지의 거리의 합이 최소가 되..