본문 바로가기

대학교 2학년 1학기/자료구조

 (12)
4. 스택 1. 스택 - 후입 선출: 가장 최근에 들어온 데이터가 가장 먼저 나감. 스택의 추상 자료형 - push(s, item): 스택 맨 위에 데이터를 추가, 스택이 가득 차서 입력이 불가능하면 오류 발생. - pop(s): 스택 맨 위에 있는 원소를 삭제하고 반환, 스택에 데이터가 없어서 출력이 불가능하면 오류 발생. - is_empty(s): 스택이 공백상태인지 검사. - is_full(s): 스택이 포화상태인지 검사. - create(size): 최대 크기가 size인 공백 스택을 생성. - peek(s): 스택의 맨 위의 원소를 제거하지 않고 반환. 2. 스택의 구현 - 요소를 저장할 1차원 배열과 top 변수를 구조체로 정의 top 변수: 스택이 비어 있으면 -1의 값을 가짐. 0의 값을 가지면 안 ..
3. 배열, 구조체, 포인터 1. 배열: 타입이 같은 데이터를 하나로 묶는 방법 - 사용 시 연속적인 메모리 공간이 할당. 2. 구조체: 타입이 다른 데이터를 묶는 방법 - c언어에서는 struct 키워드를 이용하여 표기. - struct 키워드와 구조체 태그로 구조체 생성 ex) struct tag s; - 구조체 안에 있는 멤버를 사용하려면 구조체 변수 뒤에 ‘.’(멤버 연산자)를 첨가하여 항목 이름을 적음. - c언어에서는 typedef를 이용하여 구조체를 새로운 타입으로 정의할 수 있음. 3. 포인터: 다른 변수의 주소를 가지고 있는 변수 - & 연산자: 변수의 주소를 추출하는 연산자 - * 연산자: 포인터가 가리키는 장소에 값을 저장하는 연산자 - 포인터를 통해 구조체의 멤버에 접근하는 표기법은 “->” - 배열의 이름 =..
2. 순환 1. 순환 순환: 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 ex) 팩토리얼, 거듭제곱, 피보나치수열, 이항 계수, 이진트리 알고리즘, 이진 탐색, 하노이 탑 등 순환 호출의 내부적인 구현: 복귀 주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수와 지역 변수는 스택으로부터 할당받는데 이러한 시스템 스택 공간을 활성 레코드라고 함. - 순환적인 방법이 반복적인 방법에 비해 빠른 경우: 거듭제곱 계산 O(log₂n) > O(n) - 순환적인 방법이 반복적인 방법보다 느린 경우: 피보나치수열 O(2ⁿ) m = (n-1)/2 - x^2m+1 -> x*x^2m -> x*(x..
1. 자료구조와 알고리즘 1 자료구조와 알고리즘 프로그램 = 자료구조 + 알고리즘 자료구조: 프로그램에서 자료를 처리할 때 자료구조를 사용 알고리즘: 컴퓨터로 문제를 풀기 위한 단계적 절차 - 알고리즘의 조건: 입력, 출력, 명백성, 유한성, 유효성 - 알고리즘의 기술 방법: 자연어, 흐름도, 의사 코드, 프로그래밍 언어 2. 자료형 자료형: 데이터의 집합과 연산의 집합 기초 자료형 - char, int, float, double 파생 자료형 - 배열, 포인터 사용자 정의 자료형 - 구조체, 공용체, 열거형 3. 추상 자료형 추상 자료형: 객체와 연산들의 명세가 구현으로부터 분리된 자료형 - 객체: 추상 데이터 타입에 속하는 객체 - 연산: 추상 데이터 타입과 외부를 연결하는 인터페이스의 역할 4. 알고리즘 복잡도 분석 시간 복..

티스토리툴바