분류 전체보기
-
[백준 13398] 연속합 2 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 23:48
www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제풀이 N, arr : 입력값 dp : 연속합을 구하기 위한 누적합 - dp[0][i] : 특정 원소를 제거하지 않은 경우 - dp[1][i] : 특정 원소를 제거한 경우 dp를 이용한 누적 합 문제이다. N 제한이 100,000 이기에 O(N^2) 이 아닌 그보다 빠른 방식으로 해결해야 한다. 1. dp[0][0] 을 arr[0]으로 초기화 한다. - 최소 1개의 원소는 반드시 선택해야 하기 때문에 dp[0][..
-
[백준 11660] 구간 합 구하기 5 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 15:20
www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제풀이 N, M : 입력값 board : 입력 배열(2차원 리스트) dp : 특정 좌표 (i, j) 까지의 누적 합 사실 이 문제는 DP 문제(?) 라고 봐도 무방할 것 같다. 특정 좌표 (i, j) 까지의 누적 합을 구한 다음 필요한 영역만 잘라서 출력하면 해결할 수 있다. 시간복잡도는 O(N^2 + M) 으로, 약 100만 정도이기 때문에 1초 안에 해결할 수 있..
-
[백준 11659] 구간 합 구하기 4 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 15:10
www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에 www.acmicpc.net 문제풀이 N, M : 입력값 arr : 입력 배열 sum_value : 누적 합 prefix_sum : 누적 합의 값들을 저장할 리스트 N 과 M 제한이 100,000이기에 O(NM)으로는 해결할 수 없다. 구간 합을 효율적으로 구하기 위한 누적 합(Prefix Sum)을 통해 O(N+M)으로 효율적으로 해결할 수 있다. 1. sum_value에 배열의 원소..
-
[백준 3020] 개똥벌레 (Python)Algorithm & Problem Solving/구간 합(Prefix Sum) 2020. 12. 27. 15:01
www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제풀이 N, H : 입력값(가로, 세로) top : 종유석 bottom : 석순 N 제한이 200,000 H 제한이 500,000 으로 단순하게 일일이 비교하는 O(NH) 방식으로는 절대 해결할 수 없다. (20만 * 50만 = 1000억 => 1초안에 불가능) 조금 더 효율적인 방식으로 해결해야 하는데, 종유석과 석순을 구분지어서 생각해 볼 수 있다. 종유석만 보았을 때, 그림에서 높이가 작아질수록(H => 0..
-
[백준 7795] 먹을 것인가 먹힐 것인가 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 27. 00:32
www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제풀이 N, M : 배열 A, B의 크기 A, B : 입력 배열 A_idx, B_idx : 투 포인터 count : A의 원소가 B의 원소보다 큰 경우의 갯수를 메모라이제이션 ans : 결과값 tmp : A_idx 번째의 A 원소에서, 현재 B_idx 부터 A[A_idx] > B[B_idx] 를 만족하는 B_idx 의 갯수 N, M 조건이 20000 밖에 되..
-
[백준 3273] 두 수의 합 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 26. 23:19
www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제풀이 N, arr, X : 입력값 투 포인터(left, right)를 이용하여 해결할 수 있다. 1. 배열(arr)을 입력받고 정렬을 해준다. - 정렬을 하지 않으면 투 포인터를 정상적으로 사용할 수 없다. 2. left, right 를 이용하여 arr[left]와 arr[right]를 더해준다. (이 값을 tmp 변수에 저장) - tmp가 X보다 작을..
-
[백준 2018] 수들의 합 5 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 26. 18:34
www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제풀이 N : 입력값 arr : 배열(1부터 N) start, end : 투 포인터를 위한 포인터 now : 현재까지 더한 값 투 포인터(start, end)를 이용하여 해결할 수 있다. 1. N을 입력하고 배열(arr)에 1부터 N까지의 값을 넣어준다. 2. end와 now를 이용하여 now가 N이상이 될 때 까지 now에 arr[end]를 더하고 end를 1 증가시키는 과정을 반복한다..
-
[백준 2230] 수 고르기 (Python)Algorithm & Problem Solving/투 포인터(Two Pointer) 2020. 12. 26. 18:15
www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 문제풀이 N, M : 입력값 arr : 입력 배열 투 포인터(left, right)를 이용하여 해결할 수 있다. 1. 배열(arr)을 입력받고 정렬을 해준다. - 정렬을 하지 않으면 투 포인터를 정상적으로 사용할 수 없다. 2. left, right 를 이용하여 arr[right] 에서 arr[left]를 뺀다(이 값을 tmp 변수에 저장). - tmp가 M보다 작을 경우는 두..