자료구조34 [Stacks]11. Array-based Stack(배열 기반 스택) 구현 목차 1. Array-based Stack(배열 기반 스택) 구현 2. 실제 구현 3. size() 4. empty() 5. top() 6. push() 7. pop() 8. 테스트 1. Array-based Stack(배열 기반 스택) 구현 Array를 기반으로 Stack ADT 알고리즘을 구현할 경우 1. 임의의 크기의 array를 선언한다 2. 해당 array의 0번째 부터 들어오는 element를 저장한다. 3. 현재 위치를 t로 저장하며, 해당 위치에서 element를 호출되는 기능에 따라 추가하고, 삭제한다. Array를 기반으로 Stack ADT 알고리즘을 구현할 경우, 가장 큰 문제점이 바로 Array의 최대값에 다다랐을 경우입니다. 이와 같은 경우를 ADT에서 설명하지는 않지만, 구현하고.. 2021. 2. 19. [Stacks]10. Stack ADT(스택) 목차 1. Abstract Data Types(ADTs, 추상 자료형) 2. Stack ADT(스택) 3. Applications of Stack(활용하는 곳) 4. Performance and Limitations 1. Abstract Data Types(ADTs, 추상 자료형) Abstract Data Types(ADTs, 추상 자료형)은 특정 자료구조에 명세된 내용을 의미합니다. 즉, 각각의 ADT는 1. 해당 ADT가 어떤 자료를 지니고 있는지 2. 해당 ADT가 어떤 기능을 취할 수 있는지(탐색, 삽입, 삭제 등...) 이 두가지 해당사항(가이드라인)을 제시해 주는 것을 말합니다. 2. Stack ADT(스택) 위에서 언급한 ADT의 한 종류인 Stack ADT(스택)은 여러 특징들을 가집니다... 2021. 2. 19. [알고리즘 분석]9. Relatives of Big-Oh(빅 오와 유사한 방법들) 목차 1. big-Omega, big-Theta 2. 각각의 특징 1. big-Omega, big-Theta 1) big-Omega - f(n)이 Ω(g(n))과 같기 위해서는 양의 정수 c와 n0가 f(n) >= cg(n), n >= n0을 만족해야 합니다. 2) big-Theta - f(n)이 Θ(g(n))과 같기 위해서는 양의 정수 c와 n0가 c'g(n) 2021. 2. 19. [알고리즘 분석]8. Asymtotic Algorithm Analysis(점근 분석) 목차 1. Asymtotic Algorithm Analysis(점근 분석) 2. Prefix Averages(누적 평균 계산)으로 예시 1. Asymtotic Algorithm Analysis(점근 분석) 알고리즘 수행 시간을 n에 따른 함수로 표현하지 않고 Big-Oh로 표현된다면, 이를 점근 분석이라고 합니다. 점근 분석을 실행하기 위해서는, 1. 알고리즘의 수도코드 작성 2. 각 줄마나 n에 따른 경우의 수 새기 3. 마지막으로 Big-Oh로 표현함 (즉, 총 합이 6n-1일 시 O(n)으로 표현 가능하다) 2. Prefix Averages(누적 평균 계산)으로 예시 Prefix Averages(누적 평균 계산)알고리즘은 기존의 인원 수에서 계산된 평균에서, 추가 인원이 들어왔을 시 이에 따른 평균.. 2021. 2. 19. [알고리즘 분석]6. Running Time - 2 목차 1. Primitive Operations(기본 연산들) 2. Counting Primitive Operations(연산의 개수 새기) 3. Growth Rate of Running Time(수행시간의 증가율) 1. Primitive Operations(기본 연산들) 1) The Random Access Machine(RAM) Model 지난 게시물에서 언급했듯이, 특정 하드웨어/소프트웨어 상황에서 계산을 해볼 경우 그 상황에만 맞는 수행시간이 계산될 것입니다. 따라서, 가상의 컴퓨터를 두고, 이 안에서 계산을 한다고 가정합니다. 이 가상의 컴퓨터는 어떤 memory cell을 사용해도 시간은 일정한 설정으로, 즉 코어는 하나이며, 메모리가 무한이라고 가정한 컴퓨터라고 생각하면 됩니다. 2) Pri.. 2021. 2. 18. [알고리즘 분석]4. Running Time 목차 1. Analysis of Algorithms(알고리즘 분석) 2. Running Time 3. Experimental Studies(실험적 분석법) 4. Theoretical Analysis(이론 분석) 1. Analysis of Algorithms(알고리즘 분석) Analysis of Algorithms(알고리즘 분석)은 Data Structure와 밀접한 연관이 있는 것으로, 간단히 생각하자면 function procedure(연산)이라고 할 수 있습니다. 위의 그림과 같이, 간단히 생각하면 들어오는 Input 값을 Output 값으로 변화시키는 것을 말합니다. 2. Running Time 대부분의 알고리즘은 input 값을 output 값으로 변환시킵니다. 이때, 대부분 알고리즘의 시간은 i.. 2021. 2. 18. [Linked Lists]3. 단일 연결 리스트 구현 목차 1. Singly LInked LIst에 필요한 함수 목록 2. class Node 3. Empty() 4. LIst_size() 5. Print() 6. Append(data) 7. Delete(idx) 8. Insert(idx, data) 9. 테스트 1. Singly Linked List에 필요한 함수 목록 위의 목차에서 추측할 수 있는 내용이지만, Singly LInked List에 필요한 함수의 목록으로는 1. Empty() : 연결 리스트가 비어있는지 확인하는 함수 2. List_size(): 연결 리스트의 크기를 확인하는 함수 3. Print(): 연결리스트에 포함되어 있는 모든 data를 출력하는 함수 4. Append(data): 연결리스트에 data를 추가하는 함수 5. Delet.. 2021. 2. 18. [Linked Lists]2. 단일 연결 리스트 - 2 목차 1. node의 구성 2. 특별한 node 3. Head에서의 삽입 4. Head에서의 삭제 5. Tail에서의 삽입 6. Tail에서의 삭제 1. node의 구성 앞선 게시물에서도 언급하였듯이, node class는 그 node가 지닌 data와, Singly Linked List의 경우 다음 node의 주소값을 지니고 있습니다. 이를 python으로 표현해보면, class Node: def __init__(self, data: int): self.data = data self.next = None 이렇게 나타낼 수 있습니다. 2. 특별한 node Linked List는 크게 2가지 특별한 node가 있다고 할 수 있습니다. 1. Head - 맨 앞 node으로서, LInked List는 시작 n.. 2021. 2. 18. 이전 1 2 3 4 5 다음
