Jin's Dev Story

💡 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법 → 최대공약수 최대 공약수 두 수의 공통된 “약수 중에서 가장 큰 수” 재귀 방식 // 재귀 방식 public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } 반복문 방식 // 반복문 방식 public static int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } 최소 공배수 두 수의 공통된 “배수 중에서 가장 작은 수” public static i..

💡 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 모든 영역을 전체 탐색하는 방법 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 기본적인 도구이다. ⇒ Ex) 4자리의 암호를 하나씩 대입하여 푸는 것

분할 정복이란? 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 평균 : Θ(nlogn), 최선 : Ω(nlogn), 최악 : O(nlogn) mergeSort public void mergeSort(int[] array, int left, int right) { if(left < right) { int mid = (left + right) / 2; mergeSort(array, left, mid); mergeSort(array, mid+1, right); merge(array, left, mid, right); } } 퀵정렬과의 차이점 퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort) 합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬..

선택 정렬 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 최소값을 찾아 정렬하는 방식 평균과 최악 모두 수행 시간 복잡도는 O(n2) Process (Ascending) 주어진 배열 중에 최소값을 찾음 그 값을 맨 앞에 위치한 값과 교체 (pass) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체 void selectionSort(int[] arr) { int indexMin, temp; for (int i = 0; i < arr.length-1; i++) { // 1. indexMin = i; for (int j = i + 1; j < arr.length; j++) { // 2. if (arr[j] < arr[indexMin]) { // 3. indexM..

버블 정렬 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 인접한 두 개의 레코드 키 값을 비교하여 서로 교환하며 정렬하는 방식 평균과 최악 모두 수행 시간 복잡도는 O(n2) Process (Ascending) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됨 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘..

퀵 정렬 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 스택 필요 분할과 정복을 통해 자료를 정렬 평균 수행 시간 복잡도는 O(nlog2n), 최악의 수행 시간 복잡도는 O(n2) Process (Ascending) 배열 가운데서 하나의 원소를 고름 이렇게 고른 원소를 피벗(pivot) 이라고 함 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눔 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 함. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복 재귀 호출이 한번 진행될 때..