나작코

원형 연결 리스트(Circular Linked List)란 마지막 노드가 첫 노드와 연결된 단순 연결 리스트입니다. 마지막 노드의 레퍼런스가 저장된 last가 단순 연결 리스트의 head와 유사한 역할을 합니다. 여러 사람이 차례로 돌아가며 하는 게임을 구현하는 데 적합한 자료구조이며, 많은 사용자가 동시에 사용하는 컴퓨터에서 cpu 시간을 분할하여 작업에 할당하는 운영체제에도 쓰입니다. 이항 힙이나 피보나치 힙과 같은 우선순위 큐를 구현하는 데에도 원형 연결 리스트가 부분적으로 사용됩니다. 삽입이나 삭제 연산 각각 상수 개의 레퍼런스를 갱신하므로 O(1)시간에 수행됩니다. 탐색 연산은 단순 연결 리스트의 탐색과 같이 last로부터 노드들을 순차적으로 탐색해야 하므로 O(n) 시간이 소요됩니다. 원형 연..

이진 탐색(Binary Search)이란 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법입니다. 데이터가 정렬되지 않은 상태라면 진행할 수 없습니다. 찾고자 하는 값과 데이터 중앙에 있는 값을 비교합니다. 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서, 더 크면 데이터 오른쪽 부분에서 이진 탐색을 진행합니다. 알고리즘 시간 복잡도는 O(log n)입니다. 단점으로는 데이터의 삽입과 삭제가 빈번하면 정렬을 유지하기 위해 시간이 오래 걸린다는 점입니다. 1회의 삽입이나 삭제 연산 수행 시 최악의 경우 O(n) 시간이 소요됩니다. 이진 탐색 구현 코드(반복문) public static int binarySearch(int[] array, int target) { int left = 0; int r..

문제 설명 문자열 s는 한 개 이상의 단어로 구분되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요. 제한사항 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야 합니다. 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다. 입출력 예 s return "try hello world" "TrY HeLlO WoRlD" import java.lang.StringBuilder; class Solution { public String solution(String s) { s = s.toLowerCase(); St..

셸 정렬(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 ..