2021.11.21 (SUN)
계속해서 채워넣자
다들 비전공자이고 다들 처음 접하는거다. 누구만 못따라가는 것이 아니다. 다들 출발선이 똑같다. 똑같이 느리다.
v : 버텍스vertex, e : 엣지edge
* 이분 그래프 1707
이분 그래프: "특정 Node의 인접 Node 들끼리는 서로 직접 연결된 Edge가 없다" 조건을 모든 노드들이 만족할 때, 이 그래프를 이분 그래프라고한다. A의 인접 노드 B, C가 있을 때 B와 C는 인접하지않아야한다.
이분 그래프는 인접 리스트, 인접 행렬을 통해서 표현할 수 있다.
인접 행렬은 2차원 배열 adj를 만들었을때 1번 노드와 2번 노드가 인접하면 adj[1][2], adj[2][1] 를 true 값으로 표현(혹은 다른 방식으로)하는 방식이다.
이 방식은 특정 노드가 어떤 노드와 인접하는 지 확인할 때는 O(1)의 시간 복잡도를 가지지만 특정 노드의 모든 인접 노드를 확인하려면 O(V) (V는 노드 수) 만큼의 시간복잡도를 가진다. 또한 간선이 없는 경우에도 공간을 써야하므로 공간 복잡도 측면에서도 효율성이 떨어진다.
인접 리스트는 각 정점의 인접 노드들을 리스트 형식으로 표현한다. 이 방식은 특정 노드가 어떤 노드와 인접하는지 알고싶으면 그 노드의 인접 노드를 모두 검사해야하므로 O(V)의 시간복잡도를 가진다.
대신 모든 노드를 확인할 때는 O(E) (E는 간선의 수)만큼의 시간 복잡도를 가지고 공간 복잡도 측면에서도 행렬 표현보다 유리하다.
이 문제는 각 정점들의 인접 노드들을 모두 탐색하며 그 인접 노드들이 서로 다시 인접하는지(같은 색상인지) 체크해야하므로 인접 리스트를 사용하는 것이 효율적이다. [출처 유튜브 댓글]
.
.
DFS
11725 트리의 부모 찾기
- 무슨 원리로 부모노드가 뽑히는 건지?
-> 일반적으로 합치기 연산을 수행할 때 -> 더 큰 루트노트가 더 작은 루트노트를 가리키도록 만들어서 테이블을 가리키도록 관행처럼 사용됨.
=> (1, 4) 이면 4가 더 크니까 4가 1을 가리켜서 1을 부모노드로. / (2, 3)이면 2가 3의 부모노드. 더 작은 숫자가 부모노드가 됨
.
.
1707 이분 그래프
완벽하게 이해하고 싶어서... 오래걸림
- BFS로 풀이시 : 큐 사용 할 때 대부분 visit / need_visit(visited) 두 개 리스트를 만들어서 팝하고 체크하는 식으로 시작하는 듯
하
코드랑 글만 보고 이해하려니 속도가 너어무 느려서 시간을 많이 썼다
결국 인강 몇 개 찾아 듣고 바로 이해 완~
