본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[알고리즘-이론] 09 집합의 처리 집합의 처리 상호 배타적인 여러 개의 집합을 처리해야 할 경우가 있는데 최소 신장 트리를 위한 크루스칼 알고리즘에서 상호 배타적인 집합을 처리하는 알고리즘이 필요하다. 집합의 관리에서 필요한 연산은 임의의 원소가 어느 집합에 속하는지 알나내는 연산과 두 집합을 합하는 연산이다. 여기서 말 하는 상호 배타적인 집합은 서로의 교집합이 공집합인 경우를 뜻한다. 연결 리스트를 이용한 집합의 처리 연결 리스트를 이용한 표현은 쉽고 직관적이다. ++각 원소당 하나의 노드를 만들고 이들을 연결리스트로 연결한다++ 노드는 두 개의 포인터와 원소를 갖는 한 개의 필드로 이루어 진다. 다음 원소 포인터 -> 다음 원소를 가리키는 포인터. 각 집합에는 마지막 원소를 가리키는 tail이라는 변수를 둔다. 대표 원소 포인터 -.. 2019. 11. 23.

[알고리즘-이론] 해시 테이블 (Hash Table) 해시 테이블 해시 테이블은 검색의 평균 시간 복잡도가 O(1)이 되는 검색에 최고의 알고리즘이다. 검색 트리는 원소가 저장될 자리가 이미 트리에 존재하는 원소와 비교하여 결정되는 반면, 해시 테이블은 원소가 저장될 자리에 값에 의해 결정되는 자료구조이다. 해시 테이블은 단계적으로 검색키 -> 주소 계산 -> 테이블 참조 의 흐름으로 검색이 이루어진다. 검색 키 해시 함수 h(x) = x mod m에 의해 검색 키가 결정되고 x는 사용자 입력 값,(배열 값) m은 해시 테이블의 크기를 뜻한다. 주소 계산 주소 계산은 검색 키를 통해서 x mod m을 실질적으로 행하는 과정이다. 테이블 참조 검색 키를 통한 주소 계산이 이루어진 후 검색을 하는 단계이다. 원소가 저장될 자리가 값에 의해 결정되므로 평균 한 .. 2019. 11. 23.

[알고리즘-이론] 레드 블랙 트리(Red-Black Tree) 레드-블랙 트리(Red-Black Tree) 이진 검색 트리에서 시간 복잡도는 O(log n)이 될 수도 있고 O(n)이 될 수도 있다고 하였는데 이는 트리의 높이에 따라 결정된다고 했다. 이러한 단점들을 극복하기 위해서 고안해 낸 것은 바로 ==균형잡힌 이진 검색 트리== 이다. 균형잡힌 이진 검색 트리란 것은 최악의 경우 에도 이진 트리의 균형이 맞게 유지되도록 하는 것을 뜻한다. 레드 블랙 트리는 이진 검색 트리의 모든 노드에 레드 또는 블랙의 색상을 칠하는데 다음과 같은 성질을 만족해한다. 1. Root Property: 루트는 블랙이다. 2. External Property: 모든 리프(NIL)는 블랙이다. 3. Internal Property: 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.. 2019. 11. 23.

[알고리즘-이론] 이진 검색 트리(Binary Search Tree) 이진 검색 트리(Binary Search Tree) 이진 검색 트리에 대해서 공부하기 전에 트리에 대해서 먼저 알고 넘어가자 ##트리(Binary Search Tree)란? 트리란 자료들이 List, Stack, Queue와 같은 1:1 관계의 선형 구조가 아닌 1:n 관계의 비선형 구조로 계층 관계로 만들어진 계층형 자료구조라고 한다. 위의 그림에서 숫자들은 아래의 숫자들을 연결하는 관계를 갖고 이를 부모-자식 관계라고 한다. 형제 관계란? 30은 아래로(계층적으로) 20과 40이 연결되어 있다면 부모는 30이 되고 자식은 각각 20과40이 되며 이 둘은 서로 형제관계 라고한다. 노드란? 이 때 30은 부모 노드가 되고 20과 40은 각각의 자식 노드라고 불린다. 이를 미루어 보았을 때 노드는 각각의 .. 2019. 11. 23.

[알고리즘-이론] 퀵 정렬 (Quick Sort) 퀵 소트(Quick Sort)란? 퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 바로 예로 설명을 하자면 정렬할 배열 A={31,11,2,6,9} 가 주어진다. 이 때 기준 원소를 중심으로 그 값보다 큰 원소는 뒤에, 작은 원소는 앞에 배치를 하는 식으로 정렬이 이루어진다. 기준 원소를 잡는다. 기준 원소의 왼쪽은 기준 원소보다 작은 값, 오른쪽은 기준 원소보다 큰 값. 왼쪽에 대해서도 재귀호출을 실행한다. 오른쪽에 대해서도 재귀호출을 실행한다. 1라운드 기준 원소를 잡는다 -> 기준원소: 9 -> 기준원소를 기준으로 A[0]부터 값을 비교하며 재배치 한다. -> A={2, 6, 9, 31, 11}; 2라운드 기준 원소를 잡는다 -> 기준원소: 11 -> 기준.. 2019. 11. 23.

[알고리즘-이론] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort)란? 병합정렬은 앞서 설명한 선택 정렬, 버블 정렬, 삽입 정렬과는 비교 할 수 없는 시간 복잡도인 O(n log n)의 알고리즘이다. 현대의 컴퓨터 개념의 시초가 되었떤 폰 노이만(John von Neumann)이 제안한 방법으로 분할 정복 알고리즘중 하나이다. 재귀 호출을 사용하여 정렬의 효율을 극대화 시켰다. 과정 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 부분의 배열으로 나눈다. 각 부분 배열의 크기가 0이 될 때 까지 반복하고 0이 되면 각 부분을 재귀적으로 합치는 과정을 수행한다. 합치는 과정이 수행될 때 실질적 정렬이 이루어진다. 이런식으로 진행하면 단계를 세 단계로 나눌 수 있다. 1. 분할 : 입력 배열을 같은 크기의 2 개의 부분 배열로 분할한다.. 2019. 11. 23.

이전 1 ··· 21 22 23 24 25 다음

티스토리툴바