퀵 정렬(Quick sort)퀵 정렬은 데이터를 정렬할 때기준값(피벗)을 하나 정하고 나머지 데이터를 작은 값(left)과 큰 값(right)으로 나눈 다음이 두 그룹을 재귀적으로 정렬하는 방식입니다. 과정:기준점(pivot)을 정해서기준점보다 작은 데이터는 왼쪽큰 데이터는 오른쪽으로 모으는 함수가 필요각 왼쪽, 오른쪽은 재귀 호출을 통해 위 작업을 반복함함수는 [왼쪽] + 기준점 + [오른쪽]을 리턴함 동작 과정 예시:예시: `[5, 3, 8, 4, 2, 7, 1, 6]` 피벗 선택: 리스트의 첫 번째 값 5를 피벗으로 선택분할:피벗보다 작은 값 → `[3, 4, 2, 1]`피벗보다 큰 값 → `[8, 7, 6]`재귀 정렬:`[3, 4, 2, 1]` → 다시 퀵 정렬`[8, 7, 6]` → 다시 퀵 정..

동적 계획법(Dynamic Programming, DP)작은 부분 문제들을 해결한 후 해당 부분 문제들의 해를 활용하여 보다 큰 부분 문제를 해결하면서 최종적으로 전체 문제를 해결하는 알고리즘「상향식 접근법」으로 가장 최하위 해답을 구한 후 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식Memoization 기법을 사용함Memoization(메모이제이션)이란?: 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용됨예: 피보나치 수열 분할 정복(Divide and Conquer)문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘「하향식 접근법」으..

재귀 용법(Recursive Call, 재귀 호출)함수 안에서 동일한 함수를 호출하는 형태 예제팩토리얼을 구하는 알고리즘분석: 규칙이 보임 `n! = n * (n-1)!`def factorial(num): if num > 1: return num * factorial(num - 1) else: return num 시간 복잡도와 공간 복잡도`factorial(n)` 은 `n - 1` 번의 `factorial()` 함수를 호출해서 곱셈을 함일종의 `n - 1`번 반복문을 호출한 것과 동일`factorial()` 함수를 호출할 때마다, 지역변수 `n`이 생성됨시간 복잡도/공간 복잡도는 `O(n - 1)` 이므로 결국, 둘 다 `O(n)` 재귀 호출의 일반적인 형태# 일반적인..

삽입 정렬(Insertion sort)리스트를 왼쪽부터 차례대로 보면서현재 요소를 그 앞쪽의 정렬된 구간에 적절한 위치에 '삽입'하는 방식즉 하나씩 꺼내서 앞에서부터 위치를 찾아 넣는 방식이라서 삽입 정렬이라고 불립니다. 과정두 번째 요소부터 시작해요. 이 값을 key라고 부를게요.key의 왼쪽에 있는 값들을 하나씩 거꾸로 보면서key보다 큰 값이 있다면 한 칸씩 뒤로 밀어요.이렇게 하다 보면 key보다 작거나 같은 값을 만나게 되는데그 바로 뒤에 key를 넣으면 돼요.이 과정을 리스트 끝까지 반복하면 정렬이 완료됩니다. 동작 과정 예시정렬할 리스트: `[5, 3, 4, 1, 2]` `i = 1`, 3은 5보다 작다 → swap → `[3, 5, 4, 1, 2]``i = 2`, 4는 5보다 작다 → sw..

선택 정렬(Selection sort)다음과 같은 일련의 과정을 반복하며 정렬하는 알고리즘 주어진 데이터 중 최솟값을 찾음해당 최솟값을 데이터 맨 앞에 위치한 값과 교체함맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함참고: https://visualgo.net/en/sorting 알고리즘 구현public static List selectionSort(List dataList) { int n = dataList.size(); for (int i = 0; i 알고리즘 분석이중 반복문 `O(n^2)`실제 계산 `n*(n-1)/2`

정렬(Sorting)어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것으로다양한 알고리즘이 고안되었으며 알고리즘 학습의 필수라고 할 수 있다. 다양한 정렬 알고리즘 이해를 통해 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고각 알고리즘 간 성능 비교를 통해 알고리즘 성능 분석에 대해서도 이해할 수 있다! 버블 정렬(Bubble sort)두 인접한 데이터를 비교해서앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘 VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)VisuAlgo is free of charge for Computer Science commu..