알고리즘 4주차

문제번호 15721

• 알고리즘 : ?
• 난이도 :

문제

15721

접근

• 내가 풀기 위해 접근했던 순서

가정

• 풀기 전에 ~ 식으로 풀면 되겠다. 등.

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.List;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    static int number = 0;  
    static int connections = 0;  
    static int count = 0;  
    static boolean[] visit;  
    static List<Integer>[] computers;  
  
    public static void main(String[] args) throws IOException {  
  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
       number = Integer.parseInt(br.readLine());  
       connections = Integer.parseInt(br.readLine());  
       visit = new boolean[number + 1];  
       computers = new List[number + 1];  
  
       for (int i = 0; i < number + 1; i++) {  
          computers[i] = new ArrayList<Integer>();  
       }  
  
       StringTokenizer st;  
       for (int i = 0; i < connections; i++) {  
          st = new StringTokenizer(br.readLine());  
          int first = Integer.parseInt(st.nextToken());  
          int second = Integer.parseInt(st.nextToken());  
          computers[first].add(second);  
          computers[second].add(first);  
  
       }  
  
       dfs(1);  
       System.out.println(count);  
  
    }  
  
    public static void dfs(int start) {  
       if (!visit[start]) {  
          visit[start] = true;  
          count++;  
       }  
  
       for (int i = 0; i < computers[start].size(); i++) {  
          dfs((int)computers[start].get(i));  
       }  
  
    }  
  
}

시행착오

• 풀 면서 자신이 했던 시행착오들

참고자료

• 함께 보면 좋은 글, 링크 등.

문제번호

• 알고리즘 : dfs
• 난이도 :

문제

1012

접근

• 내가 풀기 위해 접근했던 순서

가정

• 풀기 전에 ~ 식으로 풀면 되겠다. 등.

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.List;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    static int number = 0;  
    static int[] time;  
    static int[] price;  
  
    public static void main(String[] args) throws IOException {  
  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       number = Integer.parseInt(br.readLine());  
  
       StringTokenizer st;  
       for (int i = 0; i < number; i++) {  
          st = new StringTokenizer(br.readLine());  
          time = new int[st.countTokens()];  
          price = new int[st.countTokens()];  
  
       }  
  
       int[] dp = new int[number + 1];  
  
       for (int i = 0; i < number; i++) {  
          if (i + time[i] <= number) {    //범위에 벗어나지 않는다면  
             dp[i + time[i]] = Math.max(dp[i + time[i]], dp[i] + price[i]);  
          }//if  
          dp[i + 1] = Math.max(dp[i + 1], dp[i]);    //다음dp=현재 누적값vs 다음 누적값  
  
       }//for  
       System.out.println(dp[number]);  
  
    }  
}

시행착오

참고자료

문제번호

• 알고리즘 :
• 난이도 :

문제

접근

• 내가 풀기 위해 접근했던 순서

가정

• 풀기 전에 ~ 식으로 풀면 되겠다. 등.

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
  
public class Main {  
  
    static int number = 0;  
    static int[] time;  
    static int[] price;  
  
    public static void main(String[] args) throws IOException {  
  
  
       // TODO Auto-generated method stub  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       StringBuilder sb = new StringBuilder();  
       int T = Integer.parseInt(br.readLine());  
       for(int i=0;i<T;i++) {  
          String W = br.readLine();  
          int K = Integer.parseInt(br.readLine());  
          int min = 10001, max = 0;  
          ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();  
          for(int a=0;a<26;a++) {  
             list.add(new ArrayList<>());  
          }  
  
          //W 탐색  
          for(int j=0;j<W.length();j++) {  
             int unicode = W.charAt(j) - 97;  
             list.get(unicode).add(j);  
  
             //어떤 알파벳(W[j])가 K번 나왔을 때 연속 문자열 길이를 구한다  
             int size = list.get(unicode).size();  
             if(size >= K) {  
                int start = list.get(unicode).get(size - K);  
                int end = list.get(unicode).get(size-1);  
                int len = end - start + 1;  
                if(len<min) {  
                   //System.out.println("min: "+end+" "+start);  
                   min = len;  
                }  
                if(len>max) {  
                   //System.out.println("max: "+end+" "+start);  
                   max = len;  
                }  
             }  
          }  
          if(min==10001) {  
             sb.append("-1\n");  
             continue;  
          }  
          sb.append(min+" "+max+"\n");  
       }  
       System.out.println(sb.toString());  
    }  
}

시행착오

• 풀 면서 자신이 했던 시행착오들

참고자료

• 함께 보면 좋은 글, 링크 등.