Algorithm
-
LRU(Least Recently Used) 알고리즘Algorithm 2020. 10. 7. 15:32
페이지 교체 알고리즘 중 하나 캐시에서 메모리를 다루기 위해 사용되는 알고리즘 한정된 메모리 공간 안에서 효율적인 사용을 하기 위해서 사용 가장 최근에 사용된 적이 없는 캐시의 메모리부터 새로운 데이터로 갱신시켜준다. 즉 가장 오랫동안 사용하지 않은것을 제거하는 알고리즘 이는 오래동안 사용 되지 않은 것은 앞으로도 사용될 가능성이 낮다고 보는것이다. Cache Hit CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우 Cache Miss CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않은 경우 LRU 예시 문제 추천 https://programmers.co.kr/learn/courses/30/lessons/17680 코딩테스트 연습 - [1차] 캐시 3 [Jeju, Pangyo, Seoul,..
-
[Python] 병합 정렬(merge sort)Algorithm 2020. 5. 15. 16:47
분할 정복 알고리즘 중 하나로 병합 정렬(merge sort) 또는 합병 정렬이라고 부른다. 정렬되지 않은 전체 데이터를 하나의 단위로 분할한 후 분할한 데이터들을 다시 병합하면서 정렬하는 방식이다. 간단히 설명하자면, 큰 데이터를 하나의 작은 데이터로 쪼갠 후 정렬하면서 다시 합치는 것이다. 시간 복잡도는 O(n*logn)이다. 포인트 1. 분할: 배열이 하나의 원소가 될때 까지 절반으로 나눈다. 2. 병합: 분할된 각각의 원소를 비교하여 정렬된 배열을 만든다. Python Code def mergesplit(data): if len(data) left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged..
-
[Python] 백준 1302번 베스트셀러Algorithm 2020. 5. 14. 22:07
가장 빈도가 높은 문자열 출력하기 포인트! collections 모듈을 사용하여 알고리즘을 구현하였다. from collections import Counter collections에 있는 Counter를 이용하여 각 데이터 마다의 빈도를 구하고 ex) Counter({'top': 4, 'kimtop': 1}) most_common()을 이용하여 데이터의 개수가 많은 순의 리스트를 구하여 가장 빈도가 높은 문자열을 출력하였다. ex) [('top', 4), ('kimtop', 1)] Python Code from collections import Counter n = int(input()) books = [] for _ in range(n): books.append(input()) books.sort()..
-
[Python] 삽입 정렬(Insertion sort)Algorithm 2020. 3. 26. 14:14
삽입 정렬이란? 데이터들 중 두 번째 값부터 시작해서 그 앞의 데이터들과 비교해서 알맞은 위치로 삽입하는 형태의 정렬 앞 원소보다 크고, 뒤 원소보다 작은 위치에 삽입한다. 즉, 선택된 값의 앞쪽 원소들은 이미 정렬되어 있다. 과정 삽입 정렬은 두 번째 인덱스부터 시작 해당 인덱스(key) 앞에 있는 데이터(x)부터 비교해서 key값이 더 작으면 x값을 뒤 인덱스로 복사 이를 key값이 더 큰 데이터를 만날때까지 반복 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동 특징 시간 복잡도는 O(N^2) 정렬이 어느정도 되어있는 상태에서는 삽입 정렬이 빠르다. 배열이 길어질수록 효율이 떨어진다. Python code def insertion_sort(data): for index in range(len..
-
[Python] 선택 정렬(selection sort)Algorithm 2020. 3. 18. 16:14
선택 정렬이란? 정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식(오름차순일 경우) 과정 다음과 같은 순서를 반복하며 정렬하는 알고리즘 1. 주어진 데이터 중 최소값을 찾는다. 2. 해당 최소값을 데이터 맨 챂에 위치한 값과 교체한다. 3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다. selection sort 특징 자료 이동 횟수가 미리 결정된다. 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다. 코드가 간단하고 적은양의 데이터에서 효과적이다. 시간복잡도는 O(n^2)이다. Python Code def selection_sort(dat..
-
[Python] 버블 정렬(Buble sort)Algorithm 2020. 3. 15. 20:06
Buble sort 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 특징 시간 복잡도가 O(n²)로 느리다. 코드가 단순하여 자주 사용된다. Python Code def bubleSort(data): for index in range(len(data) - 1): swap = False for idx in range(len(data) - index - 1): if data[idx] > data[idx+1]: data[idx], data[idx+1] = data[idx+1], data[idx] swap = True if swap == False: break return data buble sort 확인하기 import random data_list =..