모각코 4회차 활동 내용 정리

목표 : 알고리즘 문제 풀고 블로그에 정리하기

 

https://ethereal-coder.tistory.com/76

코드트리 [자바 java] 그래프 탐색

https://www.codetree.ai/missions/2/problems/graph-traversal/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

정점과 간선이 주어지고, 1에서 출발해서 도착할 수 있는 정점을 구하는 문제이다.

처음에는 유니온파인드로 풀어야하나 했지만, 생각해보니 dfs로 탐색하고, 방문한 수로 같은 그래프에 해당하는 정점의 갯수를 구하는게 더 빨랐다.

리스트를 이용해서 각 정점과 연결되어있는 정점들을 저장했고, 1번리스트에 있는 정점들부터 stack에 차례로 쌓으면서 dfs를 수행했다.

 

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<Integer>[] list = new LinkedList[n+1];

        for(int i = 1;i<=n;i++){
            list[i] = new LinkedList<>();
        }

        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list[a].add(b);
            list[b].add(a);
        }

        Stack<Integer> stack = new Stack<>();

        for(int i = 0;i<list[1].size();i++){
            stack.push(list[1].get(i));
        }

        boolean[] vis = new boolean[n+1];
        vis[1] = true;

        while(stack.isEmpty() != true){
            int k = stack.pop();
            if(vis[k] == false){
                vis[k] = true;
                for(int i = 0;i<list[k].size();i++){
                    int g = list[k].get(i);
                    if(vis[g] == false){
                        stack.push(g);
                    }
                }
            }

        }

        int cnt = 0;
        for(int i = 2;i<=n;i++){
            
            if(vis[i] == true) {
                cnt++;
            }
        }

        System.out.println(cnt);

    }
}

 

 

https://ethereal-coder.tistory.com/75

코드트리 [자바 java] k개 중에 1개를 n번 뽑기

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 두 수가 주어지면 차례대로 순열을 만들어서 출력하는 프로그램이다.

알고리즘 풀 때 많이 사용되는 개념인데, 매번 풀 때마다 헷갈리는 것 같다. 

문제의 조건에 따라 따져야 할 것이 많은데, 이 문제는 중복을 허용하고, 오름차순, 내림차순에 대한 기준이 없다. 따라서 재귀함수에서 for문을 돌 때 현재 i의 값을 넘겨주지 않아도 되고(오름, 내림 x) , 현재 탐색하고 있는 i값의 방문여부도 상관하지 않아도 된다.

 

처음에 StringBuilder을 사용하지 않아서 시간초과가 나왔는데, 수정하니 정상적으로 작동했다.

 

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




public class Main {

    
static int[] arr;
static int m;
static int n;
static StringBuilder sb;

static void print(){
    for(int i = 0;i<m;i++){
        sb.append(arr[i]).append(" ");
    }
    sb.append("\n");
}

static void make(int size){
    if(size == m){
        print();
    }

    else{
        for(int i = 1;i<= n;i++){
         
                arr[size] = i;
                make(size+1);
          

      }
    }
    
}


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];

        make(0);

        System.out.println(sb);

    }
}

https://ethereal-coder.tistory.com/74

백준 [java 자바] 9084 : 동전

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

9084번: 동전

 

이 문제를 보자마자 언젠가 풀었던 문제인 것 같은데? 라는 생각이 들긴 했다. dp를 사용하고, 점화식을 구해서 풀어야 한다는 것 까지는 알아냈지만 여기서 어떻게 해야 할지 도저히 감이 잡히지 않아서 사람들의 풀이법을 검색해서 배웠다.

일단 풀이법을 그림으로 정리해보았다. 글씨가 정말 별로지만, 이해하는데는 확실히 도움이 되었다. 일단, 동전의 수가 주어지고 동전의 액수가 들어오면, 해당 액수만큼 dp배열을 만든다. 

그 다음에 동전의 액수가 작은 것 부터 하나씩 탐색하는데, 현재 탐색중인 액수에서, 현재 탐색중인 동전의 액수만큼 뺀 것을 액수의 dp값에 더해주면, 이제까지 탐색했던 동전들로 만들 수 있는 종류의 수가 배열에 들어가게된다.