본문 바로가기

전체 글32

자료구조 4(스택) - 스택 컴퓨터에서 많이 사용되는 자료구조로 후입 선출(LIFO : Last-in-first-out) 형태이다. - 스택의 추상자료형 create : 공백 스택을 생성 is_full : 스택이 포화상태인지 확인 is_empty : 스택이 공백상태인지 확인 push : 스택의 삽입 연산 pop : 스택의 삭제 연산 peek : 스택의 맨 위의 원소를 삭제하지 않고 반환 - 스택의 구현 #include #define MAX 5 typedef struct stack { int stack[MAX]; int top; }Stack; void init_stack(Stack *A) { A->top = -1; } void is_empty(Stack *A) { if(A->top == -1) printf("스택이 공백상태입.. 2023. 1. 9.
자료구조 3(순환 2) - 피보나치수열 피보나치수열은 앞의 두 개의 숫자를 더해 뒤의 숫자를 만든다. $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...$$ 일반적인 피보나치수열의 코드를 알아보자 int fibo(int n) { if(n == 0) return 0; else if(n == 1) return 1; return (fibo(n - 1) + fobo(n - 2)); } 코드는 매우 단순하고 이해하기 쉽지만 비효율적이다. 위의 그림처럼 숫가자 작은 경우에도 똑같은 함수가 여러 번 반복되기 때문에 숫자가 점점 더 커지고 깊이가 점점 깊어질수록 심해지기 때문에 상당히 비효율적이라고 말할 수 있다. 그리고 6이라는 숫자를 구하기 위해서 함수가 25번 호출되었고 이 숫자가 커지면 커질수록 숫자가 기하급수적으로.. 2023. 1. 9.
자료구조 2(순환 1) - 순환 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 -> 즉 재귀 함수를 뜻함 사용 경우 : 팩토리얼의 순환/ 하노이탑 하지만 일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행 속도 면에서는 떨어진다. 따라서 알고리즘을 설명할 때만 순환으로 하고 실제 프로그램에서는 그것을 반복 버전으로 바꾸어 코딩하는 경우도 있음 - 순환의 원리 문제의 일부를 해결한 다음 나머지 문제에 대하여 순환호출을 한다. 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할정복 이라 한다. 순환은 알고리즘의 정의가 순환적으로 되어 있는 경우에 유리한 방법이다. - 순환 알고리즘의 성능 반복 알고리즘과 순환 알고리즘이 단순한 시간 복잡도는 같지만 순환 호출의 경우 여분의.. 2023. 1. 9.
자료구조 1(자료구조와 알고리즘) - 알고리즘 컴퓨터로 문제를 풀기 위한 단계적인 절차 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것/ 특정한 일을 수행하는 명령어들의 집합 - 추상자료형(ADT) 말 그대로 자료 형태를 추상적으로 형태만 정리만 해놓은 것 추상자료형(ADT)가 구현될 때 보통 구현 세부사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개 -> 사용자는 인터페이스만 사용하기 때문에 추상 자료형의 구현 방법은 언제든지 안전하게 변경할 수 있다. 즉 인터페이스만 정확하게 지켜진다면 추상자료형이 여러 가지 방법으로 구현될 수 있음을 뜻함 -> 정보은닉의 기본개념 - 시간 복잡도 알고리즘의 수행 분석 시간을 뜻함 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라 알고.. 2023. 1. 9.

티스토리툴바