나작코

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

힙 정렬(Heap Sort)이란 힙 자료구조 형태의 정렬 방식입니다. 기존 배열을 최대 힙으로 구조 변경 후 정렬을 진행합니다. 알고리즘 복잡도는 O(n log n)입니다. 힙 정렬 구현 코드 public class Main { public static void heapSort(int[] array) { for (int i = array.length / 2 - 1; i >=0 ; i--) { heapify(array, i, array.length); } for (int i = array.length - 1; i > 0; i--) { swap(array, 0, i); heapify(array, 0, i); } } public static void heapify(int[] array, int parentIn..

문제 설명 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수입니다. 입출력 예 n result 45 7 125 229 class Solution { public int solution(int n) { int answer = 0; while (n > 0) { answer = answer * 3 + n % 3; n /= 3; } return answer; } } while문은 n이 0보다 클 때 반복합니다. answer에 3을 곱한 값에 n을 3으로 나눈 나머지를 더합니다. n을 3으로 나눕니다. while의 조건이 충족될 때까지 이..

합병 정렬(Merge Sort)이란 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식입니다. 알고리즘 복잡도는 O(n log n)입니다. 길이가 1인 배열 상태가 된 이후에는 인접한 부분끼리 값을 비교하여 정렬한 뒤 합칩니다. 데이터를 합치는 과정에서 이를 저장하는 메모리가 추가로 필요합니다. 그러나 속도는 이전의 버블 정렬, 삽입 정렬, 선택 정렬과 같은 정렬에 비해 빠릅니다. 과정은 다음 이미지과 같습니다. 합병 정렬 구현 코드 public class Main { public static void mergeSort(int[] array, int[] temp, int left, int right) { if (left < right) { int mid = (lef..

List 인터페이스 의 크기 조정 가능한 배열 구현입니다 . 모든 선택적 목록 작업을 구현하고 null 을 포함한 모든 요소를 ​​허용합니다 . List 인터페이스 를 구현하는 것 외에도 이 클래스는 목록을 저장하기 위해 내부적으로 사용되는 배열의 크기를 조작하는 메서드를 제공합니다. (이 클래스는 동기화되지 않는다는 점을 제외하면 Vector 와 거의 동일합니다.) 각 배열리스트 인스턴스에는 용량이 있습니다. 용량은 목록에 요소를 저장하는 데 사용되는 배열의 크기입니다. 항상 최소한 목록 크기만큼 큽니다. 요소가 배열리스트에 추가되면 용량이 자동으로 증가합니다. 배열의 선언과 생성 import java.util.ArrayList; 배열리스트를 사용하기 위해 import문을 추가해야 합니다. ArrayL..

문제 설명 한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2,3, 0, 2, -5일 때, 첫 번째 , 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다. 한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세..

선택 정렬(Selection)이란 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식입니다. 알고리즘 복잡도는 O(n^2)입니다. 정렬되지 않은 데이터 15 11 1 3 8 ↓ 1 11 15 3 8 ↓ 1 3 15 11 8 ↓ 정렬이 끝난 데이터 1 3 8 11 15 선택 정렬 구현 코드(최솟값부터) pubilc class Main { public static void selectionSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { int min = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } int temp ..

문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요...