[2021 동계 모각코] 5회차 회고록

5회차(2022.02.04 15:00~18:00)

---

1. 알고리즘 문제해결전략

무식하게 풀기 부분 읽고 정리

https://www.notion.so/6-1d949295ded14f818bb5795ceaa7408a

 

2. 재귀호출, 완전탐색 관련 문제 2개 이상 풀기

1) 16953 A->B

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

10819번: 차이를 최대로

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

public class Main {
    static long a;
    static long b;
    static boolean exist = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        String[] s = input.split(" ");
        a = Long.parseLong(s[0]);
        b = Long.parseLong(s[1]);

        changeAtoB(a, 1);
        if(!exist) {
            System.out.println(-1);
        }
    }

    static void changeAtoB(long start, int count) {
        if(start>b) {
            return;
        } else if(start==b) {
            exist=true;
            System.out.println(count);
        } else {
            changeAtoB(start*2, count+1);
            String tmp = Long.toString(start);
            tmp += "1";
            changeAtoB(Long.parseLong(tmp), count+1);
        }
    }
}

 

2) 2667 단지번호붙이기

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

public class Main {
    static int n;
    static int[][] box;
    static boolean[][] visit;

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int count;

    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        n = Integer.parseInt(input);
        box = new int[n][n];
        visit = new boolean[n][n];

        for(int i=0;i<n;i++) {
            input = br.readLine();
            String[] s = input.split("");
            for(int j=0;j<n;j++) {
                box[i][j] = Integer.parseInt(s[j]);
            }
        }

        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(box[i][j]==1 && !visit[i][j]) {
                    count=0;
                    dfs(i, j);
                    if(count==0) {
                        list.add(1);
                    } else {
                        list.add(count);
                    }
                }
            }
        }

        System.out.println(list.size());
        Collections.sort(list);
        for(Integer i : list) {
            System.out.print(i + " ");
        }
    }

    static void dfs(int x, int y) {
        if(box[x][y]==0)
            return;
        for(int i=0;i<4;i++) {
            if(x+dx[i]<n && x+dx[i]>=0 && y+dy[i]<n && y+dy[i]>=0 && !visit[x+dx[i]][y+dy[i]]) {
                if(box[x+dx[i]][y+dy[i]]==1) {
                    visit[x+dx[i]][y+dy[i]]=true;
                    count++;
                    dfs(x+dx[i], y+dy[i]);
                }
            }
        }
    }

}

3) 연결 요소의 개수

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

public class Main {
    static int n;
    static int[][] vertex;
    static boolean[] visit;

    static int count=0;

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

        String[] s = input.split(" ");
        n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        vertex = new int[n+1][n+1];
        visit = new boolean[n+1];

        for(int i=0;i<m;i++) {
            input = br.readLine();
            String[] ss = input.split(" ");
            int start = Integer.parseInt(ss[0]);
            int end = Integer.parseInt(ss[1]);

            vertex[start][end]=1;
            vertex[end][start]=1;
        }

        for(int i=1;i<=n;i++) {
            if(!visit[i]) {
                visit[i]=true;
                dfs(i);
                count++;
            }
        }
        System.out.println(count);
    }

    static void dfs(int start) {
        for(int i=1;i<=n;i++) {
            if(!visit[i] && vertex[start][i]==1) {
                visit[i]=true;
                dfs(i);
            }
        }
    }
}

---

하나의 알고리즘을 깊게 공부하고, 응용 문제도 풀어보며

더 깊은 이해와 문제 해결 방법을 얻을 수 있었던 유익한 시간이었다.