Backend/Algorithm & Data structure (10) 썸네일형 리스트형 스케줄링 알고리즘 스케줄러: 어떤 작업이 언제 실행될지 결정하는 역할 선점 스케줄링 : 우선순위가 더 높은 작업이 먼저 실행된다. 비선점 스케줄링 : 프로세스가 종료되거나 자발적으로 중지될때까지 실행한다. 1. FCFS 스케줄링(First Come First Served) : 선입선출, 큐데이터구조 사용 2. SJF 스케줄링(Shortest Job First) : - 선점 : 실행 중인 프로세스를 멈추고 더 짧은 CPU점유시간을 가진 프로세스를 실행 - 비선점 : CPU 점유시간이 짧은 순서대로 프로세스 실행, 나중에 도착한 점유시간이 짧은 프로세스는 먼저 도착한 점유시간이 긴 프로세스의 실행이 끝날때까지 기다려야함. 기아상태가 발생할 수 있다. *기아상태 : 특정 프로세스의 우선순위가 낮아서 원하는 연산 자원을 계속 할.. 군집화 알고리즘(K-알고리즘) 1. k-평균(k-means) 알고리즘 센트로이드라는 분할형 군집의 중심점을 할당한다. 각 노드는 가장 인접한 센트로이드를 중심으로 군집을 형성한다.(군집의 개수인 k값을 미리지정) 일반적으로 센트로이드를 무작위로 선택하여 유클리드 거리를 계산하여 인접한 노드를 군집의 요소로 선택한다. 요소를 선택한 후 요소를 중심으로 센트로이드의 위치를 다시 계산한다. 결과적으로 각 군집에 속한 모든 요소의 평균위치로 재설정된다. 센트로이드가 더이상 이동하지 않을 때까지 수행된다. → 'k'개의 '평균'을 찾는알고리즘, 머신러닝의 비지도 학습 시스템에서도 사용 2. k-최근접 이웃 알고리즘 → 검증 표본(초록색 원)은 첫 번째 파랑 네모의 항목이나 빨강 삼각형의 두 번째 항목으로 분류되어야 한다. 만약 “k = 3” .. 경로 탐색 알고리즘 너비 우선 탐색(BFS) 그래프를 층별로 탐색한다. 한번 거친 노드 순서를 저장한 후 다시 꺼내는 선입선출 원칙으로 탐색한다.(큐 데이터구조) 깊이우선탐색(DFS) 경로 하나의 모든 층을 탐색한 후 그 다음에 다른 경로의 모든 층을 탐색한다. 재귀호출이나 스택을 사용한다. 다익스트라(Dijkstra) 알고리즘 가중 그래프에서 동작하고 그래프의 시작 노드에서 목표노드까지의 최단 경로(최소 비용)를 찾는다. 그래프의 가중치를 비용이라고 하며, 비용이 음수가 아니어야한다. 무정보탐색으로 많은 시간과 자원을 소비한다는 한계점이있다. (참고) 벨먼-포드 알고리즘은 가중치가 음수인 그래프에서도 동작한다. A*알고리즘 휴리스틱 알고리즘(확률론을 토대로 문제의 대략적인 해결책을 제공)의 범주에 속한다. 데이크스트라 알.. 정렬 알고리즘 1. 버블정렬 인접한 2개의 요소의 크기를 비교해 숫자의 위치를 바꾼다. 시간 복잡도가 O(n^2)으로 비효율적임. 2. 선택 정렬 선형탐색으로 배열에서 가장 작은 숫자를 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨처음 위치를 뺀 나머지 리스트를 같은방법으로 교환한다. 버블정렬보다 효율적임. 3. 삽입 정렬 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성한다. 선택정렬보다 효율적임. 4. 셸 정렬 요소를 몇개의 단위로 묶은 후 단위마다 삽입정렬을 실행함 요소 수를 줄여 묶은 후 삽입 정렬을 실행함 단위 요소 수가 1이 될때까지 실행하면 정렬이 완료됨 시간복잡도는 평균 O(n^1.5) 5. 병합 정렬 배열에 하나의 숫자만 남을 .. 선형 및 이진탐색 선형탐색 찾고자 하는 값을 리스트의 맨앞에서부터 끝까지 차례대로 비교 요소 개수 증가에 정비례하여 증가 시간복잡도가 O(n)이다. 이진탐색 한번 검색할 때마다 배열을 반으로 나눠 검색 대상에서 제외 선형탐색보다 처리속도가 빠름 시간복잡도가 O(logn)이다. 코드 참고 : https://velog.io/@anjaekk/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%98%95%ED%83%90%EC%83%89%EA%B3%BC-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89 [알고리즘] 선형탐색과 이진탐색 저장된 정보들 중에서 원하는 값을 찾는 것찾고자 하는 값을 리스트의 맨 앞에서부터 끝까지 차례대로 찾아 나가는 방식장점: 검색 방법 중 가장 단순.. 그래프 그래프는 노드사이의 연결을 보여준다. 그래프의 노드를 객체또는 정점(vertex)라고하며, 정점을 연결하는 선을 간선(edge)라고 한다. 트리도 일종의 그래프라고 볼 수 있다. 에지는 노드하나에서 다른 노드로 방향성을 가질 수 있다. 방향성에 따라 Undirected Graph 와 Directed Graph로 나뉜다. 참고 : https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph [CS 기초 - 자료구조] Graph 그래프의 개념 및 종류, 구현 방법 등 velog.io 해시 데이터 구조 해시 테이블 키와 값으로 구성된 검색 시스템. 모든 키에 대응하는 값이 있다. 요소를 검색할 때 시간 복잡도가 O(I)이다. 해시 충돌 해시값과 배열 크기 때문에 서로 다른 입력2개가 같은 해시값을 생성할 때 발생 발생을 방지하기 위해 '체이닝(chaining)'방식으로 해시테이블을 구현한다. 체이닝(Chaining) 요소를 단순한 배열이 아닌 연결 리스트인 배열에 저장하는 방식. 즉, 해시 함수가 여러 요소에 대해 똑같은 인덱스를 반환할 경우, 해시값과 해당요소들을 함께 연결하여 해시테이블의 같은 인덱스에 저장한다. 연결리스트가 길어졌을 때 테이블 검색의 시간복잡도가 증가할 수 있다. ☞ 해싱은 컴퓨터 보안 영역에서 주로 사용된다. 디지털 서명이나 사용자 인증 등에 사용된다. 양방향(암호화, 복호화)인.. 트리 구조 트리 데이터 구조는 데이터를 계층으로 정렬한다. 노드:데이터를 저장하며, 키(데이터식별)와 값(저장된데이터)을 포함할 수 있음. 루트노드: 트리구조의 맨 위 노드 부모노드: 상위노드 자식노드: 하위노드 리프노드:말단노드, 더이상 자식노드를 갖지않는 마지막 노드 에지:트리를 연결하는 선 서브트리:하위트리,노드하나와 자식노드로 구성된 트리 1. 이진트리 가장 많이 사용되는 데이터 구조. 각 부모 노드가 항상 2개의 자식 노드와 연결 이진탐색트리 : 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다. 2. AVL트리 하나의 자식 노드를 갖는 불균형 이진트리의 균형을 조정하여 최소높이로 만든것. 높이 차이를 감지하면 트리회전으로 조정한다. 시간 복잡도는 O(logn)이다. +RB트리(모든 노드가.. 이전 1 2 다음
