cs51 [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. [알고리즘 분석]7. Big-Oh Notation(빅 오 표기법) 목차 1. Big-Oh Notation(빅 오 표기법) 2. Big-Oh Examples(예시) 3. Big-Oh and Growth Rate 4. Big-Oh Rules(규칙들) 1. Big-Oh Notation(빅 오 표기법) Big-Oh Notation(빅 오 표기법)을 간단히 설명하면 다음과 같습니다. Input n에 대한 수행시간 함수를 f(n), g(n)이라고 할 시, 아래의 조건들을 만족하면 f(n)은 O(g(n))이라고 할 수 있습니다. 1. f(n) = n0 를 만족하는 2. 두 양의 상수 c와 n0가 존재할시 위와 같은 설명으론 체감이 잘 안되므로, '2n+10이 O(n)이다'로 예시를 들어보면, 1. 2n+10 = 10 3. n 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. [알고리즘 분석]5. Pseudocode(의사 코드) 목차 1. Pseudocode(의사 코드) 2. 의사 코드 문법 1. Pseudocode(의사 코드) Pseudocode(의사 코드)란, 프로그램의 코드를 작성하기 전에, 프로그램의 진행 과정을 간단하게 기록하여 둔 것을 의미합니다. 의사 코드의 특징으로는, 1. 알고리즘 서술 시 많이 사용됨 2. 실제 코드보다 간단함(간단한 설명보다는 정교함) 3. 프로그램 디자인 시 사용함 아래는 의사코드로 배열의 최대값을 지닌 element를 찾는 알고리즘을 표현한 것입니다. 2. 의사 코드 문법 사실 의사 코드에 정해져 있는 문법은 없으나, 많은 사람들이 알아보고 사용하기 위해서 어느정도 정해진 규칙이 있다고 합니다. 1. 반복문 - if ... then ... [else ...] - while ... do .... 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. 이전 1 ··· 3 4 5 6 7 다음
