![]()
Median of Medians (MoM)퀵셀렉트 알고리즘 이용 → 최악의 경우를 방지하기 위해 랜덤 pivot말고 좀 똑똑하게 고르자 → approximate median으로 pivot 고름(대략적인 중앙값) → MoM이 pivot 이름 → 이를 통해 i번째 원소 찾기 가능보다 밸런스 파티션을 보장함 -Select Procedure5개원소로 그룹 만듦 → [n/5]개의 그룹 탄생각 그룹을 정렬한 후 해당 그룹 별로 median(중앙값) 찾기 → 중간값들이 새 배열 형성새 배열인 median들 중에서 median 찾아서 pivot으로 삼음 (MoM 재귀적 호출 통해) ⇒ T([n/5])기존 배열을 pivot 기준으로 작은 값, 큰 값 두 구간으로 나눔 → 이때 pivot이 k번째 작은 값임을 알 수 있음..
![]()
13. TLB14. Advanced Page Table15. Swapping: Mechanisms16. Swapping: Policies17. Concurrency & Threads18. Thread API19. Lock20. Semaphores21. I/O devices22. HDD23. Files & Directory24. FS Implementation25. FS Consistency
-Backtracking(백트래킹)백트래킹은 brute force, DFS와 비슷하게 가능한 모든 방향을 탐색하는 알고리즘이다.다만 DFS는 중간에 원하던 값이 아니더라도 무조건 트리의 리프노드까지 일단 갔다가 돌아오는 방식이고, 백트래킹은 내려가다가 중간에 원하던 값이 아닌 경우 바로 그전 단계로 되돌아오는 방식이다. (조금 더 효율적인 알고리즘)관련 문제로는 미로찾기, N Queens, Subset Sum등이 있다. -문제 설명미로에서 탈출하는 경우의 수를 pathCnt로 계산해서 출력하는 문제이다. 0,0에서 시작해서 row-1,col-1로 도달하면 성공으로, 그때 pathCnt를 증가시킨다. 입력은 0과 1로 이루어진 행렬로 주어지며, '1'은 벽이고 '0'이 이동 가능한 통로이다.(int가 아..
