ConnectingDots

정렬이란? 데이터를 기준에 맞춰 나열하는 것 정렬의 종류 버블 정렬 인접한 두 요소를 비교하여 필요하면 위치를 바꾸는 방식 큰 요소를 점차 끝으로 보내며 정렬한다. 시간 복잡도는 O(N^2)로, 효율성이 낮아 소규모 데이터 정렬에 적합하다. 선택정렬(selection sort) 전체 배열에서 가장 작은 값을 찾아 맨 앞의 요소와 교환하는 방식 시간 복잡도는 O(n^2)로, 데이터가 많을수록 비효율적이다. 삽입 정렬(Insertion sort) 배열의 첫 번째 요소를 기준으로 다음 요소를 적절한 위치에 삽입해가며 정렬하는 방식 시간 복잡도는 O(n^2)이지만, 거의 정렬된 데이터에서는 빠르게 동작하여 효율적이다. 퀵 정렬(Quick Sort) 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 ..

DP(Dynamic Programming) 주어진 문제를 하위 문제로 나누고, 작은 문제들부터 시작하여 점점 큰 문제를 해결하는 상향식(Bottom-Up) 방식 배열이나 테이블에 작은 하위 문제의 결과를 저장하고, 각 단계에서 이를 참조하여 더 큰 문제를 해결한다. 작은 문제들을 차례로 해결하여 마지막에 전체 문제의 해답을 얻는 방식 장점모든 하위 문제를 한 번씩만 계산하고 결과를 저장하므로 재귀 호출의 깊이에 제한이 없어 메모리 오버헤드가 적고, 대부분의 경우 실행 속도 역시 바르다. 한계해결해야 할 모든 하위 문제를 미리 테이블에 저장하므로 불필요한 계산과 메모리 낭비가 발생할 수 있다. 메모이제이션(Memoization) 필요할 때만 하위 문제를 해결하고 이를 캐시에 저장하는 방식 재귀적으로 문제를..