cs/자료구조37 [Stacks]12. Linked list-based Stack(연결 리스트 기반 스택) 구현 목차 1. Linked list-based Stack(연결 리스트 기반 스택) 구현 2. class Node, S_linked_list 3. class Stack_linked 4. 테스트 1. Linked list-based Stack(연결 리스트 기반 스택) 구현 Linked list-based Stack을 구현할 경우, 1. Singly linked list를 구현한다. 2. append, pop은 모드 singly linked list의 head에서 이루어진다. 3. 이를 기반으로 스택 알고리즘을 구현한다. Singly linked list를 활용하여 스택 알고리즘을 구현할 경우, head에서 append와 pop을 진행하야한다는 사실만 주의하면 됩니다. 지난 Linked list 게시물에서도 언급.. 2021. 2. 20. [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. [알고리즘 분석]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. 이전 1 2 3 4 5 다음
