'👩‍💻 프로그래밍/🎐 알고리즘' 카테고리의 글 목록 (2 Page)

2024.04.15· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 일종의 자기 균형 이진 탐색 트리 이진 탐색 트리의 조회는 O(logn) 시간이 걸리게 되는데, 문제는 균형이 무너질 경우 O(n)까지 시간이 증가할 수 있다는 것이다. 👉 레드-블랙 트리의 가장 큰 특징은 삽입, 삭제 동안 트리의 모양이 "균형 잡히도록" 각 노드들은 red or black 색상을 가진다는 것이다. 검색, 삽입, 삭제 시 최악의 경우에서도 모두 O(logn)이 보장되는 자료구조 🌟 예1. map map은 중복을 허용하지 않는 (key, value) 쌍으로 이루어진 트리 map의 내부 구현은 검색, 삽입, 삭제가 O(logn)으로 동작하는 레드-블랙 트리로 구성되어 있다. 🟩 성질 리프 노드는 따로 key나 data를 포함하지 않으며, 실제 코드에서도 구현되지 않는 "완전 가상의 노드..

2-3-4 트리

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 다음 성질을 만족하는 균형 탐색 트리 2-노드 👉 1개의 키와 2개의 자식을 갖는 노드 3-노드 👉 2개의 키와 3개의 자식을 갖는 노드 4-노드 👉 3개의 키와 4개의 자식을 갖는 노드 각 노드의 한 키와 왼쪽 서브트리에 있는 모든 키 값은 그 키 값보다 작다. 각 노드의 한 키와 오른쪽 서브트리에 있는 모든 키 값은 그 키 값보다 크다. 🌟 노드의 구조 🟩 탐색 🟩 삽입 탐색 과정에서 4-노드를 만나면 항상 노드 분할을 우선 수행 🌟 노드 분할 노드 분할의 유형 부모가 2-노드인 4-노드인 경우 👉 중간 키를 부모로 보내어 3-노드에 연결된 2개의 2-노드로 변환 부모가 3-노드인 4-노드인 경우 👉 4-노드에 연결된 2개의 2-노드로 변환 루트가 4-노드인 경우 👉 3개의 2-노드로 변환 & 루..

이진 탐색 트리(Binary Search Tree)

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🌟 이진 트리 한 노드의 왼쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 작다. 한 노드의 오른쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 크다. 🟩 루트 노드에서부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 탐색 진행 🟩 삽입 연산 삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치에 자식 노드로서 새 노드를 추가 🟩 삭제 연산 삭제되는 노드의 자식 노드의 개수에 따라 구분해서 처리 1. 자식 노드가 없는 경우 👉 남는 노드가 없어 위치 조절 불필요 2. 자식 노드가 1개인 경우 👉 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따로 올림 3. 자식 노드가 2개인 경우 👉 삭제할 노드 왼쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리에 올린다 ..

이진 탐색(Binary Search)

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여 가면서 원하는 값을 가진 원소를 찾는 방법 분할정복 방법이 적용됨 주어진 배열이 정렬되어 있지 않으면 정렬 수행 🟩 탐색 방법 배열의 가운데 원소 A[mid]와 탐색키 key를 비교 🌟 중간 값을 구하는 방식 1. mid : low + (high-low) / 2 2. mid : (low + high) / 2 👉 low + high 값이 (2^31-1)의 범위보다 크다면 음수값으로 오버플로우 발생 가능 1. A[mid] = key 👉 탐색 성공 (인덱스 mid 반환 후 종료) 2. A[mid] key 👉 이진 탐색(원래 크기의 1/2인 왼쪽 부분배열) 순환 ..

순차 탐색(Sequential Search)

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🌟 다양한 탐색 방법 리스트 형태 👉 순차 탐색, 이진 탐색 트리 형태 👉 이진 탐색 트리, 2-3-4 트리, 레드-블랙 트리, B-트리 해시 테이블 👉 해시 함수, 충돌 해결 방법 🟩 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로("순차") 비교하면서 원하는 값을 갖는 원소를 찾는 방법 // A[] : 입력배열 // n : 입력 크기 (탐색할 데이터의 갯수) // x : 탐색 키 SequentialSearch(A[ ], n, x){ i = 0; while (i < n && A[i] != x) i = i + 1; return (i); } // x가 배열 내에 존재하면 인덱스, 아니면 n을 반환 🌟 삽입 및 삭제 🟩 시간 복잡도 탐색, 삭제 : O(n) 삽입 : O(1) 🟩 정렬되지 않고 크기가 작..

버킷 정렬(Bucket Sort)

2024.04.13· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 계수 정렬을 일반화한 것으로 간주 가능 특히 값의 범위가 골고루 퍼져있을 때 유용 EX) 0.0~1.0 사이의 소수점 수를 가진 큰 집합을 정렬 👉 숫자들이 골고루 분산되어 있다면 인덱스 지정이 어렵기 때문에 계수정렬은 적용이 어렵고, 버킷정렬이 유용 🟩 방법 1. 주어진 데이터들의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만든다. 2. 각 데이터를 해당하는 버킷에 넣고 3. 각 버킷을 삽입 정렬과 같은 안정적인 정렬을 수행한 후 4. 버킷 순서대로 각 데이터를 나열하는 정렬 방식 🟩 특징 안정 정렬 (중복된 값의 경우 입력 순서를 무작위로 뒤섞은 상태에서 정렬하는 것) 제자리 정렬 알고리즘 X 🟩 시간복잡도 O(n) 하지만 한 버킷에 입력 키값들이 몰린 경우에는 버킷에 속하는 키들을 정렬하는데..

기수 정렬(Radix Sort)

