📙[Algo] 24.01.18 투포인터 / 알고리즘 / SQL

투포인터 이론 정리

주로 아래 두 가지 상황에서 많이 쓰인다.

 

1️⃣ 특정 조건을 만족하는 두 수

💡 다음과 같이 이해하기
[s, e] ⇒ 정답 후보의 범위
s의 입장 : 나는 정답 후보 중 제일 큰 값과 더했다.
e의 입장 : 나는 정답 후보 중 제일 작은 값과 더했다.

💭 풀이 로직
s = 0, e= n - 1에서 출발
s, e가 만날 때까지
s, e중 정답 후보에서 빠져야 하는 게 있다면 그걸 지운다.

 

2️⃣ 특정 조건을 만족하는 구간

💭 풀이 로직
s = 0, e = 0에서 출발(0번만 들어있는 구간을 생성해서 시작)
e < n : 정상적인 구간이라면 반복
구간을 늘려야 한다면 e++, 구간을 줄여야 한다면 s++

 

3️⃣ 정렬된 두 배열을 합칠 때(드문 케이스, 머지 소트)

 

1️⃣ 특정 조건을 만족하는 두 수 ⇒ 합이 X인 두 수 : O(n)

문제. BOJ 3273 두 수의 합

문제 요약 : 수 두 개를 골라서 합했을 때 특정 숫자가 몇 개 등장하는지 카운트 하는 문제

찾고자 합는 합 : 13

 

1) 먼저 sort를 해준다.

 

2) s → 1, e → 14

arr[s] + arr[e] = 15 > 13

⇒ 제일 작은 거랑 더했는데도 답보다 크다.

⇒ 즉, e입장에서 다른 후보랑 더해도 절대 답이 될 수 없다!!

⇒ 합을 줄이기 위해 e를 이동 → 이렇게 이해 X

 

3) s → 1, e → 12 (o)

arr[s] + arr[e] = 13 == 13

⇒ 14는 이제 범위 밖이므로 없다고 생각

⇒ 답을 찾았으므로 카운트 증가

 

4) s → 2, e → 12

arr[s] + arr[e] = 14 > 13

⇒ 12(e)도 다른 어떤 후보랑 더해도 13이 될 수 없다.

 

5) s → 2, e → 11 (o)

arr[s] + arr[e] = 13 == 13

⇒ 답을 찾았으므로 카운트 증가

⇒ 주어진 수가 서로 다른 수라는 전제 하에, 여기서 2는 11제외 다른 어떠한 수와 더해도 13이 될 수 없음.

⇒ 즉, s도 옮기고 e도 옮기게 된다.

 

6) s → 3, e → 12

 

arr[s] + arr[e] = 12 < 13

⇒ 13보다 작음

⇒ 즉, s입장에서 다른 어느 누구와 더해도 답이 될 수 없으므로 s를 한 칸 이동(합을 키우기 위해라고 이해하지 말기!!)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args)  {

        int target = 13;
        int[] arr = {1, 2, 3, 5, 7, 9, 11, 12, 14};

        int s = 0;
        int e = arr.length - 1;
        int cnt = 0;

        while (s < e) {
            if (arr[s] + arr[e] == target) {
                // target인 지점을 찾았다면, s기준 e사이에 있는 후보들에 어떤 걸 더해도 target보다 작음
                // e기준에서도 s사이에 있는 후보들에 어떤 걸 더해도 target보다 큼
                // 왜냐면 조건이 서로다른 수들로만 이루어진 수열이니까!
                // 그래서 s++, e--
                cnt++;
                s++;
                e--;
            } else if (arr[s] + arr[e] < target) {
                // s입장에서 가장 큰 e랑 더했는데 작은 상황이니까 s가 뒤로 가야함
                s++;
            } else {
                // e입장에서 가장 작은 s랑 더했는데 큰 상황이니까 e가 앞으로 가야함
                e--;
            }
        }
    }
}

 

문제. BOJ 20366 같이 눈사람 만들래?

문제 요약 : 눈덩이 크기가 주어졌을 때, 2명의 사람이 각자 두 개의 눈덩이를 골라 눈사람을 만들었을 때, 둘의 눈사람 크기 차이가 최소가 되도록 하기.

a, b, c, d ⇒ (a+b)와 (c+d)의 차이가 최소가 되게 하기

