기준에 따라 데이터를 정렬
Sorting이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 많이 사용되는 알고리즘 중 하나다.
삽입정렬
자료 배열의 모든 요소를 앞에서부터 차례때로 이미 정렬된 배열 뿐과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
O(n^2)
순회돌다가, 자기보다 큰 수 만나면 그 앞에서 멈추기 .
병합정렬, mergesort, 분할정복
문제를 잘게 자른다음에, 더 이상 나눌게 없는 경우 합친다
퀵정렬
기준을 잡고 작은키, 큰키를 나눈다.
기준은 리스트의 첫 값으로 한다.
만약 중간 숫자가 기준이 된다면? 다시 한번 더 정렬시키기
문제중요도(it기업)
병합정렬,퀵정렬!
비it
선택정렬,삽입정렬
병합정렬, mergesort, 분할정복
[180, 173, 145, 165, 170, 45, 175, 171][180, 173, 145, 165], [170, 45, 175, 171][180, 173], [145, 165], [170, 45], [175, 171][180], [173], [145], [165], [170], [45], [175], [171][173, 180], [145, 165], [45, 170], [171, 175][145, 165, 173, 180], [45, 170, 171, 175][45, 145, 165, 170, 171, 173, 175, 180]
퀵정렬
[66, 77, 54, 32, 10, 5, 11, 15];
//피봇값 : 66
[54, 32, 10, 5, 11, 15] + [66] + [77]
//피봇값 : 54(66과 77은 값이 한 개이기 때문에 더이상 재귀로 호출되지 않음.)
[32, 10, 5, 11, 15] + [54] + [66] + [77]
//피봇값 : 32
[10, 5, 11, 15] + [32] + [54] + [66] + [77]
//피봇값 : 10
[5] + [10], [11, 15] + [32] + [54] + [66] + [77]
//피봇값 : 11
[5] + [10], [11], [15] + [32] + [54] + [66] + [77]
페이지 교체 알고리즘
메모리 누적되어있는 시간. 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운
페이지를 할당하기 위해 현재 할당된 페이지 중 어느것과 교체할지를 결정하는 방법이다.
이 알고리즘이 사용되는
FIFO알고리즘 : 먼저 들어온애가 교체
hit발생해도 자리 지킬뿐, 위치이동은 없다.
(맨 앞 제거, hit해도 위치 지킴)
OTP알고리즘 : 페이지 부재가 발생했을 경우 각 페이지 호출순서에 따라 사용하지 않을 페이지를 교체하는 기법
가장 많이 씀 : LRU알고리즘 (least-recently-used) 캐쉬에서 메모리를 다루기 위한 알고리즘 페이지 부재
최근 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘 (맨 앞제거, 최근 사용 맨뒤)
카카오 페이지교체알고리즘
사용하지 않을 수록 맨 앞에 있다!.
캐쉬크기 0이면 length * 데이터
[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”][“Jeju”] 1회차
[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”][“Jeju”, “Pangyo”] 2회차
[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”][“Jeju”, “Pangyo”, “Seoul”] 3회차
[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”][“Pangyo”, “Seoul”, “NewYork”] 4회차
[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”][“Seoul”, “NewYork”, “LA”] 5회차
[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”][“NewYork”, “LA”, “Seoul”] 6회차
[“Jeju”, “Pangyo”, “Seoul”, “NewYork”, “LA”, “Seoul”, “LA”][“NewYork”, “Seoul”, “LA”] 7회차
hit - 1 (이미 있을때 hit)
miss - 5 (없었을때_)
LRU 알고리즘이에요.
cash쓰는 이유? 자주 hit되는 애들 메모리에서 갖고오자는 의미!
문제에서 hit/ miss 실행시간 정해져있다.
왜 최근 사용했던 데이터를 가장 마지막에 넣을까?
==>왜냐하면 금방 꺼내서 사용할거니까!
트리
- '탐색'을 위한 자료구조
Node와 Edge(branch라고도 부름)를 이용하여 데이터 표현
노드 ~ root node / internal node /leaf node
깊이는 보통 0 에서 시작 ( 기준이 다를 수 있긴함)
차수 : 자식 노드 개수
이진트리 : 자식노드가 최대 두개인 노드들로 구성
- 포화이진트리 :모든 노드가 두 개의 자식노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다.
- 완전이진트리 :마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에서는 왼쪽부터 노드가 순서대로 채워져 있다.
-고냥 이진트리 ..> 완전이진트리> 포화이진트리
데이터 찾을 때 / 가중치 계산할때 데이터 굉장히 빨리 찾을 수 있다.
전위순회: 루트노드부터 잎 노드까지 아래 방향으로
후위순회: 잎 노드 모두 탐색하고 마지막 루트 (왼-오-루트)
중위순회:
이진탐색트리 vs 정렬된 배열의 탐색
굉장히 빠르게 정렬가능!
너비우선탐색 -
깊이우선탐색 -
current 자신
stack - 자식 노드
