1. Intro- 스택은 후입선출(LIFO, Last In First Out) 구조의 선형 자료구조이다.- 데이터를 한 쪽 끝에서만 추가하거나 삭제할 수 있는 특징을 가지며, 보통 접시를 쌓아 올리는 것과 유사한 방식- 즉, 스택에서 가장 나중에 삽입된 요소가 가장 먼저 제거된다. 2. 스택의 주요 특징- 후입선출(LIFO) : -- 가장 마지막에 들어온 데이터가 가장 먼저 나간다.-- 스택의 구조적 특성 때문에 데이터를 삽입하거나 삭제할 수 있는 위치는 Top으로 고정된다. - 한 방향에서만 접근 가능:-- 스택은 끝부분에서만 데이터를 접근할 수 있기 때문에 중간에 삽입이나 삭제를 할 수 없다. 3. 스택의 메소드3.1. push()- 스택의 끝, 즉 Top 위치에 데이터를 추가하는 연산이다. - 데이..
Data Structure
1. Counting Sort?- Counting Sort는 정수로 표현할 수 있는 데이터에 대해 효율적으로 작동하는 O(n) 정렬 알고리즘.- 정렬의 대상이 되는 데이터 값의 범위가 명확할 때 주로 사용.- Counting Sort는 비교 정렬 알고리즘이 아닌 분포 정렬 알고리즘이다. 2. Counting Sort 알고리즘i) 입력 배열과 범위 설정- 주어진 입력 배열이 A라고 하고, 배열의 길이를 n이라고 하자.- 데이터 값은 0 이상 k이하인 양수라고 가정해보자. (이때 k == max(A)) ii) 카운트 배열 초기화- C라는 배열을 만들고, 길이를 k+1로 설정 (또는 max(A) - min(A)로 설정)- C[i]는 입력 배열에서 값이 i인 요소가 몇 번 등장하는지 저장함- C의 초기값은 전..
0. Review- 6-1 에서 우리는 Heap을 알아가는 동안 Max-Heap에 대해서 알아보았다.- 이번 챕터에서는 Max-Heap을 유지하게 해주는 Max-Heapify 에 대해서 알아볼 것이다. 1. Max-Heapify- Max-Heapify 절차는 최댓값 힙 속성을 유지한다.- 입력값은 배열 A, 그리고 배열의 인덱스 i를 받는다.- Max-Heapify는 LEFT(i), RIGHT(i)로 시작하는 Heap들이 이미 Max Heap이라는 것을 가정한다. - 하지만 A[i]가 자식노드보다 작을 경우 Max-Heap을 만족하지 않는다.- 그래서 A[i]를 아래에 있는 노드로 계속 흘려보내면서 Max-Heap을 만족하게 한다.- 다음 그림은 Max-Heapify의 동작을 보여준다. - (a)상황을 ..
1. Introduction- 알고리즘은 다양하게 선택가능하다. - 예를들어 Insertion Sort는 Incremental method(증분 방법)을 사용한다.- 이번 챕터에선 분할 정복(divide and conquer) 이라는 설계 방법을 간단하게 다루게 된다. - 자세한 방법은 챕터 4때 알아보도록 하자. 2. Divide and Conquer(분할 정복)- 많은 유용한 알고리즘들은 재귀적(recursive) 구조를 가지고 있음.- 주어진 문제를 해결하기 위해, 이들은 스스로 한번 이상 호출하여 하위문제들을 해결함- 일반적으로 분할 정복(Divide & Conquer)을 따름- 문제를 원래 문제와 유사하지만 더 작은 크기의 여러 하위 문제로 나누고, - 하위 문제를 재귀적으로 해결한 뒤 이러한 ..
