CS/자료구조

[자료구조] 이분그래프 (Bipartite Graph)

이분그래프란? 2가지 특성으로 나눌 수 있는, 이분되어 있는 그래프 vertex를 2개의 그룹으로 나눌 수 있는데, 같은 그룹의 vertex끼리는 인접할 수 없는 그래프 특징 하나의 edge의 양 끝 vertex는 서로 다른 그룹에 속해 있어야 함 같은 그룹의 vertex끼리는 하나의 edge로 이어질 수 없음 cycle이 발생했을 때, 그 cycle을 잇는 edge의 개수는 짝수여야 함 edge가 없고 vertex만 있는 경우도 이분그래프 응용 각 그룹에 포함되어 있는 원소끼리의 관계를 나타낼 수 있다 학생 - 수업 : 학생들이 어떤 수업을 듣고 있는지, 각각의 수업을 듣고 있는 학생들은 누군지 관계를 나타낼 수 있다 구직자 - 선호 회사 : 구직자가 어떤 회사를 선호하는지 관계를 나타낼 수 있다 유저..

[자료구조] heap

Heap 최댓값 및 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조 '완전이진트리(completely binary tree)'를 기초로 함 중복된 값을 허용 ( cf. 이진 탐색 트리(binary search tree)는 중복값 허용 x ) A가 B의 부모 노드이면 A의 key 값과 B의 key 값 사이엔 대소관계가 성립 최대힙 - A key 값 > B key 값 최소힙 - A key 값 < B key 값 위 성질로 인해 항상 반정렬 상태가 유지됨 Heap 구현 힙은 보통 '배열'로 구현됨 ( 부모 노드 ) = ( 자식 노드 ) / 2 ( 왼쪽 자식 노드 ) = ( 부모 노드 ) * 2 ( 오른쪽 자식 노드 ) = (부모 노드) * 2 + 1 index 0 1 2 3 4 5 6 7 value x 9 7 ..