📙[Algo] 24.03.06 알고리즘

알고리즘 문제) BOJ 1940. 주몽

• 링크 : https://www.acmicpc.net/problem/1940

문제 요약

• 갑옷을 만드는 재료들은 각각 고유 번호를 갖고 있음
  • 두 개의 재료의 고유 번호를 합쳐서 M이 되면 갑옷이 만들어짐
• N개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지 구해라

시간 제한

• 2초

입력

• 재료 개수 N
  • 1≤N≤15000
• 갑옷을 만드는데 필요한 수 M
  • 1≤M≤1000만
• N개의 재료들의 고유 번호가 주어짐
  • 고유 번호 : 10만 이하 자연수

출력

• 갑옷을 만들 수 있는 개수

접근법

1. 완전 탐색으로 생각하기
   • 2중 for문으로 재료 두 개 선택해서 M이 되는 개수를 고른다
     • 어차피 다 다른 고유 번호가 주어지기 때문에 특정 숫자가 무언가와 더해서 M이 될 수 있는 경우는 단 한가지 뿐이다.
2. 투포인터 적용하기
   • 먼저 정렬 (M=9)
     1 2 3 4 5 7
     s             e
     • s→1, e→7
       • 8 < 9
       • s+=1
     • s→2, e→7
       • 9 == 9
       • cnt++
       • e-=1
     • s→2, e→5
       • 7 < 9
       • s+=1
     • s→3, e→5
       • 8 < 9
       • s+=1
     • s→4, e→5
       • 9 == 9
       • cnt++
       • e0-1
     • s→4, e→4
       • 같은 곳을 가리키므로 종료
   • 합계 < M : s+=1
   • 합계 == M : 카운트 증가, e-=1
   • 합계 > M : e-=1

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

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

        Arrays.sort(arr);

        int s = 0, e = N - 1, sum, answer = 0;
        while (s < e) {
            sum = arr[s] + arr[e];

            if (sum < M) {
                s++;
            } else {
                if(sum == M) answer++;
                e--;
            }
        }

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

 

알고리즘 문제) BOJ 9024. 두 수의 합

• 링크 : https://www.acmicpc.net/problem/9024

문제 요약

• 여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때
• S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 출력

시간 제한

• 1초

입력

• 테스트 케이스 개수 t
• 테스트 케이스별로 두 줄에 데이터가 주어짐
  • N K
    • 2≤N≤100만
    • -1억≤K≤1억
  • N개의 정수가 주어진다.
    • 각 정수의 최댓값은 1억, 최솟값은 -1억

출력

• 테스트 케이스별 결과 출력

접근법

N이 100만까지 가능하므로 2중 for문사용 X

⇒ 투포인터를 사용해서 N*N을 N으로 줄이기

1 3 5 7 (K=20)
s       e

• s→1, e→7
  • 8 < 20
  • 가까워지려면 더 늘려야 함
  • s+=1
• s→3, e→7
  • 10 < 20
  • s+=1
• s→5, e→7
  • 12 < 20
  • s+=1,
• s→ 7, e→ 7
  • break;
• 합계 < K : 가까워지려면 더 늘려야 하므로 s += 1
• 합계 ≥ K : 가까워지려면 더 줄여야 하므로 e -= 1
• 정답 갱신 할 때 주의 ⇒ 가장 가까운 조합의 개수를 구하는 거임
  • min변수 값과 같을 때 카운트 늘리고
  • 더 가까우면 카운트 다시 1로 min변수 갱신할 것
  • min 변수 : 차이값
• min변수 초기화 주의 ⇒ 배열원소에 음수가 들어올 수 도 있어서 min변수를 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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        StringBuilder sb = new StringBuilder();
        int N, K, s, e, sum, minSum, cnt;
        int[] arr;
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

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

            Arrays.sort(arr);

            s = 0;
            e = N - 1;
            **minSum = arr[s] + arr[e];**
            cnt = 0;
            while (s < e) {
                sum = arr[s] + arr[e];

                if (Math.abs(minSum - K) > Math.abs(sum - K)) {
                    minSum = sum;
                    cnt = 1;
                } else if (Math.abs(minSum - K) == Math.abs(sum - K)) {
                    cnt++;
                }

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

            sb.append( cnt+"\\n");
        }

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

 

