[항해99]99클럽 코테 스터디 17일차 TIL + 그래프

 

우와 벌써 17일차가 되었네요~~ 오늘은 인프런 강의를 들으며 그래프에 대해 좀 배워봤습니다... 함부로 코드를 구현하지 못하겠더라구요

1.  오늘의 학습 키워드 : 그래프

그래프 : 노트와 엣지로 구성된 집합

노트 : 데이터를 표현 단위 / 에지 : 노드를 연결

트리도 그래프의 일종

1) 유니온 파인드

: 그래프의 사이클이 생성되는지 판별하는 알고리즘

싸이클 유무 판단

2) 위상 정렬

조건 : 사이클이 없어야함 / 방향이 있는 그래프

특징 : 값이 유일하지 않다.

ex) 수강신청( 수1→ 수2) 방향이 있음. / 선아이템이있어야 그 다음 아이템 살 수 있음

→ 전후 관계(방향)이 있는. 싸이클이없음.

선조건 :싸이클ㄴㄴ 방향간선 ㅇㅇ 이때 노드 정렬해주는 알고리즘 → 정렬결과가 꼭 1개 ㄴㄴ 대표적은 수강신청

4) 다익스트라 (4,5,6은 최단거리 알고리즘)

S 라는 시작점이 있고 다른 모든 노드로 가는 최단거리 구하는 알고리즘.

단, 음수간선ㄴㄴ

5) 벨만-포드

얘는 음수간선도 ㅇㅋ

음수싸이클이 있는지? ex)시간여행을 할 수 있냐?

6) 플로이드-워셜

최단거리지만 시작점이 없음. 어떤 노드를 체크해도 둘의 최단거리 구할 수 있음.

근데 시간복잡도가 안좋지. ex)도시간의 최단거리 구해라~ 모든 도시 해라

⇒ 위 세 개는 최단 거리 알고리즘

다 - 시작점 ㅇㅇ 음수간선 ㄴㄴ

벨 - 시작점 ㅇㅇ 음수간선 ㅇㅇ

플 - 시작점 ㄴㄴ 임의의 모든 노드쌍에 대해 최단거리

7) 최소 신장 트리

그래프있고 에지 많을 때, 에지의 가중치가 다 있음. 모든 노드들을 연결하는데 최소 비용으로 간선써서 연결하고 싶은거.

간선의 가중치가 최소가 되게 하는 알고리즘 = MST

이걸 풀 때 유니온 파인드가 필요. 싸이클이 나올 수 없음. 그래서 유니온 파인드를 구현하는게 그 안에 있음.

그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 하는 알고리즘

2.  오늘의 문제 :  Minumum Number Of moves to seat everyone

https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone/

easy문제라 아주 쉬운 문제인데 풀기가 어려웠어요 저는 항상 복잡하게 문제를 풀려고 하는 것 같네

3.  풀이 

class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        int total = 0;
        Arrays.sort(seats); Arrays.sort(students);
        for(int i = 0; i < seats.length; i++){
            total += Math.abs(students[i] - seats[i]);     
        }
        return total;
    }
}

 

 

3.  회고 

https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone/discuss/5304430/Beats-100-Explained-with-Video-C%2B%2BJavaPythonJS-Arrays-Sorting-Interview-Solution

시간복잡도가 3초가 나와서 다른 방법이 없을까 discuss를 봤는데 신기하게 코드를 구현하셨더라고요. 근데 저는 이 코드가 잘 이해가 가지 않네요... 같이 방법을 모색해봅시다..