전체 글
-
[PS] 1007) 벡터매칭백준 PS 2022. 10. 20. 15:53
https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net Gold2) 1007.벡터매칭 수학, 브루트포스 알고리즘 문제를 잘못 읽어서 돌고 돌아 AC를 받은 문제. 요구 사항은 복잡하지 않아 쉽게 해결방법을 떠올릴 수 있었다. 주어진 모든 점을 각각 한 번씩 사용하여 벡터를 구성하고 구성한 벡터들의 벡터합을 구하여 벡터의 크기를 출력하면 된다. 이때, 주어진 점에 대해 구성할 수 있는 벡터들이 정해져 있지 않으므로 브루트포스 알고리즘을 사용하여..
-
[자료구조] 힙(Heap)자료구조 2022. 10. 20. 15:12
힙(Heap) 기본 지식 반정렬 상태의 Binary Tree 사용 이유 값을 추가/삭제 하면서 정렬 상태를 유지 ( 추가/삭제의 시간 복잡도 O(logN) ) Linked List나 배열은 값을 추가하고 재정렬 시 기본적으로 O(N) 소요 우선순위 큐(Priority Queue) -> 기본적인 Queue 자료구조 + 순위 Max heap ( 부모 노드 >= 자식 노드 ) 최대값 Searching Min heap ( 부모 노드 배열로 구현 가장 상위 부모 노드인 root node 부터 배열에 저장 Tree 구조의 부모,자식 관계 -> Binary Tree 구조(각 Level의 노드 개수 = 2^n개)를 고려해보면 알 수 있음 왼쪽 자식 노드 Index = 부모 Index * 2 오른쪽 자식 노드 Index..