스택이란 정의 : 스택은 ‘먼저 들어간 것이 나중에 나오는 자료구조’로써 초코볼이 담겨있는 통에 비유할 수 있다. 스택의 기본 연산 초코볼 통에 초코볼을 넣는다. (push) 초코볼 통에서 초코볼을 꺼낸다. (pop) 이번에 꺼낼 초코볼의 색이 무엇인지 통 안을 들여다 본다. (peek) 스택의 ADT 정의 스택의 배열기반 구현 인덱스가 0인 위치를 스택의 바닥으로 정의해야 배열 길이에 상관없이 바닥의 인덱스 값이 동일해진다. - 인덱스 0의 배열 요소가 '스택의 바닥으로 정의 되었다. - 마지막에 저장된 데이터의 위치를 기억해야 한다. (Top의 위치 중요) push : Top을 위로 한칸 올리고(+1), Top이 가리키는 위치에 데이터 저장 (선 증가, 후 저장) pop : Top이 가리키는 데이터를..
큐의 정의 큐는 먼저들어간 데이터가 먼저 나오고, 나중에 나온 데이터가 나중에 나오는 자료구조이다. 큐는 운영체제 관점에서 보면 프로세스나 스레드의 관리에 활용이 되는 자료구조이다. 이렇듯 운영체제의 구현에도 자료구조가 사용된다. 따라서 운영체제의 이해를 위해서는 자료구조에 대한 이해가 선행되어야 한다. 큐의 ADT 정의 ADT를 대상으로 배열기반의 큐 또는 연결리스트 기반의 큐를 구현할 수 있다. 원형큐의 구조 아래와 같은상황은 F 와 R이 같은 위치를 가리키는 상태가 텅빈 상태를 나타낸다. enqueue 연산시, R이 가리키는 위치를 한칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장한다. dequeue연산시, F가 가리키는 위치를 한칸 이동 시킨 다음에, F가 가리키는 위치에 저장된 데이터를..
앞장에서 배열을 이용한 리스트 구현에 대해서 배웠다. 요약하자면 아래와 같다. 1.ADT (Abstract Data Type) 추상 자료형에 대한이해 2.리스트 자료구조의 특성과 활용 3.리스트 종류 -순차 리스트 : 배열을 기반으로 구현된 리스트 -연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트 4.배열 기반 리스트의 단점 -배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다. -삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다. 5.배열 기반 리스트의 장점 -데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다. 배열과 관련된 예제를 보자. 위의 예제를 보면 배열의 단점을 알 수 있다. "배열은 메모리의 특성이 정적이어서(길이의 변경이 불가능해서) ..
추상 자료형(ADT)의 이해 추상자료형이란? 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것 지갑을 의미하는 구조체 Wallet의 정의 int TakeoutMoney(Wallet* pw, int coinNum, int billNum); -첫번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다. -두번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수를 전달한다. -꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다. void PutMoney(Wallet* pw, int CoinNum, int billNum); -첫번째 인자로 전달된 주소의 지갑에 돈을 넣는다. -두번째 인자로 넣을 동전의 수, 세번째 인자로 넣을 지폐의 수를 전달한다. -넣은 만큼 동전과 ..
재귀함수의 기본적인 이해 javascript 로 구현한 재귀함수 예제 재귀함수의 간단한 예제 팩토리얼의 이해 재귀함수를 이용한 팩토리얼 예제 피보나치 수열 함수의 이해 피보나치 수열 함수의 흐름 재귀함수를 이용한 피보나치 수열 이진 탐색 알고리즘의 재귀구현의 이해 이진 탐색 알고리즘의 재귀구현 참고: 윤성우의 열혈 자료구조
자료구조란 무엇인가? "프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다." 데이터를 표현 : 자료구조 데이터를 처리 :알고리즘 자료구조의 분류 알고리즘을평가하는 두 가지요소 - 시간 복잡도(time complexity) -> 얼마나 빠른가? - 공간 복잡도(space complexity) -> 얼마나 메모리를 적게 쓰는가? *시간 복잡도를 더 중요시 한다. 시간복잡도의평가방법 - 중심이되는 특정연산의 횟수를 세어서평가를 한다. - 데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다. 알고리즘의 수행속도 비교기준 데이터의 수가 적은경우의 수행속도는 큰 의미가없다. 데이터의 수에 따른 수행 속도의 변화정도를 기준으로한다. 최악의 경우와 최상의 경우 순차 탐색 예제 이진탐색 위키백과 ..