일단 완전탐색으로 접근하고 생각하자!

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args)  {

        int n = 5;
        int[] arr = {3, 5, 2, 5, 9};
        int answer = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    for (int l = 0; l < n; l++) {

                        if (i == j || i == k || i == l || j == k || j == l || k == l) {
                            continue;
                        }

                        answer = Math.min(answer, Math.abs(arr[i] + arr[j] - arr[k] + arr[l]));
                    }
                }
            }
        }

        System.out.println(answer);

    }
}

 

그러나 n의 범위가 600까지 가능하므로, n^4연산이 불가능하다. (n^3은 가능)

투포인터는 n하나 줄일 때 많이 사용한다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args)  {

        int n = 5;
        int[] arr = {3, 5, 2, 5, 9};
        int answer = Integer.MAX_VALUE;

        Arrays.sort(arr);

        int s, e;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                /*
                   여기까지 내 눈덩이의 총 크기를 결정할 수 있다.
                   arr[i] + arr[j]
                */

                /*
                   그 다음은 내 눈사람과 최대한 비슷한 눈사람을 만들어야 함
                   두 개가 결정되면 나머지 두개를 n으로 처리할 수 있을까?
                   => 투포인터로 처리
                */
                s = 0;
                e = n - 1;
                while (s < e) {

                    if (s == i || s == j) {
                        s++;
                        continue;
                    }

                    if (e == i || e == j) {
                        e--;
                        continue;
                    }

                    answer = Math.min(answer, Math.abs(arr[i] + arr[j] - (arr[s] + arr[e])));

                    if (arr[s] + arr[e] > arr[i] + arr[j]) {
                        /* 
                            이미 e입장에서 가장 작은 애랑 더했는데고 크니까
                            다른 후보랑 더할 의미가 사라짐
                        */
                        e--;
                    } else {
                        s++;
                    }
                }
            }
        }

        System.out.println(answer);

    }
}

 

중복이 가능한 경우? ⇒ 생각해보기

 

2️⃣ 특정 조건을 만족하는 구간(연속 부분 수열) : O(n)

문제. BOJ 2003 수들의 합2

문제 요약 : 수열에서 연속으로 고른 부분 수열 중에서 부분 수열의 합이 특정 숫자가 되는 경우 찾기

일단 완전탐색으로 접근하고 생각하자! ⇒ 2중 포문

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n  = Integer.parseInt(st.nextToken());
        int target  = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] nums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int cnt = 0;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total = 0;
            for (int j = i; j < n; j++) {
                total += nums[j];

                if(total == target) cnt++;

                // 여기서 수열의 모든 원소가 양수이기 때문에 target보다 커질 경우 바로 break걸어도 된다.
                if(total > target) break;
            }
        }

        System.out.println(cnt);
    }
}

 

여기서 투포인터를 적용해보기!

1)

수열의 target을 넘어버리므로 break

2)

 

기존 방식의 경우 i가 1증가하고, j가 i위치로 이동한다.

하지만 이미 1번에서 j가 3위치까지 간 것은 이전 구간은 target이 되기에 부족한 구간이기 때문에, j를 i위치로 가져올 필요가 없다.

그렇기 때문에 넘치는 구간이 발생하면 i만 뒤로가고 j는 그대로 둔다.

즉, 부족하면 j가 뒤로가고, 넘치면 i가 뒤로간다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n  = Integer.parseInt(st.nextToken());
        int target  = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] nums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int s = 0, e = 0, total = nums[0], cnt = 0;
        while (e < n) {
            if (total < target) {
                e++;
                total += nums[e];
            } else if (total > target) {
                total -= nums[s];
                s++;
            } else {
                cnt++;
                total -= nums[s];
                s++;
                e++;
                total += nums[e];
            }
        }

        System.out.println(cnt);
    }
}

 

알고리즘 문제) BOJ2467. 용액 

2467번: 용액

문제 요약

• 산성 용액 특성값 : 1 ~ 10억
• 알칼리성 용액 특성값 : -1 ~ -10억
• 용액의 특성값이 정렬된 상태로 주어질 떄, 두 용액을 혼합해서 특성값이 0에 가장 가까운 용액 찾기

시간 제한

• 1초

입력

• 전체 용액의 수 N (2≤N≤10만)
• 용액의 특성값을 나타내는 정수가 오름차순으로 입력
  • 값들은 서로 다 다르다

출력

• 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력
  • 오름차순으로 출력
  • 여러 개일 경우 아무거나 출력 

접근법

먼저 완전탐색부터 생각하기

