본문 바로가기

Data Structure

(4)

선택 정렬(Selection Sort) 선택 정렬(Selection Sort)의 특징 선택 정렬은 배열을 순회하면서 각 단계에서 배열의 나머지 부분 중에서 최소값을 찾아 최소값을 해당 단계의 시작점에 위치한 요소와 교환한다. 이 과정을 반복하여 정렬한다. 제자리 정렬(In-place sorting): 선택 정렬은 추가적인 배열을 필요로 하지 않으며, 배열 내에서 요소들의 위치를 교환하여 정렬한다. 불안정 정렬(Unstable sort): 선택 정렬은 동일한 값을 가진 요소의 상대적 순서가 정렬 과정에서 바뀔 수 있다. 동일한 원소가 초기 배열에서 가진 순서를 보존하지 않는다. 예를 들어, [4, 6, 3, 4, 2, 8] 배열에 중복된 값이 있을 때, 정렬 과정에서 이 두 4 중 어느 하나가 다른 위치로 이동할 때, 그들 사이의 원래 순서가 ..

버블 정렬(Bubble Sort) 버블 정렬의 특징 버블 정렬은 옆에 있는 요소와 비교해서 자신의 위치를 찾아간다. 버블 정렬은 한번 순회할 때마다, 가장 오른쪽 끝자리부터 순차적으로 자리를 찾아간다. 자신의 위치를 찾아가는 형태가 버블 같다고 해서 버블 정렬이라 한다. 기본적으로 데이터의 길이만큼 순회해야 모두 자기 자리를 찾아가게 된다. 아래와 같은 방법으로 데이터의 길이만큼 순회한다. 예를 들어, 아래와 같은 배열이 있다. 작은 수부터 큰 수로 나열한다고 했을 때, [4, 6, 3, 2, 8]; 4, 6을 서로 비교하면 4 3 이기 때문에 두 요소의 위치가 바뀐다. [4, 3, 6, 2, 8]; 6, 2를 비교하면 6 > 2이기 ..

Binary Search Tree Binary Tree 노드에 차일드가 최대 2개까지 붙는 트리를 바이너리 트리(Binary tree)라고 한다. 이진트리(Binary tree) 특징 각 노드가 자식이 없거나, 한 개 혹은 두 개의 자식을 가진다 엄격한 이진트리: 모든 노드가 두 개의 자식을 가지거나 자식이 없는 트리 포화 이진트리: 모든 노드가 두 개의 자식을 가지고 모든 리프 노드가 같은 레벨에 있는 트리 완전 이진트리: 무조건 왼쪽에 자식 노드가 있는 트리 트리의 높이로 각 이진트리의 노드 개수를 추측할 수 있다. Binary Search Tree 이진 검색 트리는 노드를 기준으로 왼쪽 자식 노드는 부모 노드보다 작아야 하고 오른쪽 자식 노드는 부모 노드보다 커야 한다. DFS와 BFS 바이너리 서치 트리를 순회하는 방법에는 깊이 ..

Tree Tree 구조 나무를 뒤집어 놓은 것처럼 하나의 노드(root)로 부터 시작되어 자식 노드(child node)들이 가지를 치듯 뻗어 나가는 구조이다 아래 그림과 같이 HTML이 좋은 예이다. 루트로부터 시작해서 아래 자식 노드들이 뻗어 나가는 구조이다. 트리 구조 용어 루트(root): 부모가 없는 노드 리프(leaf): 자식이 없는 노드 내부 노드: 루트도 리프도 아닌 노드 엣지(edge) or 브랜치(branch): 부모와 자식이 이어지는 연결 선 형제(siblings): 부모가 같은 노드들 path: 루트에서 자식 노드까지 가는 경로 노드의 높이: 루트에서 자식 노드 사이의 엣지(edge) 개수 노드의 깊이: 리프에서 해당 노드 사이의 엣지(edge) 개수 트리의 높이: 모든 노드의 높이 값 중 ..

이전 1 다음

티스토리툴바