미가공 필기(알고리즘)24 210701 레드 블랙 트리(Red-Black Tree) 레드 블랙 트리(Red-Black Tree) 모든 노드는 블랙 노드이거나 레드노드이다 루트는 블랙노드이다 모든 리프 노드는 블랙노드이다 (*리프 노드 : child가 없는 노드) 레드 노드의 child들은 모두 블랙 노드이다 임의의 노드에 대해 그 노드부터 후손 리프 노드까지의 경로에는 같은 수의 블랙노드가 있다 균형 이진 탐색 트리 => 탐색시간 O(log n) 키의 개수 n, 리프의 개수 L 이라고 하였을 때, 전체 노드의 수 = n + L = 전체 edge 수 +1 = 2n +1 L= n+1 레드 블랙 트리 평균 높이 : 원래 트리의 높이를 h, 새로운 트리의 높이를 h' 라 하면 h' >= h/2 검색 연산들은 이진검색 트리와 동일. 삽입, 삭제는 Rotation을 이용하여 수행하다 회전(Rota.. 미가공 필기(알고리즘) 2021. 7. 5. 210630 해싱(Hashing ) 해시 테이블(Hash Table) 찾고자 하는 원소의 키값을 해시함수를 통해 해시 값을 계산하여 그 원소가 저장된 장소를 찾아내는 방법 해시 함수(Hash Function) 모든 가능한 키 값의 집합이 U 라 하고 해시 슬롯의 갯수가 m인 경우 충돌(Collision) : 두 키값의 해시 값이 같을 때 => 충돌 발생시 해결 방법이 효율성을 좌우함 충돌 해결법 연결리스트를 이용한 방법 (Chaining) 오픈 어드레싱(Open addressing) 연결리스트를 이용한 방법 (Chaining) 평균적인 경우 : Simple uniform hashing을 가정시 (각각의 키값이 특정 슬롯에 할당될 확률이 다른 키의 할당에 상관없이 동일하다는 가정) n을 키값의 갯수라고 하고 m을 슬롯의 갯수라고 할 때, 각.. 미가공 필기(알고리즘) 2021. 7. 2. 210629 기수 정렬(Radix Sort) & 카운팅 정렬(Counting Sort) 비교 기반 정렬 알고리즘의 최대 효율 결국엔 숫자열의 모든 가능한 수열 중 하나를 찾아 내는 문제 모든 가능한 순열의 수 : n! 이를 Decistion Tree 를 통해 나타내면 이러한 과정을 통해 비교 기반 정렬 알고리즘의 최대 효율이 O(nlog n) 임을 알 수 있다 그렇다면 비료를 사용하지 않는 정렬 알고리즘은 어떤가? 제한적이지만 O(n)으로 수행가능한 방법들이 존재한다 카운팅 정렬(Counting Sort) 가장 큰 데이터에 따라 효율이 좌우됨 특정 데이터의 개수들을 저장해두고 순서대로 저장된 횟수대로 뱉어내어 정렬하는 방법 위와 같은 방법인데 파란색으로 표시한 1000 이 들어온 경우를 보면 왜 가장 큰 데이터에 효율이 좌우되는지 알 것이다. 가장 큰 데이터가 1000이기에 n이 8 밖에 .. 미가공 필기(알고리즘) 2021. 6. 30. 210629 힙 정렬(heap sort) 우선 힙(heap) 이라는 구조에 대해서 먼저 이야기하면, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨 Complete(or left - complete) binary tree 로 표현 가능 * 가장 낮은 레벨 제외하고 full, 가장 낮은 레벨은 왼쪽부터 채워진 트리 * 우선 순위 큐(Priority Queue)를 구현할 수 있는 자료구조 A가 B의 부모 노드이면, A의 키(Key) 값과 B의 키(Key) 값 사이에는 대소 관계 성립 즉 루트에서 임의의 리프노드( 자식이 없는 노드) 까지 경로는 항상 정렬되어 있다 이진트리는 일반적으로 포인터 사용하여 저장 but left - complete라 배열 사용 가능 두가지 종류 부모 노드의 키 값이 자식 노드의 것 보다 항상 크면 = 최대 힙.. 미가공 필기(알고리즘) 2021. 6. 30. 210628 합병 정렬(merge sort) & 퀵 정렬(quick sort) 합병 정렬(merge sort) : 안정적, 분할 정복 알고리즘(문제를 작은 문제로 분리하고 각각 해결하여 합쳐서 문제를 해결하는 방법) 중 하나 리스트의 길이 0 또는 1이면 정렬된 것으로 취급, 아닌 경우는 비슷한 크기로 잘라 두 개의 리스트로 만듬 각 부분 리스트 재귀적으로 합병 정렬을 통해 정렬함 두 부분 리스트 합병 반복함 단: 만약 배열로 구성한다면 임시 배열 필요 , 제자리 정렬 아님 데이터의 크기가 큰 경우에는 이동 횟수가 많아 매우 비효율적 장 : 안정적인 정렬 방법, 데이터의 분포에 영향 덜 받음, 입력 데이터에 영향 덜 받음 레코드를 연결 리스트로 구성하면, 링크 인덱스만 바꾸면 되기에 데이터의 이동은 무시할 수 있을 정도로 작아짐, 제자리정렬로 구현 가능 큰 데이터 다를 때 연결 리.. 미가공 필기(알고리즘) 2021. 6. 28. 210628 버블 정렬 (bubble sort) & 삽입 정렬 (insertion sort) 버블 정렬(bubble sort) : 인접한 두 원소를 비교하여 정렬하는 알고리즘 n 크기의 배열을 정렬한다고 가정하면 1번째 원소와 2번째 원소를 비교 후 정렬 2번째 원소와 3번째 원소를 비교후 정렬... 반복 n-1번째 원소와 n번째 원소를 비교후 정렬 이것이 한 사이클, 이 사이클을 반복하는데 맨 마지막의 원소는 제외한 범위에서 반복한다 why? 한 사이클을 수행하면 가장 큰 자료가 맨 뒤로 이동하기 때문이다 장 : 구현이 매우 간단하다. 단: 하나의 원소가 가장 왼쪽에서 오른쪽으로 이동하기 위해서는 배열의 모든 다른 요소들과 교환되어야 함, 특정 원소가 최종적인 위치에 이미 있는 경우에도 이동되는 경우 발생함 시간복잡도 비교 횟수 : n-1, n-2,.... 1번 (Best, Worst 일 때 .. 미가공 필기(알고리즘) 2021. 6. 28. 210628 선택 정렬(selection sort) 선택 정렬 (selection sort) : 제자리 정렬 알고리즘 중 하나 입력 배열 외의 다른 추가 메모리 필요 없음 주어진 배열에서 최솟값 찾음 그 값을 맨 앞의 값과 교환함 맨 처음 위치를 제외한 배열 범위에서 1~2번 반복 즉 1,2 번이 하나의 사이클로 한번 할때 마다 배열 내의 가장 작은 원소를 맨 앞으로 땡겨오는 작업을 n번하여 정렬하는 방법이다. 장 : 자료의 이동 횟수가 예상 가능함 단 : 불안정함, 값이 같은 레코드가 있는 경우에 상대적 위치가 변경될 수 있음 시간복잡도 배열의 크기 n 이라 하였을 때 비교 횟수 : n-1, n-2, n-1, .... 2, 1 번 교환 횟수 : 한 번 교환할 떄( swap 함수) 3번 => 최대 3(n-1) 번 그러므로 Best (모두 정렬되어 있는 상.. 미가공 필기(알고리즘) 2021. 6. 28. 210625 시간복잡도와 공간복잡도 성능 평가 성능 분석(performance analysis) - 실행하는 환경에 영향 안 받음 (이론적인 이야기) 성능 측정(performance measurement) - 실행하는 환경에 영향 받음 공간 복잡도(space complexity) : 프로그램 실행하여 완료하는데 까지 필요한 메모리 공간의 양 고정 공간(fixed space) : 프로그램의 입출력에 상관없는 메모리 공간 , 알고리즘과 무관한 공간 ex) 코드 저장 공간단순 변수, 고정된 크기의 배열, 상수 등 가변 공간(variable space) : 프로그램의 입출력에 상관있는 메모리 공간, 알고리즘과 상관있음 ex) 동적 배열 등 총 필요 저장 공간 = 고정공간 + 가변 공간 // S(P) = c + Sp(n) 고정 공간은 상수이므로 공.. 미가공 필기(알고리즘) 2021. 6. 25. 210624 그래프(Graph) 그래프(Graph) : 연결되어 있는 개체간의 관계를 표현하는 자료 구조 트리도 그래프의 일종이라고 볼 수 있다. 그래프의 용어 그래프는 ( V , E ) 으로 표시됨 V는 정점(vertices)들의 집합 E는 간선(edge)들의 집합 정점과 간선은 모두 관련되는 데이터를 가질 수 있음 ( ex - 정점은 도시의 이름 간선은 도로의 길이 등 ) 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(in - degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(out - degree) : 방향 그래프에서 외부로 향하는 간선의 수 단순 경로(simple path) : 경로 중에서 .. 미가공 필기(알고리즘) 2021. 6. 24. 210624 트리(Tree) 트리(Tree) : 계층적인 구조, 노드들로 구성됨, 노드들이 부모 자식 관계 가짐 트리의 용어 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자식들로 이루어진 트리 단말노드(terminal node) : 자식이 없는 노드 비단말노드(non-terminal node) : 적어도 하나의 자식을 가지는 노드 레벨(level) : 트리의 각층의 번호 높이(height) : 트리의 최대 레벨 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 이진 트리(binary tree) : 모든 노드가 2개의 서브 트리를 가지고 있는 트리 노드에는 최대 2개까지의 자식 노드 존재 모든 노드의 차수 2개 이하가 되어 구현하기 편리 노.. 미가공 필기(알고리즘) 2021. 6. 24. 210624 스택(Stack) 과 큐(Queue) 스택(Stack) : 접시를 쌓듯이 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능 top의 위치에서만 원소를 삽입/삭제하기 때문에 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이며 마지막에 삽입한 원소가 가장 먼저 삭제된다. 그래서 후입선출(LIFO , Last In First Out) 구조라고 함 스택의 연산으로는 대표적으로 삽입 연산 : push 삭제 연산 : pop 이 존재하고 조회하는 peek 등 존재함 스택을 응용하는 예시로 시스템 스택이 있음 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로 스택을 이용하여 수행순서 관리하는 것. 실행 순서를 복기하면, 프로그램이 실행을 시작하면 메인 함수가 실행되.. 미가공 필기(알고리즘) 2021. 6. 24. 210623 알고리즘 자료구조란? 컴퓨터에서 어떤 문제를 해결하기 위해 자료의 특성에 따라서 자료를 분류하여 구성하고 저장해 놓은 것 자료구조의 형태 단순 구조 - 정수, 실수, 문자, 문자열 선형 구조 - 순차 리스트, 연결 리스트, 스택, 큐, 덱 비선형 구조 - 트리, 그래프 파일 구조 - 순차 파일, 색인 파일, 직접 파일 알고리즘이란? 알고리즘은 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술한 명세서 알고리즘의 표현 방법 자연어를 이용한 서술적 표현방법 순서도를 이용한 도식화 표현방법 프로그래밍 언어를 이용한 구체화 방법 가상코드를 이용한 추상화 방법 알고리즘과 프로그램의 차이는? 알고리즘은 어떤한 문제에 대한 해결 방법, 프로그래밍 언어, 컴파일러, 시스템에 비의존적 프로그램은 알고리즘을 구현하여 문제를.. 미가공 필기(알고리즘) 2021. 6. 23. 이전 1 2 다음 반응형