[백준 JAVA] 알고리즘 재활훈련 (심화)

 

이어서 조금 시간이 걸리더라도 이번에는 조금 꼼꼼히 풀어보고자 한다.

 

부분합

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

풀이시간 : 풀지 못함

 

투포인터의 기본 문제라고 하는데 역시 투 포인터 개념이 약한것 같다.

 

그리고 문제도 잘못읽어서 많은 시간을 허비했다. 문제부터 꼼꼼히 읽는 습관을 다시 기르자.

 

실수

1. 문제에서는 이어지는 수열의 부분합을 말하고 있지만 먼처 정렬을 해버리는 바람에 결과가 잘못나왔다.

 

2. S 와 일치하는 값이 나올때 답이 구해지는줄 알았는데 S이상일 때 부분합의 최소길이를 구하는 문제였다.

 

3. 이중 포문은 딱봐도 시간초과가 예상되었는데 어떻게는 풀어보자는 마음으로 시도했다가 역시나 틀렸다.

 

반성

 

1. 문제 꼼꼼히 읽기

 

2. 시간계산 해서 안돼면 시도도 해보지 않기

 

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

public class Main {
    public static int N, S, ans = Integer.MAX_VALUE;
    public static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = 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());
        }

        int start = 0, end = 0, sum = 0;

        while(true){
            if(sum >= S){
                ans = Math.min(ans, end - start);
                sum -= arr[start++];
            }else if(end == N){
                break;
            }else {
                sum += arr[end++];
            }
        }

        System.out.println(ans == Integer.MAX_VALUE ? 0 : ans);
    }

}

 

투포인터 문제는 좀 더 연습해야될꺼같다.

 

점프

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

풀이시간 : 못품

 

bfs로 접근하여 빠르게 풀고 예제까지 맞아서 풀었나 싶었는데 메모리 초과가 났다.

 

이 경우에 메모리 초과가 나는 이유는 map의 크키가 100 * 100 이라 큐에서 경우의 수를 못버티는 것이다.

 

풀이방법이 생각나지않아 찾아봤더니 DP 로 경우의 수를 계산해야 한다고 나와있어서 그대로 다시 풀었다.

 

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

public class Main {
    public static int N;
    public static long[][] dp;
    public static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new long[N][N];
        dp[0][0] = 1;

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

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(i == N - 1 && j == N - 1) continue;
                int k = map[i][j];
                if(k == 0) continue;
                if(i + k < N) dp[i + k][j] += dp[i][j];
                if(j + k < N) dp[i][j + k] += dp[i][j];
            }
        }

        System.out.println(dp[N-1][N-1]);
    }
}

 

전혀 생각지도 못한방법이여서 시간을 더 오래 투자했어도 못풀었을꺼같았다.

아직 갈길이 멀다.

 

최소비용 구하기

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

풀이시간 : 다익스트라 보고 품

 

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

public class Main {
    public static int N, M, start, end;
    public static int[] dist;
    public static List<int[]>[] graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        dist = new int[N + 1];
        graph = new List[N + 1];
        for(int i = 1; i <= N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[u].add(new int[] {v, w});
        }

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        pq.offer(new int[] {start, 0});

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int now = cur[0];
            int nowDist = cur[1];

            if(nowDist > dist[now]) continue;

            for(int[] next : graph[now]){
                int cost = dist[now] + next[1];
                if(cost < dist[next[0]]){
                    dist[next[0]] = cost;
                    pq.add(new int[] {next[0], cost});
                }
            }
        }

        System.out.println(dist[end]);
    }
}

 

이것도 다익스트라가 기억이 가물가물해서 보고 풀었다. 내일 다시 보자.

 

수들의 합 4

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

 

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

