220301.md

지난 과제 리뷰

• 백준 2458 키순서

  • Problem: 전체 학생 수와 상대적으로 키를 비교한 입력 값이 주어질 떄, 자신의 키가 몇 번째인지 알 수 있는 학생의 수를 출력하는 문제

  • Solution: [수진] - 플로이드-워셜 알고리즘을 통해 입력 값에 해당하는 학생들의 키로 초기화하고, 반복문을 통해 두 학생의 키를 모르는 경우는 탈출 [성범] - 입력값으로 받은 정상 순서와 역순을 각각 이차원 배열에 저장한 후, 플로이드-워셜 알고리즘 진행 -> 정상 순서와 역순을 or연산하여 false가 나오는 것을 걸러낸다.(두 학생의 키를 비교할 수 없는 경우) [기탁] - 플로이드-워셜 알고리즘을 통해 i < j 이면서 j < k 인 경우, i < k 보다 크게 되기 때문에 추가적으로 이차원 배열의 값을 변경(키를 비교할 수 있으면 1 아니면 0을 저장) -> 둘 다 비교할 수 없는 경우(해당 값이 둘다 0)의 학생을 제외한다.

  • Code: 기탁 성범 수진

• 백준 1922 네트워크 연결

  • Problem: 전체 학생 수와 상대적으로 키를 비교한 입력 값이 주어질 떄, 자신의 키가 몇 번째인지 알 수 있는 학생의 수를 출력하는 문제

  • Solution: 크러스컬(Kruskal) 알고리즘의 전형적인 예

  • Code: 기탁 성범 수진

• 백준 15683 감시

  • Problem: 1~5번 까지 CCTV가 탐색할 수 있는 방향이 정해져 있고 벽이 세워진 경우는 CCTV가 감시를 못할 때, CCTV를 돌렸을 때 사각지대가 최소가 나오는 경우를 구하는 문제

  • Solution: DFS를 백트래킹을 통해 CCTV가 확인할 수 있는 모든 경우의 수를 구하여 사각지대의 최소값을 갱신시키도록 구현하는 문제

  • Code: 기탁 성범 수진

그래프 알고리즘 정리

다익스트라 (Dijkstra) 알고리즘

• Greedy 기반 알고리즘
• 인접 리스트 사용
• 한 노드에서 다른 노드까지의 최단 경로를 구해야 할 경우 사용
• 음의 가중치를 가질 수 없음
• 매번 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾기 위해 우선순위 큐(최소 힙) 사용
• 시간 복잡도: O(ElogV)

플로이드 워셜(Floyd-Warshall) 알고리즘

• DP 기반 알고리즘

• 인접 행렬 사용

• 노드 to 노드(모든 노드에 대해서 최소 비용을 구해야 할 경우 사용)

• 시간 복잡도: O(N^3)

  for(int k=0;k<N;k++){ // 1번부터 N번까지의 모든 노드를 비교 탐색
  	for(int i=0;i<N;i++){
  		for(int j=0;j<N;j++){ // i부터 j까지 바로 가는 것과 k를 거쳐 오는 것 중 min 값 비교
  			dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j];
  		}
  	}
  }
  

크러스컬(Kruskal) 알고리즘

• 최소 비용 신장 트리(MST; Minimum Spanning Tree) 찾는 알고리즘
• 최소 비용으로 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 탐색 시 사용
• Union-Find 개념을 사용하여 사이클 유무 판별
• 절차
  1. 모든 edge weight를 오름차순으로 정렬
  2. 정렬된 간선을 순서대로 선택
  3. 선택한 간선의 두 노드가 사이클을 발생시키는지 판별 (find)
  4. 사이클을 발생시키지 않는 간선만 MST 집합에 포함 (union)
• 시간복잡도: O(ElogE)