[12월 1주차] 알고리즘 스터디

1. 단절점과 단절선 - 실버 1

출처 - https://www.acmicpc.net/problem/14675

MySol) 트리 1380ms

<hide/>

public class Test1 {


    static ArrayList<Integer>[] lists;  // 리스트로 이뤄진 배열

    public static void solution(int t, int k) {

        if (t == 2) {
            System.out.println("yes");
            return;
        }

        if (lists[k].size() >= 2) {		 // k번 노드와 연결된 노드의 개수
            System.out.println("yes");
            return;
        }
        System.out.println("no");
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int node = Integer.parseInt(br.readLine());
        lists = new ArrayList[node + 1];

        // 0번 노드는 없으니까 1 ~ node 번까지 초기화
        for (int i = 1; i <= node; ++i) {
            lists[i] = new ArrayList<>();
        }

        for (int i = 0; i < node - 1; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            lists[start].add(end);      // start 번 노드에 연결된 노드의 List
            lists[end].add(start);
        }

        int qCnt = Integer.parseInt(br.readLine());

        for (int i = 0; i < qCnt; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            solution(t, k);
        }
    }
}

 

• list는 k번째 노드와 연결된 노드를  list로 나타낸 것과 같다.
• root, leaf 노드는 연결된 노드의 개수가 1개 이하?? 왜?
• t = 2일 때, 간선을 자르니까 트리의 간선을 자르면 항상 두 개의 트리로 나눠진다.
  • "yes" 출력
• t = 1인 경우, 노드를 제거한다.
  • 1) 해당 노드와 연결된 노드가 2개 이상 => 2개의 트리로 나눠질 수 있다.
  • 2) 해당 노드와 연결된 노드가 2개 미만 => 2개의 트리로 나눠질 수 없다.

 

 참고 blog - https://moonsbeen.tistory.com/271

 

 

 

 

2. 퇴사 2 - 골드 4

출처 - https://www.acmicpc.net/problem/15486

 

  MySol)  832ms

 

• 스터디원 코드를 보고 변수명만 조금 바꿈
• 입력된 배열 consulting[][] 배열에다가 dp 배열을 하나 더 만드니까 속도가  100ms정도 더 걸렸다.
• 마지막 날에 대한 max 값만 구하면 된다.
• 따라서 DP를 쓴다.
  • 만약, 중간 날짜에 대한 max값을 모두 구해야되는 경우는 브루투 포스, 그리디를 써야되지 않을까 싶다.
• n +1 번째 날 퇴사하므로 n + 2 크기의 배열을 만든다.
• if문을 넣어서 일정이 n + 2를 넘지 않도록 설정한다.
  • 현재 일정을 추가할지 말지 max() 문으로 결정한다.

 

  Sol)   스터디원(JW) 코드   732ms - DP     

https://github.com/Joowon-Seo/Baekjoon_Practice/blob/main/%EB%B0%B1%EC%A4%80/Gold/15486.%E2%80%85%ED%87%B4%EC%82%AC%E2%80%852/%ED%87%B4%EC%82%AC%E2%80%852.java

<hide/>

public class Main {

	public static BufferedReader br = new BufferedReader(
		new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(
		new OutputStreamWriter(System.out));

	public static int N;
	public static int[] T;
	public static int[] P;
	public static int[] dp;
	public static int max = Integer.MIN_VALUE;

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

		// N의 범위 값이 1,500,000 => 2중 반복 x
		// 따라서 한번 순회를 하면서 문제를 해결해야함 -> 데이터를 보관(dp)활용
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		T = new int[N + 2];
		P = new int[N + 2];
		dp = new int[N + 2];

		for (int i = 1; i < N + 1; i++) {
			st = new StringTokenizer(br.readLine());
			T[i] = Integer.parseInt(st.nextToken());
			P[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i < N + 2; i++) {

			// 현재 최고 값 찾기
			// i를 날짜로 활용
			max = Math.max(max, dp[i]);

			// 일정이 N + 2를 넘어갈 수 있음(에러방지)
			if (i + T[i] < N + 2) {

				//현재 일정을 소화할지말지에 대한 판단
				dp[i + T[i]] = Math.max(dp[i + T[i]], max + P[i]);
			}
		}
		bw.write(max + "");
		br.close();
		bw.close();
	}
}

 

 

 

3. 특정 거리의 도시 찾기

 

출처 - https://www.acmicpc.net/problem/18352

 

  MySol)