게으름뱅이의 앞구르기

깊이 우선 탐색(Depth First Search) 맹목적 탐색방법의 하나로 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식 탐색시작 노드를 스택에 삽입하고 방문처리함 스택의 최상단 노드에게 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리함 / 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 2를 더이상 수행할 수 없을 때까지 반복 스택 자료구조에 기초함 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용..

우선순위 큐(Priority Queue) 평범한 큐나 스택과 비슷한 축약 자료형이나 각 원소들은 우선순위를 갖고 있음 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리됨 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리됨 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등에 적용 우선순위 큐 vs. 큐 우선순위 큐 큐 트리구조. 최대 힙*을 이용해 구현함 선형적인 형태 *최대힙(Max Heap) : 부모노드가 자식노드 보다 값이큰 완전 이진 트리. 전체에서 루트 노드가 가장 값이 큼 우선순위 큐 삽입 O(logN)의 시간 복잡도를 가짐 완전 이진 트리를 유지하는 형태로 순차적으로 삽입 삽입 이후 루트 노드까지 거슬러 올라가면서 상향식으로 최대 힙을 구성함..

트리 나무 형태를 뒤집은 것과 같은 형태의 자료구조 루트 : 최상단 노드 리프 : 가장 끝 노드 길이(length): 출발 노드에서 목적지 노드까지 거쳐야하는 가지 수 높이(height): 루트노드에서 가장 깊은 노드까지의 길이 부모 - 자식관계를 가지며, 같은 부모면 형제노드라고함 이진 트리(Binary tree) 최대 2개의 자식을 가질 수 있는 트리 포화 이진 트리(Full Binary Tree) : 리프노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리 완전 이진 트리(Complete Binary Tree) : 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리 높이 균형 트리(Height Binary Tree) 편향트리 : 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이나지 않는 트리 ..

자료구조의 필요성 데이터 효과적으로 저장, 처리하는 방법에 대한 이해 필요 불필요한 메모리 및 성능 낭비를 피하기 위해 기본적인 자료구조 선형 구조 배열 연결리스트 스택 큐 비선형 구조 트리 그래프 자료구조와 알고리즘 효과적인 자료구조 설계를 위해 알고리즘 지식 필요 효과적인 알고리즘 작성을 위해 적절한 자료구조 사용 성능 측정 방법론 시간 복잡도 : 사용되는 연산 횟수 Big-O 표기법 사용하며, 최악의 경우를 나타냄 O(n) ← n 만큼 반복 O(n²) ← 이중 for문을 사용해서 n의 2제곱만큼 반복됨 O(1) ← 한번에 처리됨 O(1) → O(n) → O(nlogn) → O(n²) → O(n³) (순서대로 1000 → 1,000,000 → ... → ...→ 10억번 연산(1초 이상 소요)) 시간..