📙[Algo] 24.01.31 알고리즘

알고리즘 문제) BOJ 17611. 직각다각형

17611번: 직각다각형

문제 요약

• 직각 다각형 : 각 변이 x,y축에 평행한 다각형
• 단순 다각형 : 다각형의 두 선분이 연속하는 선분의 꼭짓접을 제외하고는 만나지 않음
• 단순 직각 다각형위에 수평선 H, 수직선 V와 몇번 교차하는지 알려고함
• 단순 직각 다각형과 가장 많이 교차하는 수평선 H와 수직선 V의 위치를 찾고 교차 횟수 구할 것 ⇒ max(h, v)
• 단 수평선, 수직선은 다각형의 선분과 겹치면 안 됨

시간 제한

• 1초

입력

• 단순직각다각형의 꼭지점 개수 n
  • 4 ≤ n ≤ 10만
• 꼭지점 좌표 xi, yi (정수)
  • -50만 ≤ xi, yi ≤ 50만
  • 시계 방향으로 주어진다.

출력

• max(h,v) 출력

접근법

• 읽다보니 뭔가 개똥벌레 문제와 유사하다고 생각함…!?
• imos 알고리즘 사용
• 좌표를 입력 받을 때,
• x축, y축 각각 의 경우 숫자가 벌어지는 구간을 표시한다. 시작 구간 +1, 그리고 끝나는 구간에 -1 표시
  • 만약 숫자가 감소되는 부분이라면 처음 주어지는 구간에 -1, 그 다음수에 +1 표시
• 추가로 끝나는 점과 시작 점도 이어주는 작업 필요
• 그 다음 구간합 배열 만들기
• 음수부분은 인덱스 표시가 애매해서 다른 사람 방법 참고 ⇒ 그냥 기존 인덱스에 +500000한다 생각

코드

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


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

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

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

        int[] prefixX = new int[1000010];
        for (int i = 1; i < n; i++) {
            if (arr[i - 1][0] < arr[i][0]) {
                prefixX[arr[i - 1][0]] += 1;
                prefixX[arr[i][0]] += -1;
            } else if (arr[i - 1][0] > arr[i][0]) {
                prefixX[arr[i - 1][0]] += -1;
                prefixX[arr[i][0]] += 1;
            }
        }
        // 첫번쨰랑 마지막 꼭짓점 연결하는 부분 추가!
        if (arr[0][0] < arr[n - 1][0]) {
            prefixX[arr[0][0]] += 1;
            prefixX[arr[n - 1][0]] += -1;
        } else if (arr[0][0] > arr[n - 1][0]) {
            prefixX[arr[0][0]] += -1;
            prefixX[arr[n - 1][0]] += 1;
        }

        int[] prefixY = new int[1000010];
        for (int i = 1; i < n; i++) {
            if (arr[i - 1][1] < arr[i][1]) {
                prefixY[arr[i - 1][1]] += 1;
                prefixY[arr[i][1]] += -1;
            } else if (arr[i - 1][1] > arr[i][1]) {
                prefixY[arr[i - 1][1]] += -1;
                prefixY[arr[i][1]] += 1;
            }
        }
        // 첫번쨰랑 마지막 꼭짓점 연결하는 부분 추가!
        if (arr[0][1] < arr[n - 1][1]) {
            prefixY[arr[0][1]] += 1;
            prefixY[arr[n - 1][1]] += -1;
        } else if (arr[0][1] > arr[n - 1][1]) {
            prefixY[arr[0][1]] += -1;
            prefixY[arr[n - 1][1]] += 1;
        }

        int xMax = 0;
        for (int i = 1; i < 1000010; i++) {
            prefixX[i] += prefixX[i - 1];
            if(xMax < prefixX[i]) xMax = prefixX[i];
        }

        int yMax = 0;
        for (int i = 1; i < 1000010; i++) {
            prefixY[i] += prefixY[i - 1];
            if(yMax < prefixY[i]) yMax = prefixY[i];
        }

        bw.write(String.valueOf(Math.max(xMax, yMax)));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 253332. 수들의 합 8

25332번: 수들의 합 8

문제 요약

• A = {A1, … , An}
• B = {B1, …, Bn}
• Ai + … + Aj = Bi + … + Bj 를 만족하는 (i,j)쌍 개수 구하기

시간 제한

• 1초

입력

• N
  • 1~ 20만
• A 수열을 나타내는 N개의 양의 정수
• B 수열을 나타내는 N개의 양의 정수
  • 정수는 1~10000

출력

• 만족하는 (i,j) 쌍의 개수 출력

접근법

• 2중 for문 사용하면 시간초과가 뜬다.
• 어떻게 구간합에서 부분 수열의 합을 비교할 수 있을까?

1 3 4

1 2 3

