나작코

우선순위 큐(Priority Queue)란 가장 높은 우선순위를 가진 항목에 접근하거나 삭제하는 연산과 임의의 우선순위를 가진 항목을 삽입하는 연산을 지원하는 자료구조입니다. 스택이나 큐도 일종의 우선순위 큐로, 스택의 경우 가장 마지막으로 삽입된 항목이 가장 높은 우선순위를 가지며, 최근 시간일수록 높은 우선순위를 부여하는 우선순위 큐입니다. 큐의 경우 먼저 삽입된 항목이 우선순위가 더 높습니다. 따라서 이른 시간일수록 더 높은 우선순위를 부여하는 우선순위 큐입니다. 우선순위 큐는 배열, 연결 리스트, 힙을 이용하여 구현할 수 있습니다. 정렬된 배열과 연결 리스트에서의 삽입과 삭제의 시간 복잡도는 각각 O(N)과 O(1)입니다. 그러나 힙의 경우에는 각각 O(logN)이므로 일반적으로는 힙 자료구조가 ..

문제 설명 영어 점수와 수학 점수의 평균 점수를 기준으로 학생들의 등수를 매기려고 합니다. 영어 점수와 수학 점수를 담은 2차원 정수 배열 score가 주어질 때, 영어 점수와 수학 점수의 평균을 기준으로 매긴 등수를 담은 배열을 return 하도록 solution 함수를 완성해주세요. 제한사항 0

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5……. 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5……. 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5……. 1번 문제부터 마지막 문제까지 정답이 순서대로 들은 배열 answer가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제..

이진 힙(Binary Heap)이란 완전 이진 트리로서 부모의 우선순위가 자식의 우선순위보다 높은 자료구조입니다. 다른 트리 자료구조와 다르게 중복 값을 허용합니다. 각 노드에 대해 부모의 우선순위가 자식의 우선순위보다 높은 것을 힙 속성(Heap Property)이라 합니다. 이진 힙에는 키가 작을수록 높은 우선순위를 가지는 최소 힙(Minimum Heap)과 클수록 더 높은 우선순위를 가지는 최대 힙(Maximum Heap)이 있습니다. 최솟값 또는 최댓값을 빠르게 찾아내는 데 유용합니다. 그러나 형제 노드 간 우선순위 보장이 없으므로 반 정렬 상태입니다. 최소 힙 삽입과 삭제 구현 코드 import java.util.ArrayList; class MinHeap { ArrayList heap; pub..

문제 설명 철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4]로 원형 수열을 만들면 다음과 같습니다. 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다. 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 3

문제 설명 코니는 매일 다른 옷을 조합하여 입는 것을 좋아합니다. 예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다. 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다. 코니는 하루에 최소 한 개의 의상은 입습니다. 코니가 가진..

해시 테이블(Hash Table)이란, 키와 값을 대응시켜 저장하는 데이터 구조입니다. 키를 배열의 인덱스로 그대로 사용하면 메모리 낭비가 심해질 수 있습니다. 해시 테이블에서는 이러한 문제를 해결하여 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장합니다. 이를 해싱(Hashing)이라고 합니다. 해싱에 사용되는 함수를 해시 함수(Hash Function), 해시 함수가 계산한 값을 해시값(Hash value) 또는 해시 주소라고 합니다. 배열을 이용하여 해시 테이블 직접 구현한 코드 class HashTable { Integer[] table; int elementCount; HashTable() {} HashTable(int size) { this.table = new I..

문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n 편 중 h 번 이상 인용된 논문이 h 편 이상이고 나머지 논문이 h 번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편 이상, 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 입출력 예 citations ..

문제 설명 머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls 개의 구슬 중 share 개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 1

레드 블랙 트리(Red-Black Tree)란 노드에 각 색을 부여하여 트리의 균형을 유지하며 탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(logn)을 넘지 않는 매우 효율적인 자료구조입니다. 일반적으로 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점이 있습니다. 그러나 좌편향 레드 블랙(Left-Leaning Red-Black; LLRB) 트리는 삽입이나 삭제 시 고려해야 하는 경우의 수가 적으며, AVL 트리, 2-3 트리, 2-3-4 트리, 일반 레드 블랙 트리보다 매우 우수한 성능을 보입니다. LLRB 트리는 다음의 조건을 만족합니다. 루트와 null은 블랙 루트로부터 각 null까지 2개의 연속된 레드 link는 없음 루트로부터 각 null까지..