개발에 도움이 되는/자료구조 & 알고리즘 (11) 썸네일형 리스트형 정렬(Sort) 알고리즘 - 정렬 알고리즘 : 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘 - 대표적인 정렬의 종류 1. 버블 정렬 (Bubble Sort) : 두 인접한 원소의 대소를 비교하고, 조건에 따라 자리를 교환하며 정렬하는 방식 - 시간 복잡도 - 평균 : O(n^2) - 최악 : O(n^2) - 장점 1) 구현이 매우 간단하고, 소스 코드가 직관적이다. 2) 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬) 3) 중복된 값을 입력 순서와 동일하게 정렬하는 안정 정렬이다. - 단점 1) 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 굉장히 비효율적이다. 2) 정렬되어 있지 않은 원소가 정렬 되었을 때의 자리로 가기 위해서 교환 .. Float(부동 소수점 자료형)의 숫자 표현법 - Float (부동 소수점 자료형) : 부동이라고 해서 움직이지 않는다라는 뜻이 아니다. 그 반대의 의미로 소수점이 떠다니며 움직인다라는 의미의 부동이다. 컴퓨터는 2진수로 소수를 어떻게 표현할까? 위의 그림처럼 2진수만으로 표현할 수 있었으면 좋겠지만 그렇지 않은 경우가 있다. 예를 들어 0.3 같은 경우에는 0.01001100110011..... 무한 반복이다. 그래서 어쩔 수 없이 컴퓨터는 이를 표현할 수 있는 가장 근사치의 값이 저장된다. 이 근사 값을 저장하는 방법은 두 가지가 있다. 1. 고정 소수점 : 정수를 표현하는 비트 수와 소수를 표현하는 비트 수를 미리 정해 놓고 해당 비트만큼만 사용해서 숫자를 표현하는 방식이다. 예를 들어 실수 표현에 4byte(32bit)를 사용하고 그중 최상위.. 힙(Heap) - 힙 (Heap) 이진 힙(binary Heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(Complete Binary Tree)를 기본으로 한 자료 구조 오로지 부모 노드의 값과 자식 노드의 값 사이에는 대소관계가 성립한다. 형제 사이에는 대소관계는 의미 없음. 우선 순위 큐, 다익스트라 알고리즘 등에 사용 - 힙의 종류 1. 최대 힙 (Max Heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 힙, 가장 큰 값이 루트 노드에 있음 2. 최소 힙 (Min Heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 힙, 가장 작은 값이 루트 노드에 있음 - 힙 표현 : 일반적으로 배열로 표현, 개발 편의성과 가독성 때문에 배열 인덱스 1.. 이진 탐색 트리(Binary Search Tree, BST) - 이진 탐색 트리 (Binary Search Tree) 정렬된 이진 트리로 다음과 같은 규칙을 갖는다. 1. 이진 탐색 트리의 노드에 저장된 값은 유일하다. 2. 부모의 값은 왼쪽 하위 트리 노드들의 값보다 항상 크다. 3. 부모의 값은 오른쪽 하위 트리 노드들의 값보다 항상 작다. 4. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다. BST의 검색에 대한 시간 복잡도는 균형 상태면 O(log n)의 시간이 걸리고 불균형 상태(편향 트리 Skewed Tree)라면 최대 O(n)의 시간이 걸린다. 이러한 문제를 막기 위해 Rebalancing 기법이 등장하였다. (ex. Red-Black Tree 등) - 이진 탐색 트리의 연산 1. 검색 : 이진 탐색 트리에서 특정 요소의 위치를 찾는다. .. 이진 트리(Binary Tree) - 이진 트리 (Binary Tree) 모든 노드들이 둘 이하(공집합 포함)의 자식을 가진 트리 - 이진 트리 유형 1. 전 이진트리 (Full Binary Tree or Strict Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리 2. 완전 이진 트리 (Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리, 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함 3. 포화 이진 트리 (Perfect Binary Tree) : 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖음 4. 균형 이진 트리 (Balanced Binary Tree) : 왼쪽과 오른쪽.. 트리(Tree) - 트리 (Tree) 계층적 관계를 표현하는 비선형 자료 구조, 연결된 비순환 무방향성 그래프 트리 내에 다른 하위 트리가 있고 그 하위 트리안에는 또 다른 하위 트리가 있는 재귀적 자료 구조 - 기본 용어 1. 노드 (Node) : 트리를 구성하고 있는 기본 요소, 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음 2. 간선 (Edge) : 노드와 노드 간의 연결선 3. 루트 노드 (Root Node) : 트리 구조에서 부모가 없는 최상위 노드 4. 부모 노드 (Parent Node) : 자식 노드를 가진 노드 5. 자식 노드 (Child Node) : 부모 노드의 하위 노드 6. 형제 노드 (Sibling Node) : 같은 부모를 가지는 노드 7. 외부 노드 (External Node, Oute.. 그래프(Graph) - 그래프 (Graph) 정점의 집합과 간선의 집합으로 구성된 비선형 데이터 구조 - 정점 : 자료를 저장하려는 자료의 단위 (= 노드) - 간선 : 정점 사이를 연결하는 선으로 두 정점 쌍(n1, n2)으로 표현 - 방향성(유향) 간선 (Directed edge) : 뱡향을 가진 정점의 쌍(u, v)으로 화살표로 표현하고 단방향을 가리킴 u는 출발점 v는 도착점을 의미. 방향성 간선을 가진 그래프를 방향성 그래프(Directed Graph)라고 함. - 무방향성(무향) 간선 (Undirected edge) : 방향이 없는 정점의 (u, v)으로 직선을 표현하며 양방향을 가리킴 간선 (u, v)와 (v, u)는 같다. 무방향성 간선을 가진 그래프를 무방향성 그래프(Undirected Graph)라고 함... 해시 테이블(Hash Table) - 해시 테이블 (Hash Table) Key 값을 해시 함수를 통해 변환한 값(해시 값)을 index로 삼아 Value 데이터를 저장하는 자료 구조이다. 내부적으로 배열을 사용하여 데이터를 저장하고, 고유의 index로 접근하기 때문에 빠른 검색 속도(충돌이 일어나지 않는 경우에 O(1))를 갖는다. 대표적인 해시 함수로는 Key 값을 테이블 크기로 나누어 계산(ex. 해시 값 = Key % 테이블 크기)하는 Division Method과 문자열을 키로 사용하는 해시 테이블에 잘 어울리는 알고리즘으로 Key 값을 ASCII 코드로 바꾸고 값을 합한 데이터를 이용하는 Digit Folding 등이 있다. 하지만 문제는 아무리 좋은 해시 함수를 이용한다해도 비둘기집의 원리에 의해 충돌이 발생할 확률이 있다.. 이전 1 2 다음