알고리즘 문제) BOJ 2188. 두 개의 탑

• 링크 : https://www.acmicpc.net/problem/2118

문제 요약

• 1번부터 N번까지 지점이 존재하고, 차례로, 원형으로 연결되어 있음
• 지점들 중 두 곳에 탑을 세우려고 할 때 두 탑 사이의 거리가 최대가 되도록 할 것
  • 시계방향, 반시계방향 경로가 존재
    • 이 중 더 작은 값을 거리로 한다.

시간 제한

• 2초

입력

• 지점 개수 N
  • 2≤N≤5만
• N개의 줄에 차례로 두 지점 사이의 거리가 주어짐
  • 전체 거리 총 합은 10억

출력

• 답 출력

접근법

만약 5개의 지점이 존재하고, 거리가 다음과 같이 차례로 주어진다면

1 2 3 4 5

1~2 : 1

2~3 : 2

3~4 : 3

4~5 : 4

5~1 : 5

• arr

0

1

2

3

4

5

• prefix

0

1

3

6

10

15

1 (1) 2 (2) 3 (3) 4 (4) 5 (5) 1

만약 3, 5를 선택했다면 거리는 다음과 같이 구한다.

Math.min(prefix[2]+prefix[5]-prefix[4], prefix[4]-prefix[2])

• 정리하자면
  • 시계방향 : prefix[j-1]-prefix[i-1]
  • 반시계 방향 : 전체거리(prefix[N]) - 시계방향 거리
  Math.min(시계방향, 반시계방향)

완탐으로 접근하게되면 2중 for문을 사용해서 지점 2개를 선택하게되는데, N이 5만개까지 가능해서 사용하면 안 된다.

 

s=1,e=2로 시작할 것.

e가 늘어나면 시계방향거리가 커지고 반시계방향 거리가 작아진다.

• s→1, e→2
  • 시계 : 1
  • 반시계 : 14
  • 1 ⇒ 시계방향 거리 늘릴 것
    • e++
• s→1, e→3
  • 시계 : 3
  • 반시계 : 12
  • 3, e++
• s→1, e→4
  • 시계 : 6
  • 반시계 : 9
  • 6, e++
• s→1, e→5
  • 시계 : 10
  • 반시계 : 5
  • 5, 역전됨, s++ (반시계 방향 크기 늘려야함)
• s→2, e→5
  • 시계 : 9
  • 반시계 : 6
  • 6, s++
• s→3, e→5
  • 시계 : 7
  • 반시계 : 8
  • 7, e++ …
• 정리
  • 시계 ≤ 반시계 : e++
  • 시계 > 반시계 : s++

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

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

        int s = 1, e = 2, dist1, dist2;
        int answer = 0;
        while (e <= N) {
            // 시계 방향 거리
            dist1 = prefix[e - 1] - prefix[s - 1];

            // 반시계 방향 거리
            dist2 = prefix[N] - dist1;

            answer = Math.max(answer, Math.min(dist1, dist2));

            if(dist1 > dist2) s++;
            else e++;
        }

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

 

알고리즘 문제) BOJ 14921. 용액 합성하기

• 링크 : https://www.acmicpc.net/problem/14921

문제 요약

• 용액은 -1억~1억의 특성값을 갖는다.
• 두 용액을 합쳐 특성값이 0에 가까운 용액을 만들려고한다.
  • 이때의 특성값을 출력하시오

시간 제한

• 1초

입력

• N
  • 2≤N≤10만
• A0, .. AN
  • 특성값은 오름차순으로 입력된다.
  • -1억≤Ai≤1억
  • Ai-1≤Ai

출력

• 0에 가장 가까운 두 용액의 특성값의 합 출력

접근법

-101 -3 -1 5 93
s                  e           

• s→-101, e→93
  • -8
  • 음수이므로, 크기를 늘려야 하므로 s++
• s→-3, e→93
  • 90
  • 양수이므로, 크기를 줄여야 하므로 e—
• s→-3, e→5
  • 2
  • 양수이므로 , 크기를 줄여야 하므로 e—
• s→-3, e→-1
  • -4
  • 음수이므로 , 크기를 늘려야 하므로 s++
