자료구조 - 이분 그래프(Bipartite Graph) 관련 글 그래프 관련 글은 여기를 참조 그래프 탐색 - BFS는 여기를 참조 그래프 탐색 - DFS는 여기를 참조 1. 이분 그래프 이분 그래프는 그래프 형태의 자료구조인데 정점을 2그룹으로 나눌 수 있으되 같은 그룹의 정점끼리는 간선으로 이어지지 않은 경우를 의미한다. 즉 아래의 그림처럼 된 경우가 그러하다. 위의 그림에서 보다시피 빨간색, 파란색의 정점으로 두 그룹으로 나뉘었다. 그러나 빨간색 끼리는 인접하지 않았고, 파란색 끼리도 인접하지 않았다. 위와 같은 형태의 그래프가 형성될 때 이분 그래프(Bipartite Graph) 라고 한다. 참고로 간선이 아예 없고 정점만 있는 경우도 이분 그래프이다! 이분 그래프는 현실에서 굉장히 많이 쓰이는 중요한 그래프이다. 주요 예시는 다음과 같다. 학생 - .. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 접미사 배열(Suffix array, 맨버-마이어스 알고리즘) 1. 접미사 배열 접미사 배열은 문자열 형태의 데이터가 갖는 모든 접미사를 사전 순 정렬한 것을 의미한다. 접미사 배열은 문자열 검색, 전문 검색 등에 활용하기 위해서 많이 쓰인다. 접미사 배열로 검색하면 아래와 같은 예시를 가장 많이 볼 수 있다. 이를 통해 간단히 이해해보자. 기존 배열(original array) 접미사 배열(suffix array) banana a anana ana nana anana ana banana na na a nana 이해하기 어렵지 않다. banana 라는 문자열의 모든 접미사는 자기 자신을 포함해, 뒤에서 부터 한 글자씩 잘라낸 부분이라고 보면 된다. 위의 표를 보면 좌측의 기존 접미사를 저장한 배열이 정렬 후 우측과 같이 정렬 상태가 됨을 알 수 있다. 이제 보니, .. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 8 (Topological) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 1. Topological Sort(위상 정렬) 위상 정렬은 순서가 있는 작업을 해야할 때 그 순서를 임의로 설정할 수 있도록 정렬하는 알고리즘이다. 예를 들어서 A라는 작업을 한 뒤에 B라는 작업을 해야한다고 생각하자. 그 경우, 작업 순서는 A → B 가 될 것이다. B → A는.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 7 (Bucket) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 1. Bucket Sort(버킷 정렬) 버킷 정렬은 전체 데이터가 특정 범위 안에 균등하게 분포되어 있다는 가정을 할 수 있을 때 매우 유용하게 쓰일 수 있는 정렬 알고리즘이다. 예를 들어, 전체 데이터가 0.0 이상 1.0 미만의 범위 안에 있는데 이 데이터가 매우 소수점.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 6 (Radix) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Radix Sort (기수 정렬) 이전의 버블 / 선택 / 삽입 / 병합 / 퀵 정렬 등은 모두 값을 비교함으로써 정렬을 수행하게 되고 이는 아무리 좋은 성능을 낼지라도 평균적으로 O(nlogn)보다 더 빠르게 수행할 수는 없다. 그런데, 이전의 Counting Sort(.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 5 (Counting) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Quick 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Counting Sort(계수 정렬) 간단하게 그림으로 이해할 수 있는 자료는 다음과 같다. 혹은 이를 간단하게 테스트해볼 수 있는 웹 페이지 링크도 있다. 여기를 들어가서 확인. 계수 정렬의 특징은 다음과 같다. 특성 설명 Not In-place 알고리즘 배열을 나누는 과정에.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
자료구조 - 정렬 4 (Quick) 전체 정렬 개요의 설명은 여기를 참조 Bubble / Selection / Insertion 정렬의 설명은 여기를 참조 Shell 정렬의 설명은 여기를 참조 Merge 정렬의 설명은 여기를 참조 Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조 Counting 정렬의 설명은 여기를 참조 Radix 정렬의 설명은 여기를 참조 Bucket 정렬의 설명은 여기를 참조 Topological 정렬의 설명은 여기를 참조 Quick Sort(퀵 정렬) 이름만 봐도 매우 빠르게 동작할 것 같다. 우선 애니메이션으로 한 번 살펴보자. 퀵 정렬은 영국의 Computer Scientist인 Tony Hoare 가 고안한 방식이다. 위의 애니메이션에서 주목할 점은 Pivot이라는 문구이다. 이 Pi.. 자바 프로그래밍/자료구조(Data Structure) 4년 전