2중 for문을 돌려서 두 개씩 선택하고 그 합이 가장 0에 가까운 애들을 찾아서 기록
⇒ 10만 * 10만으로 시간 초과 뜸

 

최적화 하기

-99입장에서 98을 더한게 가장 큰 값이 되고, -2를 더한게 가장 작은 값이 된다.
1) s→-99, e→98로 시작

• 특성값 -1이니까 일단 value 변수에 기록(value=-1)
• 이때 s기준 e앞에 있는 어떤 숫자와 더해도 -1보다 작아지니까 답 후보에서 제외 되므로, s+=1 한다.

2) s→-2, e→98

• 특성값 : 97
• value와 비교 : abs(97) > abs(-1)
• 이때, e기준 s뒤에 있는 어떤 숫자와 더해도 97보다 커지니까 답 후보에서 제외되므로, e-=1 한다.

3) s→-2, e→4

• 특성값 : 2
• value와 비교 : abs(2) > abs(-1)
• 이때, e기준 s뒤에 있는 어떤 숫자와 더해도 2보다 커지니까 후보에서 제외되므로, e-=1 한다.

4) s→-2, e→-1

• 특성값 : -3
• value와 비교 : abs(-3) > abs(-1)
• 이때, s기준 e앞에 있는 어떤 숫자와 더해도 -3보다 작아지니까 답 후보에서 제외 되므로 s+=1 한다.

5) s→-1, e→-1 ⇒ 같은 용액을 가리키므로 종료

 

정리

• 특성값이 음수일 때
  • s기준 e앞에 있는 어떤 숫자와 더해도 현재 특성값보다 더 작아지니까 s+=1
    • abs(value) < abs(특성값) : s+=1
    • abs(value) > abs(특성값) : value 갱신, s+=1
    • abs(value) == abs(특성값) : s+=1
• 특성값이 양수일 때
  • e기준 s뒤에 있는 어떤 숫자와 더해도 현재 특성값보다 더 커지니까 e-=1
    • abs(value) < abs(특성값) : e-=1
    • abs(value) > abs(특성값) : value 갱신, e-=1
    • abs(value) == abs(특성값) : e-=1
• 특성값이 0일 때, 0에 가장 가까운 특성값이므로 종료. 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] values = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            values[i] = Integer.parseInt(st.nextToken());
        }

        int s = 0, e = n-1, sum = 0, minDiff = values[s] + values[e];
        int[] ans = {values[s], values[e]};
        while (s < e) {
            sum = values[s] + values[e];

            if (Math.abs(sum) < Math.abs(minDiff)) {
                minDiff = sum;
                ans[0] = values[s];
                ans[1] = values[e];
                if (sum == 0) break;
            }

            if(sum < 0) s++;
            else e--;
        }

        System.out.println(ans[0] + " " + ans[1]);
    }
}

 

SQL ) Lv2. 재구매가 일어난 상품과 회원 리스트 구하기 

문제 요약

• 동일한 회원이 동일한 제품을 재구매한 데이터를 조회하는 문제
  ⇒ GROUP BY를 제대로 이해해야 생각해낼 수 있는 문제

알게 된 점

GROUP BY

• GROUP BY는 같은 값을 가진 행을 하나로 뭉쳐줌
• 예시) 연도별 월별 티켓 평균 금액
  ⇒ 먼저 연도로 그룹화하고, 연도별로 그룹 지어진 데이터를 월별로 데이터를 한 번더 그룹
• 예시) 일별 방문 고객수가 3명보다 적은일별 티켓 평균 금액
  ⇒ HAVING절을 이용해서 조건을 추가할 수 있다. 즉, 일별로 그룹 지어진 데이터 개수가 3개보다 많을 경우라는 조건 추가.
• 예시) 일별 방문 고객수가 3명보다 많으면서, 머무른 시간이 5분보다 긴 경우의 일별 평균 금액
  ⇒ WHERE 절로 머무른 시간 조건을 추가할 수 있다. 여기서 HAVING과의 차이점은 그룹화 되기전 미리 단일행들을 필터링 한다. 

출처 

GROUP BY (上) : 개념과 실제 사용 방법

-- 코드를 입력하세요
SELECT USER_ID, PRODUCT_ID FROM ONLINE_SALE 
GROUP BY USER_ID, PRODUCT_ID
HAVING COUNT(*)>=2
ORDER BY USER_ID ASC, PRODUCT_ID DESC;