heap
-
[Algorithm] - HEAP(우선 순위 QUEUE)Algorithm/Algorithm 2022. 9. 1. 16:56
Heap - 우선 순위 Queue Pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 , 우선 순위가 가장 높은 원소가 나온다. 원소의 추가 O(LogN) 우선 순위 높은 ITEM 확인 O(1) 우선 순위 높은 순서 제거 O(LogN) 이진 검색 트리와 Heap 은 다른 자료 구조다. import heapq BOJ 1715번 - 카드 정렬하기 IDEA 1. 작은 값 2개 값을 더하는게 최소의 경우이다. ( GREEDY ) -> 작은 값을 더하지 말고 다른 값을 더하였을 경우보다 더 작은 경우가 발생 불가능! 2. 수의 범위가 1000일 때, 10만개인 경우에 INT형의 범위를 벗어나는가? -> INT형의 범위를 벗어나지 않아 별도로 생각하지 않아도 된다. 3. 예외 처리 1개만 들어온 경우는 최소..
-
[BOJ] 2170번 - 선 긋기Algorithm/BOJ 2022. 6. 11. 13:56
[BOJ] 2170번 - 선 긋기 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 주의할 점이 선을 긋는다고 하여 0부터 시작하는 것이 아닌 음수부터 시작이 된다 및 여러 번 그은 부분이나 한번 그은 부분이나 동일하게 계산되어야 한다. 알고리즘 그리디 알고리즘을 이용하여 풀었다. 시작점이 작은 좌표부터 시작하여 가장 긴 값을 찾아가는 형태로 찾아가면 최소 최대 길이를 구할 수 있다. 최소 값을 갱신하면서 찾아야 하기..
-
[BOJ] 1520번 내리막 길Algorithm/BOJ 2022. 6. 10. 13:07
[BOJ] 1520번 내리막 길 처음에는 DP와 BFS로 푸는 문제로 접근하였다. 생각하였던 예시 중에서는 올바르게 동작하였으나, 제출 시 시간 초과가 걸려 실패하였다. 왜 그런지 곰곰히 생각해보던 도중 BFS로 구현을 하게 되면 순차적으로 탐색을 하게 되어 돌아서 가는 경우에 대해서 갱신하여 처리하기 어렵다. 따라서 어차피 숫자 가중치에 따라 더 큰것부터 우선으로 찾아 들어가야하기 때문에 BFS의 Queue를 우선순위 Queue로 구현해볼까라고 생각하였다. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는..
-
DB INDEXCS/DB 2022. 2. 28. 00:58
개발을 하면서 생각보다 조회 자체로도 서버 부하에 큰 영향을 준다는 점을 알았습니다. 테스트 서버와 달리 실서버 수십만건의 결제 데이터 조회 시 서버에 부하를 일으켰습니다. 기존 서비스들이 무분별한 확장만 추구하였을 뿐 어느 누구도 서비스의 질을 생각하지 않아 속도가 느려지며 부하가 발생하여 데드락이 발생하여 점점 서비스에 영향이 갔습니다. PAGE란? 데이터 파일을 구성하는 논리 단위 SQL Server의 기본 데이터 저장 단위(8KB) 데이터를 쓸 때 행을 페이지에 기록됨 데이터를 읽을 때 페이지 내의 모든 행이 읽어짐 페이지 내의 행이 많을 수록 I/O 효율 증가 INDEX란? 추가적인 쓰기 작업과 저장 공간을 활용하여 DB 테이블의 검색 속도를 향상시키기 위한 자료구조 장점 빠른 데이터를 검색 (..