Koo's.Co

파이썬에서 제공하는 리스트를 사용하면 스택의 기능을 모두 사용할 수 있다. push연산은 append, pop연산은 그대로 pop을 이용하면 된다. 여기서는 노드를 이용해 스택을 구현해보려 한다. 구현하려는 스택의 추상 데이터 타입은 다음과 같다. empty() : 비었다면 True를, 아닐 경우 False를 반환 push(item) : 스택에 item을 삽입 pop() : 스택에 마지막으로 들어온 item을 반환, 스택이 비어있는 경우 False를 반환 peek() : 스택에 마지막으로 들어온 item을 반환 __len__() : 스택에 크기를 반환 1. 노드 class Node(object): def __init__(self, item, pointer): self.item = item self.poi..

스택이란? 스택은 원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 선형 자료구조이다. 나중에 들어온 원소가 제일 먼저 나가는 후입선출(LIFO: Last In First Out) 구조를 갖는다. 책을 상자 안에 쌓아서 넣을 때, 나중에 쌓은 책을 먼저 빼는 모양을 생각할 수 있다. 스택 안에 원소를 집어넣는 push연산, 삽입된 원소를 빼내는 pop연산, 제일 위에 있는 원소값을 반환하는 peek연산을 갖는다. 컴퓨터 내부에서 프로그램에 대한 정보를 저장하는 자료구조에도 쓰이는 등 컴퓨터 내부에서도 많이 사용된다. 간단하게 구현가능하면서도 여러 상황에 응용할 수 있어 많이 쓰이는데 힙 영역에 데이터를 저장하거나 재귀함수를 호출하는 과정도 스택 형태로 사용된다.

단순 연결리스트는 한 방향으로만 링크를 갖는 구조이다 구현하려는 단순 연결리스트의 추상 데이터 타입은 다음과 같다 isempty() : 비었다면 True를, 아닐 경우 False를 반환 add_first(item) : 연결리스트의 첫 번째 자리에 item을 삽입 add_last(item) : 연결리스트의 마지막에 item을 삽입 insert(pos, item) : pos 위치에 item을 삽입 (첫 번째 자리는 0부터 시작한다) remove(target) : target이 존재할 경우 target을 제거 search_target(target) : target이 존재할 경우 pos를 반환, 없을 경우 False를 반환 search_pos(pos) : pos위치에 존재하는 값을 반환, 없을 경우 False를..

연결 리스트란? 연결 리스트는 값과 다음 노드에 대한 포인터(주소값)으로 이루어진 선형 리스트이다. 마지막 노드는 Null값을 갖는다. 연결리스트는 연속적인 주소 값을 갖는 배열과 자주 비교된다. 노드의 구성에 따라 단순 연결 리스트, 이중 연결리스트, 원형 연결 리스트가 있다 ※ 연결 리스트와 배열의 비교 배열 특징 값이 연속된 메모리에 순차적으로 저장 장점 - 인덱스를 통한 빠른 접근이 가능 - 구현이 쉽고 직관적이다 단점 - 미리 값을 할당하므로 저장공간이 부족할 경우 오류가 발생 - 반대로 너무 많은 저장공간을 할당할 경우 메모리 낭비가 커짐 - 추가, 삭제 연산을 할 때 연산수가 많아짐 -> 원소의 이동수가 많아진다 연결 리스트 특징 - 값이 연속된 메모리에 저장되지 않고 임의 주소에 저장됨 -..

1. 추상적(Abstract)? 추상적이란 구체적의 반대되는 말로 "사물 전체에서 분리시켜 특성, 특징에 집중하는 것"을 말한다 구체적이란 말은 세부적인 하나하나의 특성을 모두 고려하는 것을 말한다. 추상적이란 말과 모호하다는 말이 혼동될 수 있는데, 추상적이라 함은 정말 핵심적인 특성에만 집중하는 것을 의미하고 모호하다는 것은 분명하지 않은 것을 의미한다. 2. 추상 데이터 타입(ADT) 데이터 타입은 데이터의 집합과 해당 데이터에 적용할 수 있는 연산으로 구성된다. int 데이터 : ..., -2, -1, 0, 1, 2, ... 연산 : +, -, *, /, % ADT는 새로운 데이터 타입을 추상적으로 정의한 것을 말한다. 데이터와 연산이 정의되지만 이들을 어떻게 구현할 것인지는 정의되지 않는다. 즉..