나작코

힙 정렬(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 함수를 작성해주세요...

배열(Array)은 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조입니다. 특정 원소에 접근할 때에는 배열의 인덱스를 이용하여 O(1) 시간에 접근할 수 있습니다. 그러나 새 항목을 배열 중간에 삽입하거나 중간에 있는 항목을 삭제하면, 뒤따르는 항목들을 한 칸씩 뒤로 또는 앞으로 이동시켜야 하므로 삽입이나 삭제 연산은 항상 O(1) 시간에 수행할 수 없다. 배열은 이미 정해진 크기의 메모리 공간을 할당받은 뒤 사용해야 하므로, 빈자리가 없어 새 항목을 삽입할 수 없는 상황(Overflow)에 직면할 수도 있습니다. Overflow가 발생하면 에러 처리를 하여 프로그램을 정지시키는 방법이 주로 사용됩니다. 하지만 프로그램 안정성을 향상시키기 위해 ..

삽입 정렬(Insertion Sort)이란 앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식입니다. 알고리즘 복잡도는 O(n^2)입니다. 앞의 원소부터 정렬하면서 비교하는 원소보다 클 경우에 비교를 중단하므로 버블 정렬보다는 빠른 편입니다. 정렬되지 않은 데이터 15 11 1 3 8 ↓ 11 15 1 3 8 ↓ 1 11 15 3 8 ↓ 1 3 11 15 8 ↓ 정렬이 끝난 데이터 1 3 8 11 15 삽입 정렬 구현 코드 pubilc class Main { public static void insertionSort(int[] array) { for (int i = 1; i 0; j--) { if (array[j] < a..

리스트(List)는 일련의 동일한 타입의 항목(item)들이 나열된 것을 의미합니다. 스택과 큐 자료구조도 리스트의 일종입니다. 일상에서는 학교의 학생 명단이나 시험 성적, 빌보드 차트, 버킷 리스트 등을 예로 들 수 있습니다. 여기서 말하는 리스트는 전문적 용어보다는, 앞서 설명한 데이터의 나열을 상징하는 표면적 단어로써의 의미가 큰 것 같습니다. 리스트와 관련된 기본 연산에는 k번째 항목을 읽는 접근, 임의의 항목을 찾는 탐색, 새 항목을 추가하는 삽입, 항목을 제거하는 삭제 연산이 있습니다. 이 책에서 리스트 파트에서는 배열, 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트만을 담고 있습니다. ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추..