본문 바로가기
Backend/공부 일지

2024/02/29(목)

by 박상윤 2024. 3. 1.

Part. 알고리즘

그리디 알고리즘

 

배열의 내림차순 정렬하는 방법

Integer[] coins = new Integer[N];
// 주의할 점 : Integer 배열일 경우에만 사용이 가능하다.

// 방법 1.
Arrays.sort(coins, Collections.reverseOrder());

// 방법 2.
Arrays.sort(coins, new Comparator<Integer>(){
	@Override
    public int compare(Integer i1, Integer i2){
    	return i2 - i1;
    }
});

 

백준 - 11047 동전0

https://www.acmicpc.net/problem/11047

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

내가 푼 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

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

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

        Integer[] coins = new Integer[N];

        for (int i = 0; i < coins.length; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(coins);

        int answer = 0;
        for (int i = coins.length - 1; i >= 0; i--) {
            answer += K / coins[i];
            K %= coins[i];
            if (K == 0) {
                break;
            }
        }

        System.out.println(answer);
    }
}

 

동전 개수의 최솟값을 구하기 위해선, 동전의 갯수를 줄여야 한다고 생각했다.

동전의 갯수를 줄이기 위해선 가치가 큰 동전부터 갯수를 세주어야 한다고 생각했다.

if(K==0){
	break;
}

 

이 조건문을 달아준 이유는 동전이 이미 다 소진되었는데, 불필요한 반복문을 최소화하기 위해서이다.

 

백준 - 1715번 카드 정렬하기

https://www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

 

 

1차 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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[] cardValues = new int[N];

        for (int i = 0; i < N; i++) {
            cardValues[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(cardValues);

        int[] S = new int[N];
        S[0] = cardValues[0];

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

        int answer = 0;
        for (int i = 1; i < N; i++) {
            answer += S[i];
        }

        System.out.println(answer);
        br.close();
    }
}

 

단순하게 제일 작은 값부터 하나씩 누적합을 해주면 된다고 생각했다. 최종적으로는 누적합 했던 결과들을 더해주면 된다고 생각했다.

 

책에서 알려주는 문제 분석하기

먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미친다.

그러므로, 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있다.

카드 중 가장 작은 개수를 가진 묶음 2개를 뽑아주고, 이 2개를 기준으로 합친 새로운 카드 묶음을 다시 데이터 넣고 정렬해야 한다.

데이터의 삽입, 삭제, 정렬이 자주 일어나므로 우선순위 큐를 이용해야 한다.

 

아.. 우선순위 큐 메모!

 

책에서 알려주는 손으로 풀어보기

1. 주어진 카드에서 가장 작은 묶음 2개를 선택

2. 합친 카드 묶음을  다시 전체 카드 묶음 속에 넣는다.

3. 1,2 과정을 카드 묶음이 1개만 남을 때까지 반복한다.

 

 

2차 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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());

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < N; i++) { // 최솟값
            pq.add(Integer.parseInt(br.readLine()));
        }

        int sum = 0;
        while (pq.size() != 1) {
            int data1 = pq.remove();
            int data2 = pq.remove();
            sum += data1 + data2;
            pq.add(data1 + data2);
        }

        System.out.println(sum);
        br.close();
    }
}

 

반복문 내부에 pq의 크기가 1이라는 것은 더이상 더해줄 카드의 묶음이 존재하지 않는다는 것을 의미한다.

 

백준 - 1744번 수를 묶어서 최댓값 만들기

 

https://www.acmicpc.net/problem/1744

 

1744번: 수 묶기

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에

www.acmicpc.net

 

 