• s→-1, e→-1
  • s==e이므로 break,,,

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        int s = 0, e = N - 1, sum;
        int answer = Math.abs(0 - (arr[s] + arr[e]));
        int water1 = arr[s];
        int water2 = arr[e];
        while (s < e && e < N) {
            sum = arr[s] + arr[e];

            if (answer > Math.abs(0 - sum)) {
                answer = Math.abs(0 - sum);
                water1 = arr[s];
                water2 = arr[e];
            }

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

        bw.write(String.valueOf(water1 + water2));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 5549. 행성 탐사

• 링크 : https://www.acmicpc.net/problem/5549

문제 요약

• M*N 지도가 있다
  • 각 구역마다 지형이 알파벳으로 표시
    • J : 정글
    • O : 바다
    • I : 얼음
• 조사 영역 대상 K개를 만들었을 때, 각 영역마다 정글, 바다, 얼음이 각각 몇 개 있는 지 구하기

시간 제한

• 1초

입력

• 지도 크기 M, N
  • 1≤M,N≤1000
• 조사 대상 영역 개수 K
  • 1≤K≤10만
• M개의 줄에 지도 내용이 주어짐
• K개의 줄에 조사 대상 영역 정보 주어짐
  • a b c d
    • 왼쪽 위 모서리 좌표가 (a,b)
    • 오른쪽 아래 모서리 좌표가 (c,d)

출력

• 각 조사 대상 영역에 포함되어 있는 정글, 바다, 얼음의 수를 공백으로 구분해 한 줄에 한 정보씩 출력

접근법

• 정글, 바다, 얼음 별 누적합 배열을 만들고, 이걸 이해서 풀기

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

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

        char[][] arr = new char[M + 1][N + 1];
        String str;
        for (int i = 1; i <= M; i++) {
            str = br.readLine();
            for (int j = 1; j <= N; j++) {
                arr[i][j] = str.charAt(j - 1);
            }
        }

        int[][] jungle = new int[M + 1][N + 1];
        int[][] ice = new int[M + 1][N + 1];
        int[][] ocean = new int[M + 1][N + 1];

        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if(arr[i][j] == 'J') jungle[i][j]++;
                else if(arr[i][j] == 'I') ice[i][j]++;
                else if(arr[i][j] == 'O') ocean[i][j]++;

                jungle[i][j] += jungle[i - 1][j] + jungle[i][j - 1] - jungle[i - 1][j - 1];
                ocean[i][j] += ocean[i - 1][j] + ocean[i][j - 1] - ocean[i - 1][j - 1];
                ice[i][j] += ice[i - 1][j] + ice[i][j - 1] - ice[i - 1][j - 1];
            }
        }

        StringBuilder sb = new StringBuilder();
        int r1, c1, r2, c2;
        int jCnt, iCnt, oCnt;
        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            r1 = Integer.parseInt(st.nextToken());
            c1 = Integer.parseInt(st.nextToken());
            r2 = Integer.parseInt(st.nextToken());
            c2 = Integer.parseInt(st.nextToken());

            jCnt = jungle[r2][c2] - jungle[r2][c1 - 1] - jungle[r1 - 1][c2] + jungle[r1 - 1][c1 - 1];
            oCnt = ocean[r2][c2] - ocean[r2][c1 - 1] - ocean[r1 - 1][c2] + ocean[r1 - 1][c1 - 1];
            iCnt = ice[r2][c2] - ice[r2][c1 - 1] - ice[r1 - 1][c2] + ice[r1 - 1][c1 - 1];

            sb.append(jCnt + " " + oCnt + " " + iCnt + "\\n");
        }

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

 

알고리즘 문제) BOJ 19951. 태상이의 훈련소 생활

• 링크 : https://www.acmicpc.net/problem/19951

문제 요약

• 일렬로 N개의 칸으로 이루어져 있으며 각 칸마다 높이가 있음
• M번의 명령이 주어지고,
  • 각 명령마다, a번부터 b번칸 까지 높이 K만큼 흙을 덮거나 파라고 주어짐
• 각 명령을 모두 수행한 뒤 각 칸의 높이를 구해라

시간 제한

• 1초

입력

• 칸의 길이 N, 명령 개수 M
  • 1≤N≤10만
  • 1≤M≤10만
• 각 칸의 높이가 순서대로 N개 만큼 주어짐
  • -1만≤Hi≤1만
  • N,M,Hi는 정수