public class Main {
    public static int N, K;
    public static Long ans = 0L, sum = 0L;
    public static Map<Long, Long> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map.put(0L, 1L);

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            int a = Integer.parseInt(st.nextToken());
            sum += a;
            ans += map.getOrDefault(sum - K, 0L);
            map.put(sum, map.getOrDefault(sum, 0L) + 1L);
        }

        System.out.println(ans);
    }
}

 

처음엔 투포인터로 풀려고 했지만 정렬을 하면 안돼고 음수값이 포함되어있기 때문에 사용할 수가 없었다. 

 

다른 사람의 풀이를 보고 풀었는데 누적합 + HashMap 을 이용하여 풀이하는 문제였다.

 

누적합을 사용하여 구간의 합을 구하는 방법은 기존에 알고 있었지만 이것을 HashMap과 함께 사용하는것은 처음 접했다.

 

우선 누적합을 S[i] 라 했을때

 

S[i] = A[1] + A[2] + ... + A[i] (i번째까지 합)이고

 

그럼 구간합 A[l..i] = S[i] - S[l-1]이 된다.

 

즉, i번째까지 합 S[i]가 주어졌을 때, S[i] - K = S[l-1]인 지점이 과거에 몇 번 나왔는지만 세면 된다.

 

마지막으로 전부 Integer로 했을때는 범위오류가 생길 수 있으므로 정답과 기존에 나온 횟수를 셀때는 Long을 사용해야한다.

 

이전까지는 Integer를 사용해도 되는 곳에 Long을 사용하면 뭔가 시간이나 메모리를 더 쓰는거같아서 확실히 Long을 사용하는데에서만 사용했는데 막상 전부 Long으로 하는것보다 Integer를 섞어서 쓰는게 시간이나 메모리는 더 많이 잡아먹었다.

 

찾아보니 ans를 Long으로 지정하고 a는 Integer로 지정해놓으면 

 

ans += a; 는 사실 ans = Long.valueOf(ans.longValue() + a) 로 변환된다.

 

즉 매 반복마다 새 Long 객체 생성 → 힙 할당 증가 → 시간/메모리 둘 다 손해인것이다.

 

줄세우기

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

 

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

public class Main {
    public static int N, M;
    public static int[] in;
    public static List<Integer>[] graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        in = new int[N + 1];
        graph = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++){
            graph[i] = new ArrayList<>();
        }
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u].add(v);
            in[v]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= N; i++){
            if(in[i] == 0) q.offer(i);
        }

        while(!q.isEmpty()){
            int cur = q.poll();
            sb.append(cur).append(" ");
            for(int t : graph[cur]){
                if(--in[t] == 0) q.offer(t);
            }
        }

        System.out.println(sb);
    }
}

 

위상정렬을 활용하는 문제 개념이 잘 기억이 안나 문제 해답은 보지 않았지만 위상정렬풀이를 보고 풀었다.

 

in은 들어오는 노드의 갯수를 기억하는 배열

graph는 나가는 노드를 저장하는 리스트

 

들어오는 노드가 0인 노드를 먼저 q 에 삽입한 뒤 그와 연결된 노드들의 차수를 1 감소시킨다.

 

그 뒤 0인 노드가 있다면 다시 큐에 넣어준다.

 

단지번호붙이기

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

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

public class Main {
    public static int N, cnt;
    public static int[][] map;
    public static List<Integer> list = new ArrayList<>();
    public static int[] dr = {1, 0, -1, 0};
    public static int[] dc = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < N; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] == 0) continue;
                cnt = 0;
                dfs(i, j);
                list.add(cnt);
            }
        }

        Collections.sort(list);
        sb.append(list.size()).append("\n");
        for(int a : list){
            sb.append(a).append("\n");
        }

        System.out.println(sb);
    }
    public static void dfs(int r, int c){
        map[r][c] = 0;
        cnt++;
        for(int d = 0; d < 4; d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == 0) continue;
            dfs(nr, nc);
        }
    }
}

 

예전부터 곱씹어가며 풀었던 문제는 이제 쉽게 푸는것같다. 반복이 중요한듯