[ 그리드 : 신장 트리 스터디]

신장 트리

=> 1. 노드의 개수가 간선의 개수보다 하나가 더 많다. 2. 순환이 (X)
최소 신장 트리를 구하는 대표적인 알고리즘이 그리드 알고리즘이다.
이 알고리즘은 2가지로 다시 나누어서 이야기할 수 있다.
1. 프림 알고리즘, 2. 크루스칼 알고리즘

1. 프림 알고리즘 사용방법

1. 임의의 점점(노드) 하나를 선택하여 최소 신장 트리에 추가한다.
2. 선택한 점점을 기준으로 연결된 것 중에서 가장 작은 가중치가 적은 정점을 신장 트리에 추가한다.
   (순환을 형성하지 않는 정점을 추가한다.) -> 그리드적 선택방법
3. 위의 2번 과정을 신장 트리 조건에 만족할때 까지 반복한다.

프림

탐색방법 : 임의 정점에서 최소 인접 가중치를 가지는 정점을 찾는 방법 ( 확장하는 방식)

크루스칼

탐색방법 : 최소 가중치를 가지는 간선부터 하나씩 추가하는 방식 (가중치를 오름 차순으로 정렬)

완전 탐색 => 데이터를 전부 확인하는 방법을 의미한다. 대표적으로 => 깊이 우선 탐색 및 너비 우선 탐색 방법을 의미한다. 단점으로는 모든 경우의 수를 탐색하는 방법으로 비효율적이다.

: 빠지없이 다 탐색하는거 깊이 너비를

어떤 가능성이 없는 곳을 알아보고 되돌아가는 것을 => 백트래킹이라고 한다. 가능성이 있는 곳을 탐색하는 알고리즘을 "백트래킹 알고리즘"

깊이 우선 탐색은 백트래킹을 활용한것이다.

[1,2,3,4] 중 2개의 숫자를 뽑앟서 합이 6을 초과하는 경우를 알아보자
단 뽑는 순서가 다르면 다른 경우의 수로 간주한다.

• 어떤 특정 조건을 정의하는 것을 -> 유망 함수 라고 한다.

문제] 정수 N을 입력받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환하는 학수 작성
조건] 백트래킹을 이용, 오름차순으로 정렬되어야 한다. (숫자 조합) .같은 숫자는 한번만 선택 가느아
N은 1이상 10이하인 정수

n=2일 경우 [] 빈 배열을 출력

class Solution {

private static ArrayList<ArrayListMInteger>> result;
private static int n;
private static void back(int sum, ArrayList<Integer> selectNum, int start){
	if(sum == 10){
   result.add(selectNum);
   return;
   }

for(int i= start; i <=n; i++){
	if(sum +i <= 10){
   	ArrayList<Integer> list = new ArrayList<>(selectNum);
       list.add(i);
       back(sum + i, list, i+1);
     }
	}
}

private static ArrayList<ArrayList<Integer>> solution(int N){
result = new ArrayList<>();
n = N;
back(0, new ArrayList<>(), i);
return result;
}

프로그래머스 피로도 문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java

class Solution {
    public int answer; // 최대 던전 수
    public boolean[] visited; // 방문 여부 
    
    //k	80
    //dungeons	[[80,20],[50,40],[30,10]]
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        
        dfs(0, k, dungeons);
        return answer;
    }
    
    public void dfs(int depth, int k, int[][] dungeons){
        for(int i = 0; i < dungeons.length; i++){
            if(!visited[i] && dungeons[i][0] <= k){
                visited[i] = true;
                dfs(depth+1, k-dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
         answer = Math.max(answer, depth);
    }
}

• 그래프는 가지를 치는 듯한 느낌을 가지고 있는데 이를 알고리즘에서는 "분기한정" 이라고 이야기 한다.