나디아 성장 일기

동적 프로그래밍(Dynamic Programming): 큰 문제를 작은 문제로 나누고, 그 결과를 저장하여 중복 계산을 피하는 최적화 기법 메모이제이션 (Memoization): 계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법하향식(Top-Down) 방식재귀를 사용해 큰 문제부터 내려가며 계산이미 계산한 결과는 저장해두고 다시 사용함 메모이제이션의 장단점장점재귀 덕분에 하향식 계산 방식으로 어려운 문제를 간단히 해결할 수 있음중복 계산을 하지 않아서 속도가 빠름 단점재귀를 사용하기 때문에 오버헤드가 큼 메모이제이션은 속도를 위해 메모리를 사용하기 때문에 메모리 사용량 증가 예시: 피보나치 수열 기본 재귀 방식function fibonacci1(n){ if(n == 0 || n ..

퀵 정렬 (Quick Sort): 기준값(피벗)을 정해 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누며 정렬하는 빠른 정렬 알고리즘 분할 정복 알고리즘재귀로 정렬하는 알고리즘 퀵 정렬의 성능시간 복잡도평균: Θ(n log n) → 피벗이 배열의 절반씩 나누는 경우최악: O(n²) → 피벗이 한쪽 끝에 치우친 경우→ 하지만 최악의 경우는 거의 발생하지 않음성능 평가병합 정렬이 평균 성능만 보면 더 나을 수 있지만, 퀵 정렬은 실제로 더 적은 비교와 메모리 사용량으로 인해더 빠르고 효율적인 알고리즘으로 평가됨 퀵 정렬의 장단점장점 전체적으로 성능이 좋음 단점 전체적으로 성능이 좋음 퀵 정렬의 흐름[ 5, 3, 7, 2, 6, 4, 9, 1, 8 ]정렬을 시작하기 전에 배열에서 하나를 피벗(pivot)..

병합 정렬 (Merge Sort): 큰 배열을 잘게 나눴다가, 정렬하면서 다시 합쳐 정렬을 완료하는 알고리즘분할 정복 알고리즘(divide and conquer): 복잡한 문제를 한 번에 해결하려 하지 말고, 작은 문제로 쪼개서 각각 해결한 후 결과를 합쳐 전체 문제를 해결하는 방식 재귀로 정렬하는 알고리즘 병합 정렬의 성능시간 복잡도: O(n log n)병합 정렬에서 성능을 평가하는 부분 ⇒ Merge() 함수 내에서 흩어진 배열을 합치는 부분 병합 정렬의 장단점장점전체적으로 성능이 좋음 단점이해와 구현이 어려움 병합 정렬 알고리즘 흐름원본: 3 5 2 4 1 7 8 61단계: 3 5 2 4 1 7 8 6 → 2개로 쪼갬2단계: 3 5 2 4 1 7 8 6 → 4개로 쪼갬3단계:..