나작코

셸 정렬(Shell Sort)이란 삽입 정렬의 약점을 보완한 정렬 방식입니다. 삽입 정렬은 오름차순 정렬 기준일 때 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환이 필요합니다. 셸 정렬은 이전의 모든 데이터와 비교하지 않고 일정 간격을 두고 비교합니다. 알고리즘 복잡도는 O(n^2)입니다. 간격 설정에 따라 최악의 경우 삽입 정렬과 동일할 수 있고, 일반적으로는 삽입 정렬보다 빠릅니다. 셸 정렬 구현 코드 public class Main { public static void shellSort(int[] array) { int gap = array.length / 2; for (int g = gap; g > 0; g /= 2) { for (int i = g; i < arra..

문제 설명 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수 solution을 완성해주세요. 제한사항 s는 길이 1 이상 200 이하인 문자열입니다. s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다. 숫자는 단어의 첫 문자로만 나옵니다. 숫자로만 이루어진 단어는 없습니다. 공백문자가 연속해서 나올 수 없습니다. 입출력 예 s return "3people unFollowed me" "3people Unfollowed Me" "for the last week" "Fo..

계수 정렬(Counting Sort)이란 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식입니다. 카운팅을 위한 메모리를 필요로 합니다. 알고리즘 복잡도는 O(n + k)입니다. k는 정렬 대상 데이터 중 최대 값을 의미합니다. 카운팅 테이블은 Array 자료구조로 되어 있습니다. 정렬되지 않은 데이터 10 32 10 27 32 17 99 56 ↓ 2 1 1 2 1 1 [0] […] [10] […] [17] […] [27] […] [32] […] [56] […] [99] ↓ 정렬이 끝난 데이터 10 10 17 27 32 32 56 99 계수 정렬 구현 코드 import java.util.Arrays; public class Main { public static void countingSort(int[]..

이중 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결 리스트입니다. 각 노드에 2개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키어 양방향 탐색이 가능합니다. 이중 연결 리스트는 단순 연결 리스트의 단점을 보완하지만, 노드마다 추가로 1개의 레퍼런스를 저장해야 하는 단점을 가집니다. 이중 연결 리스트에서 수행되는 삽입이나 삭제 연산은 각각 상수 개의 레퍼런스만을 갱신하므로 O(1) 시간에 수행된다. 탐색 연산은 단순 연결 리스트의 탐색과 같이 head 또는 tail로부터 노드들을 순차적으로 탐색해야 하므로 O(n) 시간이 걸립니다. 이중 연결 리스트의 장단점 장점 단순 연결 리스트와 달리, 양방향 탐색 가능 단..

문제 설명 외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 emergency가 매개변수로 주어질 때 응급도가 높은 순서대로 진료 순서를 정한 배열을 return 하도록 solution 함수를 완성해주세요. 제한사항 중복된 원소는 없습니다. 1

기수 정렬(Radix Sort)이란 낮은 자리 수부터 정렬하는 방식입니다. 각 원소 간 비교 연산을 하지 않아 빠른 대신에 기수 테이블을 위한 메모리를 필요로 합니다. 알고리즘 복잡도는 O(dn)입니다. d는 최대 자릿수를 의미합니다. 최악의 경우 원소의 개수보다 최대 자릿수가 더 클 수 있기 때문입니다. 기수 테이블은 queue 자료구조로 되어 있습니다. 정렬되지 않은 데이터 170 45 75 90 2 24 802 66 ↓ 170 90 2 802 24 45 75 66 ↓ 2 802 24 45 66 170 75 90 ↓ 정렬이 끝난 데이터 2 24 45 66 75 90 170 802 기수 정렬 구현 코드 import java.util.ArrayList; import java.util.LinkedList;..

문제 설명 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. 예를 들어 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀면 "a"가 됩니다. 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요. 제한사항 공백은 아무리 밀어도 공백입니다. s는 알파벳 소문자, 대문자, 공백으로만 이루어져 있습니다. s의 길이는 8000이하입니다. n은 1 이상, 25이하인 자연수입니다. 입출력 예 s n result "AB" 1 "BC" "z" 1 "a" "a B z" 4 "e F d" import java.lang.StringBuilder; class Solution ..

퀵 정렬(Quick Sort)이란 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식입니다. 알고리즘 복잡도는 기준 값이 최소값 또는 최대값으로 지정되는 경우에는 O(n^2)입니다. 그러나 평균적으로는 O(n log n)이며, 이보다 더 빠른 경우도 있습니다. 퀵 정렬 구현 코드 public class Main { public static void quickSort(int[] array, int left, int right) { if (left >= right) { return; } int pivot = partition(array, left, right); quickSort(array, left, pivot - 1); quickSort(array, pivot + 1, right);..

단순 연결 리스트(Singly Linked List)란 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조입니다. 즉, 동적 메모리 할당을 받아 노드(Node)를 만들고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결합니다. 노드마다 레퍼런스를 저장할 공간이 필요합니다. 각 노드 객체마다 항목을 저장할 item과 Node 레퍼런스를 저장하는 next를 가집니다. 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않습니다. 크기를 예측하지 않으므로 빈 공간이 존재하지 않습니다. 단순 연결 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵습니다. 이를 보완한 이중 연결 리스트(Doubly Lin..

문제 설명 2차원 좌표 평면에 변이 축과 평행한 직사각형이 있습니다. 직사각형 네 꼭짓점의 좌표 [[x1, y1], [x2, y2], [x3, y3], [x4, y4]]가 담겨있는 배열 dots가 매개변수로 주어질 때, 직사각형의 넓이를 return 하도록 solution 함수를 완성해보세요. 제한사항 dots의 길이 = 4 dots의 원소의 길이 = 2 -256 < dots[i]의 원소 < 256 잘못된 입력은 주어지지 않습니다. 입출력 예 dots result [[1, 1], [2, 1], [2, 2], [1, 2]] 1 [[-1, -1], [1, 1], [1, -1], [-1, 1]] 4 class Solution { public int solution(int[][] dots) { int answe..