알고리즘
-
[JAVA] 자료구조 Heap & Heap sort (힙 & 힙 정렬) + 구현알고리즘/개념 정리 2024. 2. 23. 18:00
Heap 자료구조 란? - 데이터에서 최댓값 과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 시간 복잡도 : O(logN) 이진 트리의 개념 - node : 각각의 값을 노드라고 부름 - root : 뿌리 노드, 레벨 0, 가장 최상단 노드로 부모 노드가 존재하지 않는 노드 - parent node : 부모 노드, 아래에 자식 노드를 가지고 있는 노드 - child node : 부모 노드로 뻗어나온 하위 노드 완전 이진 트리의 일종으로, 왼쪽으로부터 자료구조를 채워나가는 형태 오른쪽은 비어있는 경우가 있을 수 있음 1차원 배열로 나타낼 수 있음 -> 정렬이 가능한 이유 배열로 구현 시에, 인덱스 1로 시작하는 것으로 구현하면 편리함 (0으로 시작해도 무관) 중복 값 허용 (부모 노드의 인덱스) = ..
-
[백준(JAVA)] 1676 : 팩토리얼 0 의 개수 - BigInteger알고리즘/백준 - JAVA 2023. 11. 29. 20:00
https://www.acmicpc.net/problem/1676 문제 풀기 전 팩토리얼 500이 얼마나 큰 숫자일지 가늠해보기 위해서 웹 상에 있는 팩토리얼 계산기를 통해 확인해보았다 대략적으로만 봐도 21억 (int 형의 표현 범위 약 ±21억) 은 기본으로 넘는 숫자인걸 확인할 수 있다 아무리 봐도 int 형에는 담기지 않을 것 같아서 long 형으로 구현을 시도해보았으나 long 형 또한 20! 이후로는 계산 값이 정확히 나오지 않았다 따라서 더 큰 수를 담을 수 잇는 자료형을 확인하기로 했다 BigInteger 클래스 java.math 패키지의 BigInteger 클래스 API 문서의 앞 부분을 읽어보면, 불변의 임의의 정밀도 정수 모든 연산들은 마치 BigInteger 가 자바의 원시 int ..