[12] 분할 정복...⚔️

AI 최고닷

오늘 배운 내용

---

분할 정복 (Divide and Conquer)

: 큰 문제를 작은 하위 문제로 나누어 해결하는 방식

설계 전략

• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
• 결합(Combine) : (필요하다면) 해결된 해답을 모은다.

이진 검색

: 정렬된 배열에서 특정한 값을 빠르게 찾기 위한 알고리즘

-> 검색 범위를 반으로 줄여 빠르게 검색 수행

• 시간 복잡도 $O(log N)$ → 1000개의 원소를 대략 10번 정도의 비교로 값을 찾을 수 있음.
• 미리 정렬이 되어 있어야 함. (데이터 삽입, 삭제가 자주 일어나면 정렬해야 하므로 비효율적)
• 크기가 작은 배열에서는 크게 이점이 없을 수 있음

병합 정렬 (Merge Sort)

: 분할 정복 (Divide and Conquer) 기법을 활용한 안정적인 정렬 알고리즘

배열을 절반으로 분할하고, 각 부분을 재귀적으로 정렬한 뒤, 정렬된 부분 배열을 다시 병합하는 정렬 방식

• 시간 복잡도 O(NlogN)
• 추가적인 공간 필요

<의사코드>

mergeSort(arr[], left, right) {
	if left < right :
    	mid <- (left+right)/2
        mergeSort(arr,left,mid)
        mergeSort(arr,mid+1,right)
        merge(arr,left,mid,right)
}

merge(arr[],left,mid,right) {
	L <- left, R <- mid+1
    idx <- left
    while L <= mid && R <= right {
    	if arr[L] <= arr[R]
        	sortedArr[idx++] <- arr[L++]
        else
        	sortedArr[idx++] <- arr[R++]
    }
    if L <= mid {
    	for i in L to mid
        	sortedArr[idx++] <- arr[i]
    }
    else {
    	for j in R to mid
        	sortedArr[idx++] <- arr[i]
    }
    for i in left ot right
    	arr[i] <- sortedArr[i]
}

 

퀵 정렬

: 분할 정복(Divide and Conquer) 기법을 활용한 효율적인 정렬 알고리즘

• 피벗(Pivot)이라는 기준 요소를 선택하여 배열을 두 부분으로 분할하고, 재귀적으로 정렬하는 방식
• 시간 복잡도 $O(NlogN)$, 최악에는 $O(N^2)$
• 추가적인 공간은 필요치 않아 함

---

회고

---

오늘 본 Web Front와 알고리즘 시험에서 나름의 좋은 결과를 얻었다.

역시나 JavaScript는 조금 버거웠고 강의에 이틀 빠진 티가 너무 많이 났다.

HTML과 CSS는 점차 친해지고 있는 느낌이 들어서 좋다. 그래도 아직 너무 어려움..ㅠ

알고리즘 시험은 지난 과목평가에 비하면야 본인의 성장세를 알아갈 수 있는 좋은 시험이었던 것 같다.

그래도 edge케이스를 발견하지 못해 로직이 약간 틀어진건 너무 아쉽지만 어쩌겠음...

이제 내일 조금 이른 다시 역량테스트다. 잘 준비해서 붙길 바란다.

---

개선점 or 피드백

---

• Edge Case 체크는 습관화
  -> 시간이 꽤 있었음에도 체크하지 않는 것이 패착
• JavaScript도 꼭 시간내서 공부하자.
• 블로그 글 정리 순서
  TIL -> 코테 -> CS 스터디 -> Java -> Web Front -> Algorithm

---

오답노트

---

• 아쉬운 문제도 있고, 또 오늘 한참 헤맨 문제도 있지만 시험문제이기도 했고 공개는 못함! (안한다 ㅎ히히)