목록자료구조, 알고리즘 (4)

라이브러리는 도서관 아닌가요

이분 탐색 ( Binary Search )

주어진 탐색 배열 Q) 찾아야 하는 값 key가 7로 주어졌다. 일단 기본적으로 정렬이 된 배열이 필요하다. low는 1을 가리키는 인덱스 0, high는 17을 가리키는 인덱스 8이다. low와 how의 평균을 내어 가운데를 찍어본다. 9는 찾는 값이 아니다. key인 7보다 크다. 아래 영역으로 탐색하자. high는 9의 인덱스인 4에서 1을 빼서 3이 된다. low는 변경 없으므로 (0+3)/2 = 1이 된다. 인덱스 1의 값 3을 탐색 답이 아니므로 다시 영역을 변경한다. 찾는 값 보다 작으므로 low 값을 +1 올려보자. 아래 영역의 가운데를 찍어본다. key인 7보다 작다. 더 큰 영역으로 탐색하자. 정답을 찾았다. true를 반환한다. 구현적 측면 - 하한과 상한의 평균 값과 키 값을 비교해..
자료구조, 알고리즘 2022. 3. 23. 09:07
크루스칼 알고리즘 (Kruskal Algorithm), MST 최소 신장 트리

오름차순으로 정렬된 엣지를 하나씩 뽑아 노드에 연결되는 엣지로 사용할 것인지를 정하는 것이다. 즉, 두 노드의 루트가 다를 때 작은 값을 가지는 노드를 기준으로 루트를 union한다. 두 노드의 루트가 같다는 것은 하나로 연결이 되어 있다는 뜻이다. (여기서 한 노드의 루트를 찾는 find 메서드(또는 함수)가 필요해진다.) 만약 두 노드의 루트가 같다면, 연결하지 않는다. → 싸이클(Cycle)이 생성될 수 있다. 예시 코드 (백준 BOJ 1922 네트워크 연결) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Priority..
자료구조, 알고리즘 2021. 11. 16. 15:50
Knapsack Algorithm 배낭 문제 정리

가정 최대 무게가 정해진 가방이 있다. 그리고 각기 다른 가치와 무게를 지닌 물건들이 있다. 이 물건들을 가방에 집어넣을 때, 가치가 최대가 되게끔 집어넣는 방법은 어떤 게 있을까? 방법 1. 가능한 모든 경우의 수를 다 세본다. (Brute-Force) 2. 가치가 가장 최대인 물건들만 우선적으로 집어 넣는다. 그리디 (Greedy) 3. DP(Dynamic Programming), 동적 계획법을 사용한다. 진행 3번을 살펴보도록 하고 다음과 같이 가정하자. i == 물건들의 번호이자 넣는 것이 허용되는 범위 (i=4이면, 1, 2, 3, 4번의 물건만 고려한다는 뜻) j == 견딜 수 있는 무게 (j=3이면, 가방 무게를 3으로 한정 짓는다는 뜻) (처음 이렇게 보면 상당히 추상적인데, 2중 for문..
자료구조, 알고리즘 2021. 10. 30. 02:45
우선순위 큐와 힙의 차이

큐(Queue): 먼저 들어오는 데이터가 먼저 나가는 구조 (FIFO - First In First Out) 우선순위 큐(Priority Queue): 우선순위가 높은 데이터가 먼저 나가는 구조 힙(Heap): 루트 노드에 가장 큰 값 혹은 가장 작은 값을 저장하고 있는 완전이진트리 여기서, 우선순위 큐는 일반적으로 힙을 통해 구현한다. 배열, 연결리스트 등으로 구현할 수도 있지만, 최악의 경우 우선순위를 찾기 위해 인덱스의 끝까지 탐색할 수 있기 때문이다. 반면에 힙은 부모 노드, 자식 노드와의 비교만으로 노드의 자리를 찾기 때문에 시간 복잡도가 낫다. - 새 데이터 삽입: O(log2n) - 데이터 삭제: O(log2n) 둘을 비슷하거나 같게 보는 경우가 있는데, 엄연히 말하면 다르다. 추상화하면 우..
자료구조, 알고리즘 2021. 10. 21. 08:07
이전 Prev 1 Next 다음