• i → 1
  • j → A,B 둘다 i 포함 이후로 같은 숫자가 얼마나 있는지 셀 것
• i → 2
  • A[1] == B[1] == 1 이므로,
  • j → A,B 둘다 i 포함 이후로 같은 숫자가 얼마나 있는지 셀 것
• i → 3
  • A[2] = 3, B[2] =2 이므로,
  • j → A,B 둘다 i 포함 A = B + (A-B) 인 구간 찾기 …

이거를 매 케이스마다 하면 2중 for문으로 시간초과 되니까,,

역으로 생각해보면,

j를 먼저기준으로 생각했을 때

• j → 1
  • A[1] == B[1] == 1이므로,
  • i → A,B 둘다 i이전에 같은 숫자가 얼마나 있는지 셀 것
• j → 2
  • A[2] = 3, B[2] = 2
  • i → A,B 둘다 i이전에 A = B + (A-B)인 구간이 얼마나 있는 지 찾기
• j → 3
  • A[3] = 4, B[3] = 3
  • i → A,B 둘다 i이전에 A = B + (A-B)인 구간 얼마나 있는 지 찾기

즉, j로 수열을 하나씩 훑으면서

map에 A-B값이 몇 개 존재하는지 확인한다.

그러면서 현재 map에다 <차이값, 카운트>를 저장한다.

코드

import java.io.*;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;


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

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

        int[] prefixA = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            prefixA[i] = prefixA[i - 1] + Integer.parseInt(st.nextToken());
        }

        int[] prefixB = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            prefixB[i] = prefixB[i - 1] + Integer.parseInt(st.nextToken());
        }

        Map<Long, Long> diffMap = new TreeMap<>(); // <A-B 차이값, 개수>
        diffMap.put(0L, 1L);
        long answer = 0;

        long diff;
        for (int j = 1; j <= N; j++) {
            diff = prefixA[j] - prefixB[j];
            if (diffMap.containsKey(diff)) {
                answer += diffMap.get(diff);
                diffMap.replace(diff, diffMap.get(diff) + 1);
            } else {
                diffMap.put(diff, 1L);
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 14476. 최대공약수 하나 빼기

14476번: 최대공약수 하나 빼기

문제 요약

• 정수 A가 B로 나누어떨이지면, B는 A의 약수이며 A는 B의 배수
• 최대공약수란 공통 약수 중 가장 큰 수
• N개의 정수 중 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것 찾기
  • 이때 최대 공약수가 K의 약수면 안 됨

시간 제한

• 2초

입력

• 정수의 개수 N
  • 4 ≤ N ≤ 100만
• N개의 수가 주어짐
  • 20억을 넘지 않는 자연수

출력

• 정수 하나를 빼서 만들 수 있는 가장 큰 최대 공약수와 뺀 수를 공백을 두고 출력
• 없다면 -1

접근법

• 저번에도 prefix, suffix 배열 만들고, → ← 방향으로 하나씩 숫자 추가될 때마다 숫자들끼리 최대 공약수 배열 만들었던 거 같다!
• 그리고 K를 하나씩 뺐을 때 해당 위치 기준(idx), prefix[idx-1]과 suffix[idx+1]의 최대공약수를 구해준다.
• 그다음 해당 최대공약수가 K로 나누어 떨어지지 않는지 체크하고 정답갑을 최대값으로 갱신한다.

코드

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


public class Main {

    public static int getGcd(int a, int b) {
        // a > b
        int tmp;
        while (b != 0) {
            tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        int[] prefix = new int[N];
        prefix[0] = arr[0];
        for (int i = 1; i < N; i++) {
            prefix[i] = getGcd(Math.max(arr[i], prefix[i - 1]), Math.min(arr[i], prefix[i - 1]));
        }

        int[] suffix = new int[N];
        suffix[N - 1] = arr[N - 1];
        for (int i = N - 2; i >= 0; i--) {
            suffix[i] = getGcd(Math.max(arr[i], suffix[i + 1]), Math.min(arr[i], suffix[i + 1]));
        }


        int k, answer = -1, delK = -1, gcd;
        for (int i = 0; i < N; i++) {
            k = arr[i];

            if (0 <= i - 1 && i + 1 < N) {
                gcd = getGcd(Math.max(prefix[i - 1], suffix[i + 1])
                        ,Math.min(prefix[i - 1], suffix[i + 1]));
            } else if (i == 0) {
                gcd = suffix[i + 1];
            } else {
                gcd = prefix[i - 1];
            }

            if (k % gcd != 0) {
                if (answer < gcd) {
                    answer = gcd;
                    delK = k;
                }
            }
        }

        if (answer != -1) {
            bw.write(String.valueOf(answer + " " + delK));
        } else {
            bw.write(String.valueOf(answer));
        }

        bw.flush();
        bw.close();
        br.close();
    }
}