6th Meet - 코독하구만

Daily Object

    - 정점이 주어졌을 때 최단 거리를 구하는 알고리즘( 다익스트라 )을 다시 공부해보며 익힌다.

    - 지난 5주 간 독학해온 웹 크롤링법으로 멜론 차트의 음원의 제목, 가수를 출력해본다.

Review

    - 평소에 자주 사용한 음원사이트의 차트 정보를 직접 뽑아보니 재미있었고, 

      앞으로도 다양한 웹사이트에서 정보를 뽑아야 할 때 필요한 스킬을 배워 만족스럽다.

 

Dijkstra Algorithm

     - 그래프에서 정점 간 최단 거리를 찾는 알고리즘  

     

     - 동적계획법의 관점에서 보면, 다익스트라 알고리즘은 도달 방법에서 생겨난

       최단 경로 문제에 대한 동적 계획법 함수적 방정식을 푸는 연속적 근사 계획법이다.

 

     - 시간복잡도 ( 간선 E , 정점 V ) :  O( |E| log|V| )

 

이번 시간에 풀어본 예제

 

1753번: 최단경로

 

처음 생각한 풀이방법 

 

  1 ) 시작점으로부터 도달 가능한 정점에 입력받은 거리 ( 비용 ) 을 체크한다.

  2 ) 도달 가능한 모든 정점에 대해 체크가 끝나면 인접 정점 중 비용이 제일 작은 점으로 이동한다.

  3 ) 1 , 2 를 반복한다.

         - 이 때 기존의 거리 ( 비용 ) 보다 더 적은 거리 ( 비용 ) 이 발견되면 바꿔준다.

  4 ) 모든 정점에 대해 체크가 완료되면 종료한다.

 

 

백준 1753 - 최단거리 구하기

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

class Node implements Comparable<Node> {
	int end, weight;

	public Node(int end, int weight) {
		this.end = end;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		return weight - o.weight;
	}
}

public class Main {
	private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	private static Scanner sc;
	private static int INF = 100000000;
	static int e, v, start;
	static List<Node>[] list;
	static int[] dijk;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		sc = new Scanner(System.in);
		e = sc.nextInt(); // 간선
		v = sc.nextInt(); // 정점
		start = sc.nextInt(); // 시작점
		dijk = new int[v + 1]; // 
		list = new ArrayList[v + 1];
		Arrays.fill(dijk, INF); // 모든 테이블을 INF로 초기화
		for (int i = 1; i <= v; i++)
			list[i] = new ArrayList<>(); // 리스트 초기화
		
		for (int i = 0; i < v; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			// from에서 to로 가는 value 가중치
			list[from].add(new Node(to, value));
		}

		StringBuilder sb = new StringBuilder();
		// 다익스트라 알고리즘
		dijkstra(start);
		// 출력 부분
		for (int i = 1; i < v; i++) {
			if (dijk[i] == INF)
				sb.append("INF\n");
			else
				sb.append(dijk[i] + "\n");
		}
		bw.write(sb.toString());
		bw.close();
		br.close();
	}

	private static void dijkstra(int start) {
		// TODO Auto-generated method stub
		PriorityQueue<Node> queue = new PriorityQueue<>();
		boolean[] check = new boolean[v + 1];
		queue.add(new Node(start, 0)); // 시작점 0 으로
		dijk[start] = 0; // =

		while (!queue.isEmpty()) {
			Node current = queue.poll();
			int cur = current.end;
			if (check[cur] == true)
				continue;

			check[cur] = true;

			for (Node node : list[cur]) { // 도달 가능한 모든 정점들에 대해
				if (dijk[node.end] > dijk[cur] + node.weight) { // 기존 값이 더 크면
					dijk[node.end] = dijk[cur] + node.weight; // 더 작은 새로운 값으로 대체
					queue.add(new Node(node.end, dijk[node.end])); // 바뀐 정점을 큐에
																	// 추가
				}
			}
		}

	}

}

 

 

웹 크롤링 Final - Melon 차트 추출 ! 

Melon

 

 

 1 ) 멜론 차트 홈페이지를 들어가서 F12를 눌러 HTML 창을 연다 . 

 

 2 ) 마우스 클릭으로 찾기를 누르고 , 차트 1위 곡인 밤하늘의 별을 제목 칸을 눌렀다.

 

 3 ) 제목 정보는 div.ellipsis.rank01>span>a 에 들어있는 것을 확인할 수 있다.

 

 4 ) 마찬가지로 가수의 정보도 확인했다. div.ellipsis.rank02>span

      ☆★☆ 처음에 >span>a 로 했을 때 오류가 있었다.

               단체 곡인 경우 가수가 여러 명이더라도 한번에 표기해야되는데 분리하였기 때문.

                     ※ >span 까지 적어야 한다.

               

코드와 출력창

차트 1 위 ~ 100 위 까지의 곡 추출 !