언제나 휴일

10. 2 순열 문제 바구니에 있는 여러 개의 공을 꺼내는 순서의 조합을 찾는 것은 대표적인 순열 문제입니다. 그리고 확률과 통계를 얘기할 때도 순열 문제는 자주 등장합니다. 바구니에서 공을 꺼내는 문제에서는 바구니에 남아있는 공과 꺼낸 공의 조합이 경험정보입니다. 이러한 경험 정보를 스택을 이용하여 동적 알고리즘으로 해결하면 어렵지 않게 문제를 해결할 수 있습니다. 다음은 이처럼 여러 단계로 나누어 문제를 해결하고 이전 단계에서 다음 단계로 진행할 수 있는 모든 경우의 수를 경험하는 방법으로 해결하는 동적 프로그래밍의 의사 코드입니다.초기 경험 정보를 생성스택에 보관반복(스택이 비어 있지 않다면) 스택에서 경험 정보 꺼내옮 스택에서 꺼내온 경험 정보에서 다음 경험 목록 조사 반복(다음 경험 목록을 순차..

디딤돌 자료구조와 알고리즘 C++ 책 소개 자료구조는 자료를 메모리에 표현하는 구조를 말하며 크게 선형 자료구조와 비 선형 자료구조로 나눠요. 선형 자료구조에는 같은 종류의 자료를 연속적인 메모리에 관리하는 배열과 데이터와 링크로 구성하는 노드들의 선형 집합인 연결리스트가 있어요. 그리고 임시적으로 자료를 보관하는 버퍼로 가장 최근에 보관한 자료를 꺼내주는 스택(Last In First Out)과 가장 먼저 보관한 자료를 꺼내주는 큐(First In First Out)도 선형 자료구조인 배열이나 연결리스트를 이용한 잘 알려진 버퍼입니다. 비 선형 자료구조에는 나무의 뿌리처럼 자료를 보관하는 모습을 계층적으로 표현할 수 있는 트리와 정점과 간선으로 표현하는 그래프 등이 있어요. 이 책에서는 이러한 자료구조..

3.3 스택(Stack) 이번에는 스택을 알아보기로 해요. 스택은 자료를 한쪽으로 보관하고 꺼내는 LIFO(Last In First Out) 방식의 자료구조입니다. 스택에 자료를 보관하는 연산을 PUSH라 말하고 꺼내는 연산을 POP이라고 말합니다. 그리고 가장 최근에 보관한 위치 정보를 TOP 혹은 스택 포인터라 말합니다. 먼저 간단하게 정수를 보관하는 스택을 만들어 보기로 해요. class Stack { 스택에는 자료를 보관할 저장소가 필요합니다. int *buffer; 저장소의 크기를 기억하는 멤버를 선언하세요. const int size; 가장 최근에 보관한 자료의 위치를 인덱스로 기억하는 멤버를 선언하세요. int top; public: 생성자는 스택 크기를 입력 인자로 받게 합시다. Stack..

스택 - 동적 생성, 소멸, C언어 소스 // 스택 - 동적 생성, 소멸 #include #include typedef struct Stack //Stack 구조체 정의{ int *buf;//저장소 int ssize;//저장소 크기 int top; //가장 최근에 보관한 인덱스}Stack; Stack *NewStack(int ssize);//스택 생성자void DeleteStack(Stack *stack);//스택 소멸자int IsFull(Stack *stack); //스택이 꽉 찼는지 확인int IsEmpty(Stack *stack); //스택이 비었는지 확인void Push(Stack *stack, int data); //스택에 보관int Pop(Stack *stack); //스택에서 꺼냄 int m..

스택 - 버퍼를 동적 할당, 정수 형식 보관, C언어 소스 //스택 - 버퍼를 동적 할당, 정수 형식 보관 #include #include typedef struct Stack //Stack 구조체 정의 { int *buf;//저장소 int ssize;//저장소 크기 int top; //가장 최근에 보관한 인덱스 }Stack; void InitStack(Stack *stack, int ssize);//스택 초기화 int IsFull(Stack *stack); //스택이 꽉 찼는지 확인 int IsEmpty(Stack *stack); //스택이 비었는지 확인 void Push(Stack *stack, int data); //스택에 보관 int Pop(Stack *stack); //스택에서 꺼냄 void D..

스택 - 고정 크기 버퍼, 정수 형식 보관, C언어 소스 //스택 - 고정 크기 버퍼, 정수 형식 보관 #include #include #define STACK_SIZE 10 typedef struct Stack //Stack 구조체 정의 { int buf[STACK_SIZE];//저장소 int top; //가장 최근에 보관한 인덱스 }Stack; void InitStack(Stack *stack);//스택 초기화 int IsFull(Stack *stack); //스택이 꽉 찼는지 확인 int IsEmpty(Stack *stack); //스택이 비었는지 확인 void Push(Stack *stack, int data); //스택에 보관 int Pop(Stack *stack); //스택에서 꺼냄 int m..