• M개의 줄에 명령이 주어짐
  • a b k
  • k≥0 : a부터 b까지 abs(k)만큼 흙을 덮음
  • k<0 : a부터 b까지 abs(k)만큼 흙을 파냄
  • abs(k) ≤ 100

출력

• 모든 지시를 수행한 후 각 칸의 높이를 출력

접근법

• 명령을 수행하고 나서 각 칸마다 얼마나 흙을 더하고 뺴야하는 지를 나타내는 배열을 만들어야 함
• N과 M이 10만까지 가능하므로 2중 for문 쓰면 X
• 그렇기 때문에, 업데이트를 한 번에 해야 한다.
• imos 알고리즘 사용
  • 먼저 업데이트 기록 ⇒ 예를 들어 1 5 -3이 주어지면 arr[1]=-3, arr[6]=3
  • 그다음에 arr배열을 활용해 누적합 배열을 만든다.
• 만든 누적합 배열과 원본 배열의 같은 인덱스의 원소 끼리 합을 원소 별로 각각 출력한다.

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        int a, b, k;
        int[] imos = new int[N + 2];
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());

            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            imos[a] += k;
            imos[b + 1] += -(k);
        }

        for (int i = 1; i <= N; i++) {
            imos[i] += imos[i - 1];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append((imos[i] + arr[i]) + " ");
        }

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

 

알고리즘 문제) BOJ 2023. 신기한 소수

• 링크 : https://www.acmicpc.net/problem/2023

문제 요약

• N자리 숫자 중 신기한 소수를 오름차순으로 정렬해서 출력하기
  • 신기한 소수
    • N자리, N-1자리, N-2자리,, 1자리 모두 소수인 수
      • 7331, 733, 73, 1

시간 제한

• 1초

입력

• N

출력

• N자리 수 중 신기한 소수 오름차순 출력

고민

• 매개변수로 number 보내줄 때 재귀 끝나고 return 부분에 복원하는 부분이랑, 소수 체크하고 소수가 아닌 경우 복원하는 부분에서 헤맸다!
  • 자꾸 음수나오거나, 오버플로우 떴다ㅠㅠ

접근법

• 백트랙킹 돌면서 1자리부터 N자리까지 소수인지 판정한다
  • 만약 중간에 소수가 아니라면 return(가지치기)
• 매개변수로 현재 숫자를 같이 넘겨주면 재귀 들어올 때마다 체크할 수 있지 않을까?

코드

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

public class Main {
    static int N;
    static StringBuilder sb = new StringBuilder();

    static boolean isPrime(int number) {

        if(number == 1 || number == 0) return false;

        int cnt = 0;
        for (int i = 2; i * i <= number ; i++) {
            if (number % i == 0) {
                cnt++;
            }
        }

        if (cnt == 0) return true;
        else return false;
    }
    static void recur(int cur, int number) {

        if (cur == N) {
            sb.append(number + "\\n");
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (cur == 0 && i == 0) continue;

            if(cur > 0) number = number * 10;
            number += i;

            if (!isPrime(number)){
                number -= i;
                if(cur > 0) number /= 10;
                continue;
            }

            recur(cur + 1, number);

            if(cur > 0) number -= i;
            number /= 10;
        }
    }

    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;

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

        recur(0, 0);

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

 

알고리즘 문제) BOJ 1037. 약수

• 링크 : https://www.acmicpc.net/problem/1037

문제 요약

• 어떤 수 N의 진짜 약수가 모두 주어질 때 N을 구해라
  • 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이면서 A가 1과 N이 아닐 것

시간 제한

• 1초

입력

• N의 진짜 약수의 개수
  • 개수는 50 보다 작거나 같은 자연수
• 진짜 약수가 주어진다.
  • 100만보다 이하, 2 이상의 자연수
  • 중복 X

출력

• N을 출력

접근법

• 주어진 약수들의 최소 공배수?
  • 단 주어진 약수들이 아닌 최소 공배수 ⇒ 너무 어렵게 생각함
• 그냥 약수들 중 최대, 최소 구해서 곱하면 된다.. 쉽게 생각하자 ㅠ

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

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

            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        bw.write(String.valueOf((long) max * min));
        bw.flush();
        bw.close();
        br.close();
    }
}