안정 정렬비교한 값이 같을 때 서로 바뀌지 않는 정렬법을 안정 정렬이라고 한다병합 정렬(Merge Sort)리스트의 길이가 0또는 1이면 이미 정렬된 것으로 봄정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9};int tmparr[10];void sort(int, int);void merge(int, int);void sort(int start, int end){ if(end > start) { sort(start, (start + end) / 2); sort((..
참고 링크버블 정렬(Buble Sort)바로 뒤의 원소와 비교해 더 크다면 뒤로감구현이 쉬운 만큼 성능이 좋지 않다시간복잡도 O(n^2)def bubbleSort(x): length = len(x)-1 for i in range(length): for j in range(length-i): if x[j] > x[j+1]: x[j], x[j+1] = x[j+1], x[j] return x선택 정렬(Selection Sort)1번부터 끝까지 훑어서 가장 작은 것을 첫 번째, 그 다음에 2번째 부터 가장 작은 게 두 번째로 정렬시간복잡도 O(n^2)def selectionSort(x): length = len(x) for i in range(length-1): for j in range(i+1, ..
참고 링크트리그래프의 일종트리에서의 정점을 노드라고하고 간선을 가지라고 한다관련 용어노드(Node)그래프의 정점에 해당하는 것루트 노드트리의 기준이 되는 노드나무의 뿌리와 유사루트 노드 위에 가지가 뻗어있다는 이미지부모 노드어떤 노드에서 자신과 인접한 노드들 중 루트 노드로 향하는 노드자식 노드어떤 노드에서 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드단말 노드자식 노드가 존재하지 않는 노드가지의 끝형제 노드부모 노드가 같은 노드가지(Branch)그래프의 간선에 해당하는 것트리에서는 양방향 간선만 사용부트리(Sub Tree)부분 그래프와 비슷하게 정의차수(Degree)자식 노드의 개수길이(Length) 임의의 두 노드를 시작, 도착 노드로 하는 경로에 거치게 되는 노드의 수깊이(Dept..
참고 링크i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조를 의미그래프점들, 그리고 점들을 연결하는 선들만 이루어진 형태이때 점을 정점(vertex), 선을 간선(edge)이라고 부름인접 행렬 : O(v*e)인접 리스트 : O(v+e)관련 용어정점(Vertex)연결점, 여러 가지 특성을 가질 수 있는 객체어떤 객체도 정점이 될 수 있음고립 정점간선이 하나도 연결되지 않은 외톨이 정점간선(Edge)두 정점을 연결하는 연결선, 두 정점간의 관계단방향 간선단방향으로만 이동 가능한 간선. 이동이 가능한 방향으로 화살표를 그림양방향 간선양방향으로 모두 이동이 가능한 간선이다. 양쪽 화살표를 사용해도 되지만, 양방향 그래프에서는 모든 간선이 양방향 간선이므로 화살표 대신 선분으로 표현자가 간선자기 자신을 연..
참고 링크선형구조로 된 자료를 탐색하는 방법. 보통 어떤 값이 어디에 있는지 알아내는 것이 목적순차 탐색시작점 부터 순차적으로 탐색하는 것. 전부 탐색한다고 생각할 시에, 연산량은 O(n)이다.이분탐색특수한 상황에서 순차 탐색보다 좀 더 빠른 속도를 기대할 수 있는 알고리즘연산량은 O(log N)가운데에서 시작해서 매번 일정한 조건에 따라 어떤 방향의 가운데 값으로 탐색할 지 결정하는 알고리즘이때 가운데 값이랑 평균이 아니고 중간 값 이를 위해서는 정렬이 되어있어야한다
참고 링크한 종류의 데이터가 선처럼 길게 나열된 자료 구조랜덤 접근 가능모든 자료에 O(1)으로 접근이 보장되는 자료 구조들배열해시해시 함수에 키값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다언제나 O(1)가 보장되는 것은 아님(파이선의 해시는 딕셔너리(dictionary)라고 부른다)랜덤 접근 불가능모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다.스택(Stack)먼저 들어간 자료가 나중에 나오는 자료구조 (LIFO)자료를 넣는 push자료를 빼는 pop큐(Queue)먼저 들어간 자료가 먼저 나오는 구조 (FIFO)자료를 넣는 Enqueue함수와 자료를 빼내는 Dequeue 함수를 가짐연결 리스트로 구현한다 LinkedList데크(Deque)스택과..
