문제 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의 임의의 부 배열 두 개의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구해야 한다. 먼저 A와 B의 원소를 저장할 배열인 arrA와 arrB를 만든다. 그 다음, A와 B의 모든 부 배열의 각 원소의 합을 저장할 리스트인 sumA와 sumB를 만든다. 모든 부 배열의 각 원소의 합을 저장 한..
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 설명 다음 줄로 내려갈 때에는 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다. DP만 사용해 문제를 풀면 모든 숫자를 배열로 담고 활용해야 하므로 메모리 제약에 걸린다. 따라서, 슬라이딩 윈도우 알고리즘을 같이 사용하면 dp 배열을 계속해서 초기화하면서 문제를 풀 수 있다. 먼저 처음에 maxDP와 minDP를 첫 줄의 숫자들로 초기화한다. 다음 줄부터 들어갈 m..
투 포인터 리스트에서 원하는 값을 얻기 위해 두 개의 포인터를 이용해 각 위치를 기록하면서 처리하는 알고리즘이다. 반복문을 사용해 리스트를 단순 탐색하는 것보다 투 포인터를 사용하면 시간 복잡도를 낮출 수 있다. 리스트의 크기가 N일 때, Worst Case일 경우 시간복잡도를 알아보자. 전자의 경우에는 반복문을 N번씩 두번 돌려서 시간복잡도는 \(O(N \times N) = O(N^2)\) 이 된다. 후자의 경우에는 두 포인터가 모두 N번 탐색하여 시간복잡도는 \(O(2N) = O(N)\) 이 된다. 투 포인터는 위의 그림처럼 두 가지 방식으로 쓰인다. 앞에서부터 시작하는 포인터와 끝에서부터 시작하는 포인터가 중간에서 만나는 방식 둘 다 앞에서 시작해서 하나의 포인터가 다른 포인터보다 앞서면서 끝에 도..
문제 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 설명 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구해야 한다. 일일이 부분합을 구해서 문제를 풀기 보다 시간복잡도를 줄이기 위해 투 포인터를 사용해 구한다. 두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다. 현재 sum이 M보다 크거나 ..
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 설명 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구해야 한다. 일일이 부분합을 다 구해서 문제를 풀면 시간복잡도가 크게 나오기 때문에 투 포인터를 사용해 구한다. 두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다. 현재 합이 S보다 작으면 현재 end가 가리키는 값을 더하고 end를 하나 전진시킨다..
문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 설명 이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 형택이의 승률이 절대 변하지 않는다면 -1을 출력한다. 만약 현재 승률이 99% 또는 100%라면 승률이 절대 변할 수 없으므로 -1을 출력한다. 현재 게임을 X번 했으므로 start를 1, end를 X로 하고 이분 탐색을 진행한다. start와 end가 역전되기 전까지 mid를 계속해서 구해서 getPercent 함수를 이용해..
이분 탐색이란 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 원하는 데이터를 탐색하는 방법이다. 리스트의 중간 부분에 찾는 데이터가 있는지 확인하고, 없으면 왼쪽에 있는지 오른쪽에 있는지 판단한다. 이분 탐색은 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. 이분 탐색의 시간복잡도 원하는 데이터를 찾을 때까지 처음부터 끝까지 계속 탐색하는 순차 탐색은 Worst Case일 때 \(O(N)\) 이라는 시간복잡도를 가지므로 10만개의 데이터가 있을 때 10만번을 탐색해야 한다. 그러나, 이분 탐색은 탐색 대상을 절반씩 계속해서 줄여나가기 때문에 Worst Case일 때에도 탐색의 횟수가 \( log_{2} N \)이 되어 \(O(log N)\) 의 시간복잡도를 가지므로 10만개의 데이터가 ..
