나작코

이진 힙(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까지..

문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸. 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 제한사항 n은 1 이상, 2000 이하인 정수입니다. 입출력 예 n result 4 5 3 3 class Solution { public long solution(..

유효성 검사(validation)란 입력 내용이 요건에 만족하는지 그 타당성을 확인하는 입력 체크를 말합니다. 크게 두 개로 나뉘는데, 단일 항목 검사와 상관 항목 검사가 있습니다. 단일 항목 검사란 입력 항목 하나에 대해 설정하는 입력 체크 기능입니다. Form 클래스 등의 필드에 어노테이션을 부여해서 사용합니다. 상관 항목 검사란 여러 필드에 대해 혼합해서 체크하는 것을 말합니다. 상관 항목 검사를 수행하는 방법에는 두 가지가 있습니다. Bean Validation을 사용하는 방법과 스프링 프레임워크에서 제공하는 Validator 인터페이스를 구현하는 방법입니다. Validator 인터페이스를 구현하기 위해서는 커스텀 유효성 검사기를 주입하고 WebDataBinder 인터페이스의 addValidato..

문제 설명 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가..