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

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에 대하여 ∑i,j(i−j)|ai−bj|를 구하는 문제 당연히 O(N2)은 안될거고 O(N)에는 풀어야하는데 ai>=bj이고 ai따라서(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

모든 순서쌍의 합의 나머지를 합해야하는데 매 항마다 나머지를 더하면 안되는 문제

C - Sigma Problem (atcoder.jp) C - Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  f(x,y) = x + y를 108로 나눈 나머지라고 정의 모든 i = 1,2,3,...,n-1, i  예를 들어 3 50000001 50000002이면... (3, 50000001), (3, 50000002), ( 50000001, 50000002)가 있고... 50000004, 50000005, (100000003 % 100000000 = 3)이 된다. 이들을 합하면 10000..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 6. 6.
  • textsms

코딩테스트 복기 - 구간합이 전부 똑같도록 3구간으로 나누는 방법(잘 모를때는 조건식을 써봐라)

1. 문제 구간 A를 1번부터 x번까지, 구간 B를 x+1번부터 y번까지, 구간 C를 y+1번부터 n번까지 나눈다. 각 구간의 모든 원소의 합을 각각 a,b,c라고 하자. a,b,c가 전부 같도록 x,y를 정하자. 여기서 1  그러한 방법의 수가 몇가지일까? n은 최대 50만 배열의 각 원소는 -100만부터 100만까지로 음수일수도 있다. 예를 들어 [1,2,3,0,3]이면.. A가 1번 2번 = 3 B가 3번 = 3 C가 4번 5번 = 3 --------------------------- A가 1번 2번  = 3 B가 3번 4번 = 3 C가 5번 = 3 2가지 있다.  2. 풀이 구간합이니까, prefix sum으로 누적합을 만들어야하는 것은 명확하다 [1,3,6,6,9] n = int(input())..

  • format_list_bulleted 누적 합 알고리즘
  • · 2024. 4. 27.
  • textsms

투 포인터 기억해야할 점 - 끝 포인터를 처음으로 옮기지 않기

1. 문제 14246번: K보다 큰 구간 (acmicpc.net) 14246번: K보다 큰 구간n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오.www.acmicpc.net 2. 풀이 첫번째 핵심두개의 포인터 i,j를 두고 i~j까지의 합이 k보다 작다면, 끝 포인터 j를 1칸 늘린다. 모든 수가 자연수이기 때문에 끝 포인터 j를 1칸 늘리면 구간 합이 증가하게 된다 ------------------------------------------------------------------------------------------------------------ 두번째 핵심반대로 i~j까지의 합이 k보다 크다면, 그 순간 j부터 ..

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