힙 내부 노드에 키를 저장하며 다음 두 가지 속성을 만족하는 이진트리 힙순서 (heap-order): 루트를 제외한 모든 내부노드 v에 대해 key(v) ≥ key(parent(v)) 완전이진트리 (complete binary tree): 힙의 높이를 h라 하면 i = 0, 1, ..., h-1에 대해, 깊이 i인 노드가 2^i개 존재 깊이 h-1에서 내부 노드들은 외부 노드들의 왼쪽에 존재 힙의 마지막 노드 (last node): 깊이 h-1의 가장 오른쪽 내부 노드 힙의 높이 정리: n개의 키를 저장한 힙의 높이는 O(log n) 증명: 완전 이진 트리의 성질을 이용 힙과 우선순위 큐 힙을 사용하여 우선순위 큐(priority queue) 구현 가능 전제: 적정 이진 트리로 구현 마지막 노드의 위치를..
우선순위 큐 ADT 항목(키, 원소)들을 저장 우선순위 큐 ADT 메서드 주요 메서드 insertItem(k, e): 키 k인 원소 e를 큐에 삽입 element removeMin(): 큐로부터 최소 키를 가진 원소를 삭제하여 반환 일반 메서드 integer size(): 큐의 항목 수를 반환 boolean isEmpty(): 큐가 비어 있는지 여부를 반환 접근 메서드 element minElement(): 큐에서 최소 키를 가진 원소를 반환 element minkey(): 큐에서 최소 키를 반환 예외 emptyQueueException(): 비어 있는 큐에 대해 삭제나 원소 접근을 시도할 경우 발령 fullQueueException(): 만원 큐에 대해 삽입을 시도할 경우 발령 우선순위 큐를 이용한 정..
이번 프로젝트에서 사용할 DataBase를 선택하기 위해 찾아보고 비교해 보았다! MySQL 가장 널리 사용되고 있는 관계형 데이터베이스 관리 시스템 (RDBMS) 성능과 신뢰성 등에서 꾸준히 개선되어 옴 오픈 소스이며 다중 사용자와 다중 스레드를 지원, 여러 프로그래밍 언어를 위한 API 제공 다양한 운영체제에서 사용 가능 오픈 소스 라이센스를 따르지만, 상업적으로 사용할 때는 상업용 라이센스를 구입해야 함 MariaDB MySQL 데이터베이스 시스템을 기반으로 한 서비스 MySQL의 개선된 버전으로 호환성이 높음 MySQL에서 찾을 수 없는 수많은 내장된 강력한 기능과 많은 유용성, 보안 및 성능 개선사항이 함께 제공 MySQL에 비해 확장성이 뛰어나고 쿼리 속도가 더 빠름 MySQL vs Maria..
Dictionary 인덱스를 숫자가 아닌 문자열, 튜플을 사용하려 할 때 빠른 접근/탐색이 필요할 때 집계가 필요할 때 (원소의 개수를 세는 문제) Dictionary와 list의 시간 복잡도 차이 Operation Dictionary List Get Item O(1) O(1) Insert Item O(1) O(1) ~ O(N) Update Item O(1) O(1) Delete Item O(1) O(1) ~ O(N) Search Item O(1) O(N) 원소를 넣거나 삭제, 찾는 일이 많을 때에는 딕셔너리를 사용 Dictionary 생성 # 빈딕셔너리 생성 dict1 = {} # {} dict2 = dict() # {} Dictionary 원소 가져오기 # [] 기호 사용해 원소 가져오기 dict =..
문제 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 number k return "1924" 2 "94" "1231..
input() vs sys.stdin.readline() input() 매개변수로 prompt message를 받음 (입력을 받기 전 prompt message를 출력) 입력받은 값의 개행 문자 삭제시키고 반환 sys.stdin.readline() 한 줄 단위로 입력받음 (개행 문자 포함) 개행 문자 "\n"를 같이 입력받음 개행 문자에 대한 문자열 처리 필요 int()로 형변환을 해준다면 개행 문자는 사라지고 정수 형태만 남음 strip() 문자열 맨 앞과 맨 끝의 공백 문자 제거 sys.stdin.readlin().strip() 으로 사용 if) 입력 한 줄이 "011294/n" 로 주어질 때 (공백으로 분리되지 않은 정수) 문자열 끝의 공백 문자를 제거하기 위해 strip 사용 import sys ..
Virtual Memory Background Demand Paging Copy-on-Write 프로세스끼리 메인 메모리를 공유하게 하면서 동시에 프로세스 자신만의 데이터를 저장 Page Replacement Allocation of Frames Thrashing 요구하는 페이지가 메인 메모리에 없어 disk로부터 불러오고, 불러오는 페이지의 공간을 마련하기 위해 이전 페이지를 disk에 저장하는 page fault가 자주 발생하는 것 Memory-Mapped Files Allocating Kernel Memory Other Considerations Operating-System Examples Objectives virtual memory system의 이점을 설명 demand paging, page..
문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 ..
문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올..
문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109..
