Stack 이름에서 알 수 있듯이 후입선출하는 형태의 자료구조. 접시를 쌓아서 보관하는 것을 예로 들 수 있다. ADT 객체 : 0개 이상의 원소를 가지는 유한한 길이의 선형 리스트 연산 : create(size) ::= 최대 크기 size인 스택 생성 is_full(s) ::= 스택의 모든 자리에 원소가 차있다면 true 반환 is_empty(s) ::= 스택이 모두 비어 있다면 true반환 push(s,item) ::= s스택에 item원소 추가 pop(s) ::= s스택의 가장 위 원소를 반환하고 제거한다. peek(s) ::= s스택의 가장 위 원소를 반환한다.
분류 전체보기
Stack 이번 챕터에서는 스택에 대해서 다룬다. 스택, ADT 배열 구현 구조체 활용 동적 할당 활용 괄호 검사 수식 표기(전위, 중위, 후위) 수식 변환 미로탐색
구조체 구조체는 타입이 다른 데이터를 하나로 묶는 방법이다. 배열은 타입이 같은 데이터를 하나로 묶는다. 구조체는 각 요소를 멤버(필드)라고 하고, 멤버 변수의 이름으로 접근한다. 배열은 각 요소를 인덱스로 접근한다. 선언 선언은 struct 키워드를 통해서 다음과 같이 한다. 접근은 맴버 변수의 이름을 통해 접근한다. Typedef C언어에서 typedef 키워드는 기존 타입에 새로운 이름을 붙일 때 사용한다. 구조체 변수를 선언할 때 매번 앞에 struct를 작성해야한다는 번거로움이 있으므로 typedef를 통해 코드를 한 단어라도 줄여볼 수 있다.
배열 배열은 같은 타입의 변수 여러개 만드는 경우에 사용한다. ADT 객체 : 쌍의 집합 연산 : create(size) ::= size개의 요소를 저장할 수 있는 배열 생성 get(A, i) ::= 배열 A의 i번째 요소 반환 set (A, i, v) ::= 배열 A의 i번째 위치에 v값 저장
배열 구조체,포인터 앞으로 배우게 될 자료구조를 학습하는데 있어서 기본이 되는 배열, 구조체, 포인터와 관련 알고리즘에 대해서 배워보도록 한다. 문법에 대한 이야기는 대부분 생략하고 작성한다. 배열 구조체 다항식 표현 희소행렬 포인터 동적 할당 구조체와 포인터
피보나치 수열 피보나치 수열의 경우에는 순환 호출을 사용하면 비효율적인 예시이다. 피보나치 수열은 다음과 같이 공식으로 표현한다. 구현과 성능 순환 호출과 반복문을 각각 활용하여 피보나치 수열의 값을 계산하는 함수를 구현하자. 구현을 통해서 왜 피보나치 수열에서 순환 방식이 반복보다 비효율적인지 알아본다. 순환 종료 조건 : n이 1이나 0인 경우 fib(n)=fib(n-1)+fib(n-2)로 순환 호출하여 계산한다. 순환호출로 함수를 구현하면 사실 알아보기 쉽고 간단해 보인다. 그러나 외연과 달리 효율성은 저멀리로 :D 날아간 코드라고 할 수 있겠다. 먼저 이 함수를 살펴보면, 함수 내에서 비교연산을 한번 수행하고, 이후 2개의 fib함수를 호출하여 연산한다. 따라서 n을 처음 넣었을 때, fib함수 ..
거듭제곱 X^n을 계산하는 알고리즘을 순환 방식과 반복 방식으로 작성할 수 있다. 먼저 결론을 말하면, 거듭 제곱은 앞선 팩토리얼과 달리 순환적인 방법이 더 효율적인 예제이다. ! 팩토리얼의 경우 순환, 반복 두 경우의 시간복잡도가 같았지만, 공간복잡도가 순환방식에서 더 컸기 때문에 반복 구현이 더 효율적임을 이전 포스팅에서 알아보았다. https://he-kate1130.tistory.com/26 [자료구조] 2. 순환 - 팩토리얼 팩토리얼 중등 교육과정을 겪어본 사람이라면 모두가 아는 팩토리얼!! 오늘은 팩토리얼을 계산하는 함수를 순환을 통해 구현해보자. 순환 알고리즘 앞선 포스팅에서도 말했지만, 순환 알고리즘 he-kate1130.tistory.com 구현 반복 순환 성능 시간복잡도를 통해 성능을 ..
팩토리얼 중등 교육과정을 겪어본 사람이라면 모두가 아는 팩토리얼!! 오늘은 팩토리얼을 계산하는 함수를 순환을 통해 구현해보자. 순환 알고리즘 앞선 포스팅에서도 말했지만, 순환 알고리즘은 알고리즘 내에서 자기 자신을 호출하는 방식으로 문제를 해결한다. 예상할 수 있는 순환 알고리즘의 가장 큰 문제점은 알고리즘의 종료에 있다. 알고리즘에 순환의 종료시점을 구현하지 않는다면, 알고리즘은 무한히 반복될 수 있다. 따라서 순환 알고리즘을 구현할 때, 순환부와 종료부를 확실하게 구현하도록 하자! 착오 없이 순환 알고리즘을 구현하려면, 큰 문제를 작은 부분문제로 생각하는 것이 중요하다. 알고리즘을 통해 해결하려는 문제점을 동일한 알고리즘의 작은 문제로 나누어 생각해야 순환부를 작성할 때 착오가 생기지 않는다. 정리하..