1차 풀이 코드

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());

        PriorityQueue<Integer> minus = new PriorityQueue<>();
        PriorityQueue<Integer> plus = new PriorityQueue<>(Comparator.reverseOrder());

        for (int i = 0; i < N; i++) {
            int value = Integer.parseInt(br.readLine());

            if (value <= 0) {
                minus.add(value);
            } else {
                plus.add(value);
            }
        }

        int sum = 0;
        while (minus.size() >= 2) { // 음수는 작을수록
            int data1 = minus.remove();
            int data2 = minus.remove();
            sum += (data1 * data2);
        }

        while (plus.size() >= 2) {
            int data1 = plus.remove();
            int data2 = plus.remove();
            sum += (data1 * data2);
        }

        if (plus.size() == 1) {
            sum += plus.remove();
        }

        if (minus.size() == 1) {
            sum += minus.remove();
        }

        System.out.println(sum);
        br.close();
    }
}

 

38%까지 정답! 그래도 잘했다!

음수는 음수끼리 곱해야 최댓값이 나오고, 양수는 양수끼리 곱해야 최댓값이 나온다고 생각했다.

음수는 우선순위큐가 최솟값을 뱉어내도록 구현하고, 그에 비해 양수는 최댓값을 뱉어내도록 구현했다.

최종적으로 조건문을 두어 두 큐가 비어있지 않을 경우, 추가적인 값을 더해주었다.

 

책에서 알려주는 문제 분석하기

가능한 큰 수들끼리 묶어야 결괏값이 커진다는 것을 알 수 있다.

또한 음수끼리 곱하면 양수로 변하는 성질을 추가로 고려해서 문제를 풀어보자

 

책에서 알려주는 손으로 풀어보기

1. 수의 집합을 1보다 큰 수, 1, 0, 음수 4가지 유형으로 나눠 저장한다. -> 아! 4가지 유형으로 나눠주었구나, 1은 곱해도 그대로니 굳이 묶어줄 필요가 없고, 0은 음수를 최대한 상쇄시키고자 하는 역할이라고 생각한다.

2. 1보다 큰 수의 집합을 정렬해 최댓값부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수일 대 남은 수는 그대로 더한다.

3. 음수의 집합을 정렬해 최솟값부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수일 때 수열에 0이 존재한다면 1개 남는 음수를 곱해 0을 만들고, 수열에 0이 없다면 그대로 더한다.

 

문제 분석한 후 내 풀이의 문제점

내 풀이의 결정적인 오점은 1을 곱해주었다는 것이다.

예를들어 숫자 2 1 1 1이 존재할때, 합이 최대가 되게 하기 위해서는 2+1+1+1를 해주어야하는데, 내 풀이는 (2*1)+(1*1)을 해주고 있었다.

1은 곱해주는 것보다 더해주는게 더 최댓값이 나온다는 사실을 망각하고  있었다.

 

 

2차 풀이 코드

package 백준.수를묶어서최댓값만들기;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

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());

        PriorityQueue<Integer> minus = new PriorityQueue<>();
        PriorityQueue<Integer> plus = new PriorityQueue<>(Comparator.reverseOrder());

        int one = 0;

        for (int i = 0; i < N; i++) {
            int value = Integer.parseInt(br.readLine());

            if (value <= 0) { // 0을 넣어주는 이유는 음수를 상쇄시키기 위해서
                minus.add(value);
            } else if (value == 1) {
                one++;
            } else {
                plus.add(value);
            }
        }

        int sum = 0;
        while (minus.size() >= 2) { // 음수는 작을수록
            int data1 = minus.remove();
            int data2 = minus.remove();
            sum += (data1 * data2);
        }

        while (plus.size() >= 2) {
            int data1 = plus.remove();
            int data2 = plus.remove();
            sum += (data1 * data2);
        }

        if (!plus.isEmpty()) {
            sum += plus.remove();
        }

        if (!minus.isEmpty()) {
            sum += minus.remove();
        }

        System.out.println(sum + one);
        br.close();
    }
}

 

백준 - 1744번 수를 묶어서 최댓값 만들기

https://www.acmicpc.net/problem/1931

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

 

