 사과개발자의 일상

안녕하세요! daily_D 입니다! 👩🏻‍💻 오늘은 정렬 알고리즘에 대해 공부해봐요!! Bubble Sorting ( 버블정렬 ) 시간복잡도 : O(N^2) 공간복잡도 : O(1) 서로 인접한 두 원소를 검사하여 정렬하는 방식 ※ 정렬 알고리즘들 중에서 가장 간단한 로직을 가졌지만 그만큼 낮은 성능을 보입니다. # Python def bubble_sort(arr): for i in range(N-1, 0, -1): for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr Selection Sort ( 선택정렬 ) 시간복잡도 : O(N^2) 공간복잡도 : O(1) 비정렬영역의 최솟값을 찾아 정렬영역의 맨 뒤..

안녕하세요! daily_D 입니다! 👩🏻‍💻 오늘은 페이지 교체 알고리즘 중에서 LRU에 대해서 공부해볼까요?! LRU 란? LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식입니다. LRU 는 사용된지 가장 오래된 페이지는 앞으로도 사용될 확률이 낮다는 가설에 의해 만들어진 알고리즘입니다. LRU 의 원리 LRU 를 구현하기 위해서는 캐시가 가득 찼을때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요합니다. 페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지번호를 추가합니다. 그러면 맨 뒤에 있는 페이지번호가 가장 오랫동안 참조되지 않은 페이지번호가 되겠죠? 따라서 LRU의 원리는 캐시의 크기가 3인데 이미 3개의 페이지가 캐시에 들..

안녕하세요! daily_D 입니다! 👩🏻‍💻 오늘은 DFS 와 BFS의 원리와 이를 코드로 작성하는 방법에 대해서 써볼까합니다! DFS 와 BFS, 알고리즘하면 거의 가장 먼저 배우게 되는 것들이죠! 아마 알고리즘 원리는 몰라도 이름은 들어보신 분들이 많을거에요! 그래서 DFS, BFS 가 뭐냐! 하면!! DFS는 Depth-First-Search의 약어로 깊이 우선 탐색이고 BFS 는 Breadth-First-Search 의 약어로 너비 우선 탐색입니다. 이 둘은 그래프를 탐색하는 방법들입니다! 그럼 그래프가 뭐냐.. 하면 그래프는 정점(node)들과 이 정점들을 연결하는 간선(edge)으로 이루어진 자료구조를 말합니다. 그래프 탐색은 하나의 정점을 시작으로 다른 정점들을 모두 한번씩 방문하는 것을 말..