반응형 자료구조15 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort)는 배열 속의 모든 값을 비교해서 서로 자리를 바꾸는 알고리즘이다. 인접한 원소와 인접한 원소의 크기를 비교해서 자리를 바꾸는 알고리즘이다. ADL은 다음과 같다. bubbleSort(a[],n) for (i = 1; i 2021. 10. 22. 선택 정렬 선택 정렬(Selection Sort)은 매우 간단한 알고리즘이다. 가장 작은 숫자의 index를 선택하고 이를 배열의 맨 처음 값과 비교해서 자리를 바꾸는 것이다. ADL은 다음과 같다. selectionSort(a[],n) for (i 2021. 10. 22. Red-black Tree 유명한 알고리즘인 Red Black Tree에 대해서 알아보자 복잡도는 다루지 않을 것이며 삽입 과정만 다루겠다 Red Black Tree를 이해하기 위해선 2-3-4 트리의 이해가 우선적으로 되어야지 조금 쉽다. 왜냐하면 2-3-4 트리의 단점을 극복하기 위해 제안된 것이 Red-Black Tree 이기 떄문이다. Red = 다수의 노드, black은 보통 이라고 임의로 정의한다 Red Black Tree는 3가지 핵심 규칙이 있다. 1. Root node는 모두 black이다. 2. Root에서 외부노드(끝)까지의 경로 상에는 연속된 2개의 Red node가 포함되지 않는다. 3. 루트에서 각 외부 노드까지의 경로에 있는 Black node의 수는 모두 같다. 그리고 Red-Black Tree는 Bi.. 2021. 10. 22. Linked List - C와 Python 비교 - 개념 Linked List는 말 그대로 연결된 리스트를 말한다. 지금까지의 큐와 스택 등은 모두 배열 구조로 구현하였지만 이를 연결된 자료구조로 변환하겠다. 연결을 위해선 node의 구현이 필요하고 이 노드는 데이터와 함께 링크를 갖는다. 각 항목은 다음 노드를 가르키는 링크를 가져서 이를 연결시켜주면 되는 방식이다. 이 연결의 개념을 통해 더욱 복잡한 트리나 그래프와 같이 더 복잡한 구조도 효율적으로 표현할 수 있다. 또한, 용량이 고정되지 않아서 메모리를 효율적으로 활용할 수 있다. 또한, 중간에 자료를 삽입하거나 삭제하는 것이 용이하다. 하지만 이의 단점은 n번째 항목에 접근하는데의 시간복잡도는 O(n)이라는 것이다. 그리고 배열구조에 비해 상대적으로 구현이 어렵다는 점이다.(오류도 빈번) 연결리스트의 .. 2020. 7. 15. queue - 3 우선순위 큐에 대해 구현해보자. 보통 우선순위 큐는 heap정렬 알고리즘을 이용해 구현하지만 heap을 이용하지 않고 우선순위 큐를 구현해보겠다. 우선순위 큐란 모든 데이터가 우선순위를 가지고 있고 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력되는 구조이다. 즉 내림차순 정렬이라고 생각하면 된다. 우선순위 큐는 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어진다. 보통은 최대 우선순위 큐를 사용한다.(우선순위 높은 데이터가 먼저 삭제되는) 우선순위 큐는 다른 큐들과 다른 점이 일렬로 나열되어 있지 않다는 것이다. 우선순위 큐는 한 순간에 가장 우선순위가 높은 항목만 알 수 있으면 된다. 이를 heap이 아닌 list를 통해 구현해보겠다. class Prior.. 2020. 7. 15. Queue - C와 Python 비교 - 2 지난 원형큐 설명에 이어 deque(덱 큐)에 대해 설명하겠다. 덱 큐는 원형큐에 비해 매우 파워풀하다. 원형큐는 front가 삭제 rear가 삽입으로 정해져 있었다면 그에 비해 덱큐는 front와 rear가 모두 삭제와 삽입이 자유롭다는 것이다. 사실 이는 덱이라고 불리지만 원형큐로 구현하면 시간복잡도가 O(1) 이기 때문에 효율적이다. 그래서 덱큐라고 명칭한다. 덱큐와 원형큐가 다른 점은 앞서 말했듯이 front와 rear가 모두 삭제가 가능하다는 것이다. 이를 구현하기 위해선 원형큐에선 시계방향의 회전만 했다면 덱큐는 반시계방향 회전을 한다. 이로 인해 delete_rear와 add_front가 구현될 수 있다. 덱큐는 원형큐를 상속하여 구현해보겠다. 일단 python코드이다. # 덱큐 -> 원형큐.. 2020. 7. 13. 이전 1 2 3 다음 반응형