1차 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    public static class Node {
        int start;
        int end;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

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

        int N = Integer.parseInt(br.readLine());
        Node[] value = new Node[N];

        // 끝 시간을 기준으로 정렬하기
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            value[i] = new Node(start, end);
        }

        Arrays.sort(value, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.end - o2.end;
            }
        });

        int answer = 1;
        int beforeEnd = value[0].end;
        for (int i = 1; i < value.length; i++) {
            Node cur = value[i];
            int curEnd = cur.end;
            int curStart = cur.start;

            if (beforeEnd <= curStart) {
                answer++;
                beforeEnd = curEnd;
            }
        }

        System.out.println(answer);
    }
}

 

75%까지 맞고 나머지는 틀렸다.

회의가 끝나는 시간을 기준으로 정렬을 한다음에, 현재 회의 시작시간이 이전 회의 끝난시간과 같거나 더 크면 회의 회수를 1개 증가시켜주도록 했다. 

 

책에서 알려준 문제 분석하기

현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 게 유리하다.

그러므로, 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택하면 된다.

 

종료시간이 같은 경우

문제에서 회의의 시작 시간과 종료 시간이 같을 수도 있다고 했다.

ex) (1,2), (2,2) 2개의 회의가 존재한다고 가정했을 때, 실제로는 2개의 회의가 겹치지 않게 할 수 있지만,

(2,2)가 먼저 나오게 되면 나중에 나온(1,2)가 불가능할 수 있다.

 

나에게 하고 싶은 말

아! 이 경우를 생각하지 못했다.. 시작시간과 종료 시간이 같을 수 도  있다는 부분을 문제를 읽으면서 인지를 못했다. 문제를 더 꼼꼼히 읽어봐야 겠다. 예제 코드가 맞다고 해도 주어진 조건에 따른 예외상황을 생각해보자.

 

 

2차 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    public static class Node {
        int start;
        int end;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

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

        int N = Integer.parseInt(br.readLine());
        Node[] value = new Node[N];

        // 끝 시간을 기준으로 정렬하기
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            value[i] = new Node(start, end);
        }

        Arrays.sort(value, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {

                if (o1.end == o2.end) {
                    return o1.start - o2.start;
                }
                return o1.end - o2.end;
            }
        });

        int answer = 1;
        int beforeEnd = value[0].end;
        for (int i = 1; i < value.length; i++) {
            Node cur = value[i];
            int curEnd = cur.end;
            int curStart = cur.start;

            if (beforeEnd <= curStart) {
                answer++;
                beforeEnd = curEnd;
            }
        }

        System.out.println(answer);
        br.close();
    }
}

Comparator를 사용해서 Object 배열을 필요한 필드에 따라 정렬해주었다.

 

백준 - 1541번 최솟값을 만드는 괄호 배치 찾기

https://www.acmicpc.net/problem/1541

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

www.acmicpc.net

 

1차 풀이 코드

문자열 분리 부분에서 막혔다. 아직 기본기가 부족한것 같다.

 

책에서 알려준 문제 분석하기

최솟값을 만들기 위해선 음수를 최대로 만들어야 하기 때문에, [-]뒤에 나오는 수들은 괄호로 묶어주어야 된다고 생각했다.

[-] 뒤에 나오는 수들은 곧 [+] 다음에 나오는 라고 생각하면 된다. 이 수들을 먼저 괄호로 묶어서 더해주고, 맨 처음 숫자를 제외한 괄호로 묶어서 더해준 원소들은 전부 빼준다.

 

2차 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int answer = 0;

        for (int i = 0; i < values.length; i++) {
            int tmp = Sum(values[i]);
            if (i == 0) {
                answer += tmp; // 맨처음만 더해주기
            } else {
                answer -= tmp; // 마지막은 빼주기
            }
        }

        System.out.println(answer);
    }

    public static int Sum(String a) {
        int sum = 0;
        String[] tmp = a.split("[+]");
        for (int i = 0; i < tmp.length; i++) {
            sum += Integer.parseInt(tmp[i]);
        }

        return sum;
    }
}

 

- 기호를 기준으로 문자열을 선 분리 해준뒤, 분리된 문자열을 + 기호로 재분리해서 더해준 값을 이용한다.

