본문 바로가기
반응형

전체 글1308

[Jungol] 정올 1190 모두더하기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=473&sca=50 Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com N개의 수가 주어졌을 때 덧셈 연산은 총 N-1번 필요합니다. 더할 때 마다 더하는 두 수를 최소로 해야 하므로 N개의 수들을 계산할 때, 남은 숫자들 중에서 매번 최솟값 2개로해서 더해갑니다. 결국, 매 연산마다 최솟값을 빨리 찾아야 하므로 최소 힙 구조 이용 #.. 2021. 2. 27.
[Jungol] 정올 1570 중앙값 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=843&sca=4020 Approach 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com - 첫 입력을 mid로 중앙값이라고 하자. - 우선순위 큐로 maxpq와 minpq 생성 (각각 최대힙과 최소힙) - 첫 수 이후 들어오는 두 개의 수에 대하여 mid 보다 작으면 maxpq / mid 보다 크다면 minpq에 담습니다. ① 두 pq 크기가 같다면 mid 값 출력 ② maxpq.si.. 2021. 2. 27.
[Jungol] 정올 2082 힙정렬2 (Heap_Sort) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2283&sca=4020 Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com ▶ 최대힙(Max Heap)을 만들어 출력한다. 최대힙 특징 ① 완전 이진 트리(Complete Binary Tree) ② 부모 노드의 값 ≥ 자식 노드의 값 (마지막 노드가 반드시 전체원소의 최소값은 아닙니다. 다만, 단말(leaf) 노드 중에 최소값은 존재.. 2021. 2. 27.
fsck (File System Check) fsck (File System Check) 리눅스 파일 시스템의 경우, 무결성을 검증하기 위해, fsck(file system check)를 지원합니다. fsck는 리눅스 부팅 시에 같이 시작하며, 시스템 내의 모든 로컬 파일 시스템을 검사합니다. fsck의 역할은 리눅스에 마운트 될 파일 시스템의 메타데이터가 실제로 사용할 수 있는 상태인지를 확인하는 것입니다. 리눅스 종료 시 fsck는 모든 캐시 데이터를 디스크에 저장한 뒤 파일 시스템이 문제 없이 언마운트 되었음을 확인합니다. fsck는 마운트 될 파일 시스템을 검사하고 이상 없이 언마운트 되었음을 확인하여 파일 시스템 내부 메타데이터가 정상임을 보증합니다. 하지만 리눅스가 파일 시스템을 정상적으로 언마운트 할 수 없는 경우가 있습니다. 만일 정.. 2021. 2. 27.
저널링 파일 시스템 종류 저널링 파일 시스템 (Journaling File System) 저널링 파일 시스템 (Journaling File System) 저널링 파일 시스템이란? 특별한 데이터 구조체 혹은 데이터 영역에 시스템의 변경 사항들을 기록해 놓고, 이를 참조하여 파일 시스템에 변경 사항을 적용하기 전 변경점들을 추적한다. 이를 통 zoosso.tistory.com 저널링 파일 시스템 종류 ext (eXtended file system): 리눅스 파일 시스템으로 사용, 암호화 지원 X ext2: 리눅스 파일시스템으로 사용 (ext를 대체하기 위해 고안) 서버의 비정상적 종료 후 재부팅시 데이터 손실을 방지하기 위해 FSCK(복구) 명렁어 추가 ext3: 파일 내용 변경 시 파일 시스템과 바로 동기화 작업이 이루어짐 (저널.. 2021. 2. 27.
저널링 파일 시스템 (Journaling File System) 저널링 파일 시스템이란? 특별한 데이터 구조체 혹은 데이터 영역에 시스템의 변경 사항들을 기록해 놓고, 이를 참조하여 파일 시스템에 변경 사항을 적용하기 전 변경점들을 추적한다. 이를 통해 저널링 파일 시스템은 정상 상태로 빠르게 복구할 수 있으며 내부 데이터의 손상 가능성을 줄인다. ※ 저널링Journaling이란? Stoarge에 데이터 변경 내역을 저장하는 활동 파일 시스템 이란? 파일 시스템은 데이터를 저장, 검색 및 처리하기 위해서 존재합니다. 이를 위해 파일 시스템은 내부의 모든 데이터가 조직화되어 있어야 하고 저장된 데이터들을 액세스 가능한 상태로 관리하는 내부 데이터 구조를 가지고 있어야 한다. 이러한 데이터 관리용 자료구조를 메타데이터(Metadata) 라고 한다. ex) 접근권한, 디스.. 2021. 2. 27.
[Algospot] 알고스팟 RUNNINGMEDIAN 변화하는 중간값 출처: https://algospot.com/judge/problem/read/RUNNINGMEDIAN Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 높은 수를 우선순위로 하는 것과 낮은 수를 우선순위로 하는 것, 총 2개의 우선순위 큐 이용 ※우선순위 큐는 Heap 구조로 이루어져 있으므로 maxHeap, minHeap으로 변수명 설정 새로운 데이터를 입력 받을 때, 조건 [1]. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.. 2021. 2. 27.
[BOJ] 백준 2549 루빅의 사각형 출처: https://www.acmicpc.net/problem/2549 Input 1 2 15 4 7 8 3 6 9 10 5 12 13 14 11 16 Output 2 2 3 3 1 2 2 문제에서 정의한 한번의 움직임은 3가지 움직임을 의미합니다. 1칸 회전 = 2칸 회전 = 3칸 회전 = 한번의 움직임 따라서 매 단계 선택할 수 있는 경우의 수는 → (행 4 + 열 4) * 회전 3가지(1, 2, 3) = 24가지 ※ 회전의 경우 4cylce 주기를 갖고 있음 주어진 회전 횟수는 최대 7번 이므로 247이며, 16개 타일이 맞는 위치에 있는지 확인해야 하므로 → O(247 * 16) = O(73,383,542,784) 완전 탐색으로 이 모든 경우를 구현한다면 TLE 발생 따라서, 전체 경우를 살피는.. 2021. 2. 27.
힙(Heap) 시뮬레이션 ※ [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 배열 인덱스를 통해 쉽게 부모-자식 노드를 알 수 있습니다. if) 시작 인덱스를 1로 두면 다음과 같이 parent와 child 노드 번호 관계식을 갖습니다. → k의 left child 번호 → k × 2 → k의 right child 번호 → k × 2 + 1 → k의 parent 번호 → k / 2 시뮬레이션 (최대 Heap 구성) 부모 노드 < 자식 노드인 관계가 존재하므로 원소 위치를 바꾸어야 합.. 2021. 2. 27.
힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 편향적인 상태를 방지하여 트리의 높이를 항상 일정. - 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상. 부모 자식간의 관계만 중요하기 때문에 왼쪽 자식과 오른쪽 자식에 대해서는 크기 제한 X - 최대값 or 최솟값이 Root에 위치하기에 해당 값을 찾을 시 연산이 효율적. - 최대 힙(Max Heap): 부모노드 값 ≥ 자식 노드 값 - 최소 힙(Min Heap): 부모노드 값 ≤ 자식 노드 값 완선된 Heap은 아래와 같습니다. - Max Heap이므로 Root Node에 위치한 값은 최대값입.. 2021. 2. 27.
반응형

티스토리툴바