나작코

AVL 트리란 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진 탐색 트리를 의미합니다. 트리에 노의 삽입이나 삭제로 인해 균형이 깨졌을 때, 회전 연산을 통하여 트리의 균형을 유지합니다. 왼쪽과 오른쪽 서브트리의 높이 차이가 2 이상일 때 불균형이 발생했다고 합니다. AVL 트리에서 삽입 또는 삭제 연산을 수행할 때 트리의 균형을 유지하기 위해 LL, RR, LR, RL 회전 연산이 사용됩니다. 각 회전 연산은 두 종류의 기본적인 연산으로 구현되는데, 오른쪽으로 회전하는 rotateRight와 왼쪽으로 회전하는 rotateLeft입니다. AVL 트리에서의 삽입과 삭제 구현 코드 class Node { int key; int height; Node left; Node ri..

문제 설명 문자열 my_string과 이차원 정수 배열 queries가 매개변수로 주어집니다. queries의 원소는 [s, e] 형태로, my_string의 인덱스 s부터 인덱스 e까지를 뒤집으라는 의미입니다. my_string에 queries의 명령을 순서대로 처리한 후의 문자열을 return 하는 solution 함수를 작성해 주세요. 제한사항 my_string은 영소문자로만 이루어져 있습니다. 1

문제 설명 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요. 제한사항 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다. 곱할 수 있는 배열만 주어집니다. 입출력 예 arr1 arr2 return [[1, 4], [3, 2], [4, 1]] [[3, 3], [3, 3]] [[15, 15], [15, 15], [15, 15]] [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] class So..

이진 탐색 트리(Binary Search Tree; BST)란 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조입니다. 이진 탐색을 수행하기 위해 단순 연결 리스트를 변형시킨 것입니다. 이진 탐색은 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법입니다. 각 노드 n에 저장된 키가 n의 왼쪽 서브트리에 있는 노드에 저장된 키보다 크고 n의 오른쪽 서브트리에 있는 노드의 키보다 작은 것이 이진 탐색 트리의 조건입니다. 각각의 서브 트리도 이진 탐색 트리를 유지하면서 중복된 키를 허용하지 않습니다. 특징 중 하나는 트리를 중위 순회(Inorder Traversal)하면 오름차순으로 정렬된 출력을 얻을 수 있다는 점입니다. 또 균형이 유지된 이진..

문제 설명 문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다. 예를 들어, s = "banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다. b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. n는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다. n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다. a는 자신보다 두 칸, 네 칸 앞에 a가..

문제 설명 문자열 "hello"에서 각 문자를 오른쪽으로 한 칸씩 밀고 마지막 문자는 맨 앞으로 이동시키면 "ohell"이 됩니다. 이것을 문자열을 민다고 정의한다면 문자열 A와 B가 매개변수로 주어질 때, A를 밀어서 B가 될 수 있다면 밀어야 하는 최소 횟수를 return 하고 밀어서 B가 될 수 없으면 -1을 return 하도록 solution 함수를 완성해보세요. 제한사항 0 < A의 길이 = B의 길이 < 100 A, B는 알파벳 소문자로 이루어져 있습니다. 입출력 예 A B result "hello" "ohell" 1 "apple" "elppa" -1 "atat" "tata" 1 "abc" "abc" 0 import java.lang.StringBuilder; class Solution { p..

이진 트리(Binary Tree)는 각 노드의 자식 수가 2 이하인 트리를 의미합니다. 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능하게 하며, 이진 트리의 서브트리를 다른 이진 트리의 서브트리와 교환하기가 쉽습니다. 이진 트리에는 두 종류의 특별한 형태를 가진 트리가 존재합니다. 모든 이파리의 깊이가 같고 각 내부의 노드가 2개의 자식을 가지는 포화 이진 트리(Perfect Binary Tree)와 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 완전 이진 트리(Complete Binary Tree)입니다. 완전 이진 트리를 저장하기 위해 배열을 사용하는 경우, 레퍼런스를 저장할 메모리 공간이 필요 없으므로 매우 효율적입니다...

문제 설명 소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다. 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다. 두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return 하도록 solution 함수를 완성해주세요. 제한사항 a, b는 정수 0 < a 1) { answer = 2; } return answer; } } 분수를 기약 분수로 만들기 위해서는 최대 공약수를 알아야 합니다. 이를 구하기 위해 매개 변수 A와 B를 받는 gcd 메소드를 생성합니다. if문에서 A를 B로 나눈 나머지가 ..

문제 설명 정수 배열 arr와 query가 주어집니다. query를 순회하면서 다음 작업을 반복합니다. 짝수 인덱스에서는 arr에서 query[i]번 인덱스를 제외하고 배열의 query[i]번 인덱스 뒷부분을 잘라서 버립니다. 홀수 인덱스에서는 arr에서 query[i]번 인덱스는 제외하고 배열의 query[i]번 인덱스 앞부분을 잘라서 버립니다. 위 작업을 마친 후 남은 arr의 부분 배열을 return 하는 solution 함수를 완성해 주세요. 제한사항 5

트리(Tree)란 실제 트리를 거꾸로 세워 놓은 형태의 자료구조입니다. 노드와 링크로 구성되어 있습니다. 하나의 노드에서 다른 노드로 이동하는 경로가 유일하며, 모든 노드는 서로 연결되어 있습니다. 배열이나 연결 리스트는 데이터를 일렬로 저장하기 때문에 일반적으로 탐색 연산이 순차적으로 수행되어야 한다는 단점을 가집니다. 트리는 이러한 문제점을 보완하여 다양한 형태로 광범위하게 응용됩니다. 일반적인 트리(General Tree)는 HTML과 XML의 문서 트리, 자바 클래스 계층구조, 운영체제의 파일 시스템, 탐색 트리, 이항 힙, 피보나치 힙과 같은 우선순위 큐에서도 사용됩니다. 이를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스를 저장해야 합니다. 따라서 트리 노드의 최대 차수가 k라면,..