나작코

다이나믹 프로그래밍(Dynamic Programming)이란, 계산된 결과를 기록하고 재활용하여 문제의 답을 구하는 알고리즘입니다. 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서 중간 계산 결과를 기록하기 위한 메모리를 필요로 합니다. 한 번 계산한 부분을 다시 계산하지 않아도 돼서 속도가 빠르다는 장점이 있습니다. 동적 계획법이라고도 불립니다. 다이나믹 프로그래밍에는 타뷸레이션(Tabulation)과 메모이제이션(Memoization) 두 가지 방법이 있습니다. 먼저 타뷸레이션은 하위 문제부터 풀면서 올라가는 상향식 접근 방법으로, 모두 계산하면서 차례대로 진행합니다. 반대로 메모이제이션은 큰 문제에서 하위 문제를 확인해가며 진행하는 하향식 접근 방법으로, 계산이 필요한 순간 계산하면서 진행합..

분할 정복(Divide and Conquer)이란 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘입니다. 예를 들어 합병 정렬, 퀵 정렬, 이진 검색 등이 있습니다. 분할 정복은 세 가지 과정으로 이루어집니다. 문제를 하나 이상의 작은 부분들로 '분할'하고, 부분 문제를 해결하여 '정복'하고, 부분에서 해결한 문제를 '조합'하여 원래 문제의 답을 구하는 것입니다. 이는 재귀함수를 이용하여 구현할 수 있습니다. 문제를 나누어서 처리하기 때문에 어려운 문제도 해결할 수 있고, 병렬 처리에 이점이 있다는 장점이 두드러집니다. 그러나 재귀 호출 구조를 이용하기 때문에 잦은 분할 시에는 메모리를 많이 사용하거나 동작이 느려질 수 있다는 단점이 있습니다. 분할 정복 구현 코드(최댓값 찾기) public sta..

에라토스테네스의 체란, 마치 체로 치듯이 수를 걸러낸다고 해서 붙여진 이름입니다. 고대 그리스의 수학자 에라토스테네스가 만들어낸 방법입니다. 이는 소수(Prime number)를 빠르고 효율적으로 찾을 수 있는 알고리즘입니다. 자세한 설명은 코드와 함께 상세하게 작성한 게시글이 있으므로 생략하겠습니다. [프로그래머스 코딩테스트] 소수 찾기(Java) https://sigfriede.tistory.com/114

투 포인터(Two Pointer)란 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘입니다. 포인터는 첫 번째 원소에 둘 다 배치하여 같은 방향에서 시작하는 방법과 각각 첫 번째 원소와 마지막 원소에 배치하여 서로 다른 방향에서 시작하는 방법이 있습니다. 이를 이용하여 다중 for문의 복잡도를 줄일 수 있습니다. 투 포인터 구현 코드(첫 번째 원소에서 시작) public static int[] twoPointers(int[] array, int target) { int p1 = 0; int p2 = 0; int sum = 0; int[] result = {-1, -1}; while (true) { if (sum > target) { sum -= array[p1++]; } else if (p..

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

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

계수 정렬(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[]..

기수 정렬(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;..

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

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