전체 글 썸네일형 리스트형 [알고리즘] 버블 정렬(거품정렬, Bubble Sort) 버블 정렬이란 (거품 정렬, bubble sort) 버블 정렬은 서로 인접한 두 원소의 크기를 비교하여 정렬하는 방법이다. 구현은 간단하나 시간복잡도가 O(n^2) 으로 상당히 비효율적이다. 버블 정렬 예시 및 시간복잡도 증명 간단한 예시를 통해 버블 정렬 과정을 나타내면 다음과 같다. 위 그림에서 확인할 수 있듯이, 5개의 요소를 거품 정렬을 적용해서 정렬하면 비교연산이 4회 + 3회 + 2회 + 1회 = 10회 소요되는 것을 확인할 수 있고, 요소의 개수를 N개로 일반화하면 (N-1) + (N-2) + (N-3) + ... + 2 + 1 가 된다. 이를 공차가 1인 등차수열 공식에 대입해보면, 결과적으로 N*(N+1) / 2 임을 알 수 있다. 이를 시간복잡도로 표현해보면 O(n^2) 임을 확인할.. 더보기 [알고리즘] 선택정렬(Selection Sort) 선택 정렬 선택 정렬이란 제자리 정렬 알고리즘 중 한가지 방법이다. 보통 오름차순으로 정렬되는 선택 정렬은 다음과 같은 과정으로 이루어져 있다. 가장 작은 원소 값을 찾는다. 그 값을 맨 앞에 있는 값과 교체를 한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다. 선택 정렬 예시 예시를 통해 좀 더 자세히 살펴보자. 위 그림과 같이, [5, 3, 8, 1, 2, 7] 로 구성된 배열이 있다고 하자. 앞에서부터 탐색하여, 가장 작은 원소 1을 찾은 후 맨 앞의 값 5와 교체한다. 1의 위치를 확정짓고 [3,8,5,2,7] 중 가장 작은 수 2를 맨 앞의 값 3과 교체한다. 같은 방법으로 [8,5,3,7] 중 가장 작은 수 3과 맨 앞의 값 8.. 더보기 [자료구조] 트라이 (Trie) 트라이란? 문자열 집합에서 어느 한 개의 문자열을 탐색하는 알고리즘은 무엇이 있을까? 최대 길이가 m인 문자열 n개의 집합이 있다고 가정해 보자. 가장 간단하지만 시간복잡도가 높은 방식은 무작정 순회를 돌며 찾는 방식인 brute force이다. 최대 길이가 m인 문자열 n개의 집합에서, 원하는 문자열이 있는지 찾는다면 비교횟수는 O(mn)이 된다. 이를 좀더 개선하는 방식으로 이진 탐색을 활용하면 좀더 낮은 시간복잡도를 갖게 된다. 이진 탐색을 사용하면 O(mlogn)으로 단축 시킬 수 있지만, 정렬 과정 자체에 O(nmlogn)의 시간이 걸려서 이 또한 비효율적인 방식이라고 볼 수 있다. 이를 모두 개선하기 위한 문자열 집합 검색법이 바로 트라이(Trie)라는 자료구조이다. 이를 트라이 알고리즘이 .. 더보기 [자료구조] 해시 테이블 해시 테이블 해시 테이블이란 연관배열 구조를 이용하여 (Key, Value)로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있는 자료구조이다. 기본 연산으로는 탐색, 삽입, 삭제가 있다. TIP 연관배열 구조란 키(Key) 1개와 값(Value) 1개가 1:1로 연관되어 있는 자료구조이다. 해시 테이블 연산 ① 삽입 해시 테이블에서 자료를 저장하기 위해서는 해시 함수(Hash Function)를 통하여 키(Key)를 -> 해시(Hash)로 변경해야 한다. 위 사진의 해시 함수는 input key를 7로 나눈 나머지이므로 첫 번째 데이터의 키는 76, 해시는 6이 된다. 미리 준비해놓은 0 ~ 6의 저장소 중에 맞는 해시값을 찾아 해당 값을 저장한다. 해시 함수로 해시를 얻어내는 과정에서.. 더보기 [자료구조] 레드 블랙 트리 레드-블랙 트리 (Red-black tree) 란 ? 레드-블랙 트리는 자가 균형 이진 탐색 트리의 한 종류이며, 앞서 살펴본 이진 탐색 트리가 탐색 시 최악의 경우 시간복잡도가 O(n)인 부분을 몇 가지 조건을 통해 균형 잡힌 트리로 만들어 최악의 경우에도 탐색 시 O(logn) 을 보장하는 자료 구조이다. 레드-블랙 트리의 조건 이진 탐색 트리가 가진 조건에서 다음 조건을 만족해야 레드-블랙 트리라고 할 수 있다. 모든 노드는 Red이거나 Black이다. 루트 노드는 Black이다. 모든 리프노드(단말노드)는 Black이다. 노드가 Red이면 그 자식은 Black이다. No Double Red => Red 노드가 연속으로 나올 수 없음 루트노드에서 모든 리프노드까지의 경로에서 만나는 Black노드.. 더보기 [자료구조] B-Tree & B+Tree 1. B-Tree란? B-Tree는 자식 노드의 개수가 2개 이상인 트리를 말한다. 이진트리가 자식 노드가 최대 2개인 트리를 말하는 것인데, 이 이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree이다. 2. B-Tree의 구조 그림의 네모 칸 하나 하나를 '노드' 라고 하며, 가장 상단의 노드를 '루트 노드(Root Node)', 중간 노드를 '브랜치 노드(Branch Node)', 가장 하단의 노드를 '리프 노드(Leaf Node)' 라고 한다. 안의 구조를 자세히 살펴보면 다음과 같다. 위 그림에서 보듯이, 노드당 데이터를 2개 이상 가질 수 있으며 자식 노드를 자신의 데이터 수 이상으로 가질 수 있다. 즉, 노드의 데이터가 N개이면, 자식 수는 N+1개가 된다.. 더보기 [자료구조] 이진탐색트리 1. 이진탐색트리란? 이진탐색트리란 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진 탐색 연결 리스트 장점 탐색에 소요되는 시간복잡도가 O(logN) 로 빠르다 삽입과 삭제에 걸리는 시간 복잡도가 O(1)로 빠르다 단점 삽입과 삭제가 불가능하다 탐색의 시간 복잡도가 O(N) 이다 위와 같은 이진 탐색과 연결리스트의 장점을 고안하기 위해 만들어졌으며, 이진 탐색의 효율적인 탐색 능력을 유지하면서도 빈번한 자료 입력과 삭제가 가능하기 위해 사용된다. 2. 이진탐색트리 특징 이진탐색트리는 이진트리의 일종으로 다음과 같은 규칙으로 구성한다. 모든 노드는 유일한 키를 갖음. (중복된 노드 X) 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값.. 더보기 [자료구조] 힙(Heap) 에 대하여 힙이란? 힙(Heap)이란, 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조이다. 키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap)이라 하고, 키 값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다. 아래 그림은 최대 힙과 최소 힙의 예시이다. 힙의 연산 힙에는 새로운 원소를 추가하는 삽입 연산, 루트 노드에 있는 원소를 삭제하는 삭제 연산 두가지가 존재한다. 다만, 힙은 항상 부모노드를 최대 힙일 경우 최대, 최소 힙일 경우 최소로 유지해주어야 하는 특성이 있다. 최대 힙 : 부모노드의 키 값 >= 자식노드의 키 값 최소 힙 : 부모노드의 키 값 더보기 이전 1 2 3 4 5 ··· 24 다음 목록 더보기