+ 기호로 분리를하고자 할때는 "[+]" 이렇게 작성해주어야 한다.

맨 처음값과 마지막은 무조건 숫자가 나온다고 문제에 명시되어 있었다. 맨 처음값이 무조건 숫자이므로, 무조건 더해주어야 한다.

if (i == 0) {
    answer += tmp; // 맨처음만 더해주기
} else {
    answer -= tmp; // 마지막은 빼주기
}

 

그래프

 

백준 - 18352번 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

 

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

 

 

1차 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static List<List<Integer>> list = new ArrayList<>();

    public static boolean check = false;
    public static List<Integer> answer = new ArrayList<>();
    public static int[] visited;

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

        int cityNum = Integer.parseInt(st.nextToken());
        int roadNum = Integer.parseInt(st.nextToken());
        int distance = Integer.parseInt(st.nextToken()); // 거리 정보
        int startCity = Integer.parseInt(st.nextToken()); // 출발 도시

        visited = new int[cityNum + 1];

        for (int i = 0; i < cityNum + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < roadNum; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list.get(start).add(end);
        }

        bfs(startCity);

        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == distance) {
                answer.add(i);
            }
        }

        Collections.sort(answer);

        if (answer.size() > 0) {
            for (int value : answer) {
                System.out.println(value);
            }

            return;
        }

        System.out.println(-1);
    }

    public static void bfs(int startCity) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startCity);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int value : list.get(cur)) {
                if (visited[value] == 0) { // 방문하지 않은 경우
                    visited[value] = visited[cur] + 1; // 이전 방문 노드 + 1
                    queue.add(value);
                }
            }
        }
    }
}

 

81%정도까지 맞고 틀려버렸다..

무엇이 틀린 것일까?

 

 

2차 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static List<List<Integer>> list = new ArrayList<>();

    public static boolean check = false;
    public static List<Integer> answer = new ArrayList<>();
    public static int[] visited;

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

        int cityNum = Integer.parseInt(st.nextToken());
        int roadNum = Integer.parseInt(st.nextToken());
        int distance = Integer.parseInt(st.nextToken()); // 거리 정보
        int startCity = Integer.parseInt(st.nextToken()); // 출발 도시

        visited = new int[cityNum + 1];
        Arrays.fill(visited, -1);

        for (int i = 0; i < cityNum + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < roadNum; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list.get(start).add(end);
        }

        bfs(startCity);

        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == distance) {
                answer.add(i);
            }
        }

        Collections.sort(answer);

        if (answer.size() > 0) {
            for (int value : answer) {
                System.out.println(value);
            }

            return;
        }

        System.out.println(-1);
    }

    public static void bfs(int startCity) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startCity);
        visited[startCity]++;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int value : list.get(cur)) {
                if (visited[value] == -1) { // 방문하지 않은 경우
                    visited[value] = visited[cur] + 1; // 이전 방문 노드 + 1
                    queue.add(value);
                }
            }
        }
    }
}

 

방문 배열을 전부 0으로 초기화 해주었던것을 -1로 초기화해주었다.

방문을 하지 않은 기준을 -1로 변경시켜 주었다.

시작 노드와 방문하지 않은 노드의 구분점을 명확히 해주었다.

 

나에게 하고 싶은 말

방문 배열 초기화는 무조건 -1로 해주어야 겠다!

 

Part. Spring

ORM(ex. JPA) SQL Mapper (ex.jdbc)
DB 테이블과 Java 객체를 매핑 단순히 DB와 Java를 연결
SQL 자동 생성됨 SQL을 명시해 주어야 함

 

 

'Backend > 공부 일지' 카테고리의 다른 글

2024/03/05(화) 가자! 네카라쿠배당토  (0) 2024.03.05
2024/03/04(월)  (0) 2024.03.05
2024/03/03(일)  (0) 2024.03.04
2024/03/03(일)  (0) 2024.03.03
2024/03/01(금)  (0) 2024.03.02

관련글

티스토리툴바