Jonyo Programming

[BOJ 2143(G3)리뷰] 투 포인터를 응용해야 하는 문제이다. 문제에서 배열이 두개가 주어지고, 두개의 배열을 이용하여 만들 수 있는 합 중 T를 만족하는 경우의 수를 찾아야 한다. 완전탐색하는 방법으로는 시간초과를 맞게 되므로 투포인터 알고리즘을 이용해야 한다. 투 포인터 알고리즘을 이용하기 위하여 A와 B배열에 대해 각각의 구간합을 저장하는 사전작업을 했다. 즉, 1,3,2,1 배열이라면 1 4 6 7 3 5 6 2 3 1 라는 별도의 배열을 만든다. 그리고 이렇게 만들어진 두개의 배열을 각각 오름차순으로 정렬 한 후에 하나의 배열은 시작부터, 하나의 배열을 끝부터 시작한다. 이미 이 배열에 구간의 합에 대한 경우의 수가 들어 있으니 이 두개의 배열의 합이 T를 만족하는 개수를 찾으면 된다. 다..

[BOJ 14921(G5)리뷰] 투 포인터 문제다. 투 포인터 개념을 안다면 어렵지 않게 풀 수 있다. 구간합을 구하는 일반적인 투포인터와 달리, 두 수를 더하여 0에 가장 가까운 수를 찾아야하는 문제이다. 오름차순으로 정렬된 상태에서 시작과 끝을 포인터로 가리키고 시작해야 한다. 예를들어 다음과 같은 INPUT이 있다고 하자. arr[5] = {-101 -3 -1 5 93} st는 0을 ed는 4를 가리킨 상태에서 시작한다. 처음엔 arr[st]+arr[ed] = -8 이라는 값이 나온다. 이 때 어느 포인터를 움직여야 할까? 만약 ed포인터를 1만큼 감소시킨다면 -96이라는 값이 나온다. 배열이 정렬되어 있으므로 ed를 감소시킬 수록 더 작은 값이 나오게 되므로 점점 0에서 멀어지게 될것이다. 그러므..

[BOJ 1644(G3)리뷰] 지난 문제에 이어서 푼 투 포인터 문제이다. 이 문제는 N이 최대 400만 이므로 완전탐색을 통해 풀면 시간초과가 나게 된다. 또한 소수를 판별하는 알고리즘 역시 일반적인 방법이 아닌 속도를 개선한 알고리즘을 사용해야 한다. 나는 '에라토스테네스의 체' 알고리즘을 이용하여 N까지의 소수를 선별하여 arr벡터에 담는 작업을 했다. 그 후에는 N까지의 소수가 담긴 arr벡터를 이용하여 두개의 포인터로 부분합을 만족하는 경우를 찾으면 된다. 1과 2에대한 예외처리를 하고나서 정답처리가 나왔다. /* 21.01.04 BOJ : 1644 부분합 (https://www.acmicpc.net/problem/1644) 투 포인터 */ #include using namespace std; ..

[BOJ 1806(G4) 리뷰] 오늘 투 포인터를 공부하고 푼 문제다. 투 포인터는 배열 내에서 부분의 합을 구할때 아주 유용하게 쓰이는 알고리즘이다. 배운 개념을 그대로 적용했더니 G4문제치곤 간단하게 풀렸다. 다만 투 포인터를 응용한 문제를 풀려했더니 생각보다 어려웠다. 더 공부해야겠다. /* 21.01.04 BOJ : 1806 부분합 (https://www.acmicpc.net/problem/1806) 구현 */ #include using namespace std; int arr[100001]; int main() { cin.tie(0); ios::sync_with_stdio(0); int N, S; cin >> N >> S; for (int i = 0; i > arr..