2024.04.13· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 자리수를 비교하며 정렬을 진행하는 알고리즘 🟩 종류 1. LSD (Least Significant Digit) 기수 정렬 가장 작은 자릿수부터 정렬 진행 (예 : 일의 자릿수부터) Right-to-Left 가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이 MSD에 비해 간결하다. 마지막 자릿수까지 검사를 마친 경우, 오름차순으로 정렬이 완료됨 2. MSD (Most Significant Digit) 기수 정렬 가장 큰 자릿수부터 정렬 진행 Left-to-Right LSD와 비교했을 때, 정렬 상태 확인 등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다. 🟩 특징 및 장단점 정렬 순서상 앞과 뒤의 판단을 위한 비교 연산을 하지 않음 정렬 대상의 모..

계수 정렬(Counting Sort)

2024.04.13· 👩‍💻 프로그래밍/🎐 알고리즘

🌟 비교 기반의 정렬 알고리즘 기본 성능 O(n^2) : 선택/버블/삽입/셸 정렬 향상된 평균 성능 O(nlogn) : 퀵/합병/힙 정렬 👉 비교 기반 정렬 알고리즘의 하한 🟩 이미 얻어진 데이터 분포 정보를 활용하는 정렬 알고리즘 계수/기수/버킷 정렬 👉 선형 시간 O(n) 가능 🟩 데이터 값을 직접 비교하지 않고, 단순하게 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬하는 알고리즘 기존의 정렬 알고리즘들은 위치를 바꾸며 정렬했지만, 계수 정렬은 크기를 기준으로 개수만 세면 되기 때문에 위치를 변경할 필요 없음 🟩 특징 및 장단점 값 비교가 일어나지 않아 속도가 빠르다. 하지만, 개수를 저장하는 배열을 사용해야 하기 때문에 추가 공간 필요 👉 정렬해야할 수의 범위가 작을 때에만 유리하다. EX..

힙 정렬(Heap Sort)

2024.04.13· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 '힙' 자료구조의 장점을 활용한 정렬 최대힙 트리나 최소힙 트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서는 최대힙 (루트가 가장 큼)을 구성하고 오름차순 정렬을 위해서는 최소힙 (루트가 가장 작음)을 구성한다. 🟩 과정 1. n개의 노드에 대한 완전 이진 트리 구성 2. 최대힙 구성 3. 가장 큰 수(루트에 위치)를 가장 끝의 노드와 교환 4. 2와 3을 반복 🟩 시간복잡도 힙과 동일하게 O(nlogn) 최대힙으로 만드는 과정 O(logn), n개의 원소를 다 정렬할 때까지 반복 하므로 🟩 특징 제자리 정렬 (추가적인 공간이 필요하지 않음) 👉 메모리 측면에서 몹시 효율적 cf. 합병정렬 항상 시간복잡도 O(nlogn)을 보장 하지만 단순히 속도만 가지고 비교하면 퀵 정렬이 평균적으로 빠르기..

합병 정렬(Merge Sort)

2024.04.12· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 방법 1. 하나의 리스트를 두 개의 균등한 크기로 분할 (부분 리스트의 사이즈가 1이 될 때까지) 2. 분할된 리스트들을 정렬한 후 3. 정렬된 부분 리스트들을 하나로 합치면서 전체가 정렬된 리스트가 되게 하는 방법 🟩 분할정복 알고리즘 하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘 🟩 시간 복잡도 O(nlogn) 데이터를 절반씩 분할하면서 줄여나가기 때문에 logn만큼의 분할이 이뤄지게 되고 각 분할에서 n번의 값 비교를 통해 위치를 찾아가기 때문에 O(nlogn) cf. 퀵 정렬은 피봇을 어떻게 선택하느냐에 따라 최악의 시간 복잡도가 O(n^2)가 되지만, 합병정렬은 항상 리스트를 절반으로 나누기 때문에 O(nlogn..

퀵 정렬(Quick Sort)

2024.04.12· 👩‍💻 프로그래밍/🎐 알고리즘

🟩피벗 : 보통 주어진 배열의 첫 번째 데이터로 지정 기준이 되는 수(pivot)를 수열 안에서 임의로 하나 선택하여 피봇 이외의 수를 피봇보다 작은 수, 큰 수로 나눈다. 작은 수 < 피봇 1) { // ①피벗을 기준으로 두 부분배열로 분할 // pivot은 제자리를 잡은 피벗의 위치(인덱스)를 표시 pivot = Partition(A[0..n-1], n); // ②왼쪽 부분배열에 대한 퀵 정렬의 순환 호출 QuickSort(A[0..pivot-1], pivot); // ③오른쪽 부분배열에 대한 퀵 정렬의 순환 호출 QuickSort(A[pivot+1..n-1], n-pivot-1); } } int Partition (A[ ], n){ Left = 1; Right = n-1; while (Left < ..

셸 정렬(Shell Sort)

2024.04.12· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 삽입 정렬의 장점은 살리고, 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘 삽입 정렬의 보완 삽입 정렬은 초기 리스트가 "거의 보완"되어 있을 경우 효율적 정렬되지 않은상태의 배열에 대해 단순하게 삽입정렬을 적용하는 것이 아니라 '4-정렬', '2-정렬'처럼 조금이라도 정렬이 된 상태에 가까운 배열로 만든 다음 마지막 삽입정렬을 하는 것 정렬해야 하는 횟수는 늘지만, 전체적으로 요소 이동 횟수가 줄어들어 효율적인 정렬을 할 수 있다. 🟩 순서 1. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입 정렬 수행 2. 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄인다 3. 위의 과정을 그룹의 개수가 1이 될 때까지 반복한다. 🟩 나누는 간격 k 간격 k의 초깃값 : (데이터의 갯수) / ..

티스토리툴바