(두 위치의 거리 * 두 위치의 원소 중 최솟값)의 최댓값을 투포인터로 찾는 방법

22945번: 팀 빌딩  n명이 한줄로 서있을 때 2명을 골라 그 2명 사이의 사람 수 * min(첫번째 사람의 능력치, 두번째 사람의 능력치)의 최댓값을 찾는 문제 [1,4,2,5]이면 A[1] = 4, A[3] = 5이고 두 사람 사이에는 1명 있고 둘 중 최솟값은 4니까 4가 최댓값이다 투 포인터로 해결할 수 있다해서 연습삼아 풀어볼려했는데 기존에 알던 투 포인터 풀이는 안먹히니 답이 없다 인덱스랑 같이 넣어서 정렬해야하나 일단 정렬이 안되어있고 포인터 움직여도... min값이 커졌다 작아졌다 하는데 근데 0번과 n-1번에 포인터를 두고 서로 간격을 좁혀가면 된다는데 그래도 어떻게 해야하는지 고민되더라고 A[i], A[i+1], A[i+2], A[i+3], ...., A[j] i번과 j번을 가리키고..

• format_list_bulleted 알고리즘/투 포인터 알고리즘
• · 2025. 1. 7.
• textsms

절댓값을 풀어내는 필수 테크닉 - 모든 i,j에 대해 (i-j)|ai-bj|의 합을 빠르게 구하는 방법

28867번: Портальная пушка 최대 100000개의 원소를 가지는 배열 A,B에 대하여 $\sum_{i,j}^{}(i-j)|a_{i} - b_{j}|$를 구하는 문제 당연히 $O(N^{2})$은 안될거고 O(N)에는 풀어야하는데 $a_{i} >= b_{j}$이고 $a_{i}  따라서 $(i-j)|a_{i}-b_{j}| = i(a_{i}-b_{j})-j(a_{i}-b_{j})+i(b_{j}-a_{i})-j(b_{j}-a_{i})$ 그래서 ai>=bj인 경우 i(ai-bj)와 j(ai-bj), ai  여기서 핵심은 앞에 붙은 i,j인데 얘를 고정시킨다면 투포인터를 활용해서 O(N)에 계산할 수 있다. 예를 들어 i = 0인 경우 j = 0,1,2,...증가시켜서 ai >= bj인 경우의 j를 ..

• format_list_bulleted 알고리즘/투 포인터 알고리즘
• · 2024. 10. 24.
• textsms

배열에서 두 수의 합이 s가 되는 경우의 수(서로 다른 방향으로 움직이는 투 포인터)

29940번: Sum (acmicpc.net) 배열이 서로 다른 원소들로 이루어져있고 정렬되어 있을때, 여기서 고른 서로 다른 두 수의 합이 s가 되는 경우의 수를 구하는 문제 투 포인터로 어떻게 해결할 수 있을까 보통 투 포인터하면 i = 0, j = 0으로 같은 방향에서 시작해서 j를 1씩 계속 증가시키다가, 특정 조건에서 멈추고 다시 i를 1 증가시키고 다시 j를 계속 증가시키고... 같은 방향으로 움직이지만 두 수 A[i] + A[j] = s가 될려면 i = 0으로 고정되어 있을 때 A[j] = s - A[0]로 확정적으로 구할 수 있다. 그러면 배열 A가 서로 다른 수로 이루어져 있고 정렬되어 있으므로  모든 i = 0,1,2,..,n-1는 작은 수부터 시작하므로 반대편 A[j] = s - A[..

• format_list_bulleted 알고리즘/투 포인터 알고리즘
• · 2024. 9. 2.
• textsms

겹치는 직선 구간쌍의 개수 빠르게 세기

D - Intersecting Intervals (atcoder.jp) D - Intersecting IntervalsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  50만개의 구간 [l,r]이 주어질때, 이들 중 서로 겹치는 구간 쌍의 개수가 몇개인지 구하는 문제 모든 구간 쌍에 대해 서로 겹치는지 조사할려면 $O(N^{2})$인데, 당연히 N이 최대 50만이므로 시간제한에 맞지 않는다 전체 구간 쌍의 개수는 n개중 2개를 선택하는 경우의 수이므로, nC2 = n(n-1)/2 만약 서로 겹치치 않는 구간 쌍의 개수를 구..

• format_list_bulleted 알고리즘/투 포인터 알고리즘
• · 2024. 8. 2.
• textsms

투 포인터로 원소를 삭제하면서 가장 긴 수열을 찾을 수 있을까?

1. 문제 22862번: 가장 긴 짝수 연속한 부분 수열 (large) (acmicpc.net) 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 2. 풀이 투 포인터로는 원소를 포함시키면서 가장 긴 수열을 찾아가는 건데 어떻게 해야 최대 K번 원소를 삭제하면서 가장 긴 짝수만 포함된 연속 부분 수열을 찾을 수 있을까? 생각보다 간단하다 투 포인터 i,j로 범위를 확장해나가는데, j번 원소가 홀수라면, K값을 감소시키고 길이를 증가시키지 않는다. K가 홀수를 포함시킬 수 있는 최대 기회라고 생각한다면, 원소를 실제로 삭제하지 않고도 마치 삭제한..

• format_list_bulleted 알고리즘/투 포인터 알고리즘
• · 2023. 6. 8.
• textsms

투 포인터 올바르게 생각하기 기본문제로 연습2

1. 문제 2018번: 수들의 합 5 (acmicpc.net) 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 2. 풀이 이전에 풀이한 방식대로, 포인터 i,j를 잡고 구간 [i,j]의 합이 N이 되는지 아닌지를 검사하면 된다 자연수 N이 연속된 자연수의 합으로 나타낼려면 결국 N보다 작거나 같은 자연수의 합으로 나타낼 수밖에 없다 그러므로 1부터 n까지 natural이라는 배열을 만들었고 (정렬은 왜 한건지 모르겠지만..) 포인터 i,j를 잡은 다음, 초기값 natural[0]로 잡는다..

• format_list_bulleted 알고리즘/투 포인터 알고리즘
• · 2023. 4. 12.
• textsms