[자료구조] 그래프 (Graph)
그래프 (Graph) 노드(Node, Vertex), 간선 (Edge)의 집합 객체 사이의 연결 관계를 표현하는 자료구조 가장 표현력이 우수한 자료구조로, 현실세계의 다양한 문제를 효과적으로 모델링하는 목적 트리는 계층구조가 아닌 일반적인 관계는 나타낼 수 없다는 한계를 지님 그래프 종류 구분 종류 설명 간선의 방향성 무방향 그래프 방향X 방향 그래프 방향O 간선의 가중치 가중 그래프 간선에 가중치 할당 구조적 특징 완전 그래프 연결 가능한 최대 간선 수 가짐 부분 그래프 원래 그래프의 일부분 다중 그래프 중복된 간선 포함 1. 무방향 그래프 간선에 방향이 없는 그래프 노드 : V(A) = { A, B, C, D, E} 간선 : G(A) = {(A,B), (B, D), (C,D), (D,E), (..
2020. 9. 15.
[알고리즘] 순위 (프로그래머스 Level3)
코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 그래프 탐색 문제이다. 순위라고 했으므로 현재 그래프 내에서의 각 노드들의 위치를 알아내야 하는 문제이다. 즉, 각 선수마다 해당 선수보다 강한 선수 + 약한 선수의 수를 구해서 합쳐서 n이 된다면 랭킹을 정확하게 구할 수 있는 선수이다. 예전에도 비슷한 문제를 풀어본 기억이 있는데 'DFS + 역그래프 + DP + Set'을 적절히 활용하면 쉽게 풀 수 있다. Solution 예시 input을 단방향 그래프로 그린 모습이다. 보다시피 2번 선수 뒤에는 1, 3, 4번, 앞에는 5번 선수가 있으므로 다른 모든 선수와의 관계를 명확히 할 수 있다. 5번 또한 본인 뒤에 ..
2020. 9. 7.
