알고리즘 정리

1. 정적배열 vs 동적배열

정적배열은 입력받는 값과 상관없이 배열을 미리 만들어 놓아서 메모리 낭비가 있음

동적배열은 입력받기 전까지 배열을 미리 만들어 놓지 않고, 입력 받은 값 (필요한크기) 에 따라 배열의 크기를 유동적으로 만들어 메모리 낭비를 줄임

이때 malloc / calloc / realloc 을 사용한다.

 

2. 배열: 연속된 메모리 위치의 집합 ( index, value 쌍의 집합)

3. ADT: 객체의 명세와 그 연산의 명세가, 그 객체의 표현과 연산의 구현으로부터 분리된 데이터 타입

4. 구조체/유니언 : 구조체와 유니언(공용체)은 선언자체는 유사하지만 분명히 다르다.

구조체와 유니언은 다른 데이터 타입을 하나의 그룹으로 묶지만 메모리 부분은 다릅니다.

구조체는 멤버들의 메모리 합으로 공간을 만들지만 유니언은 멤버들 중 가장 큰 값으로 메모리 공간을 만듭니다.

따라서 유니언의 경우, 동시에 멤버를 불러들일 경우 메모리가 부족합니다. 하지만 하나씩 불러올 경우 메모리 낭비를 막을 수 있습니다.

구조체의 경우 멤버를 한번에 불러들일 수 있지만, 하나의 멤버만 부를 경우 나머지는 메모리 낭비가 됩니다.

5. 스택: 후입선출(LIFO) 

구성: top, push, pop

top은 항상 마지막 push 된 원소를 가리킨다. 가리키고 있는 원소를 pop하면 아래 원소를 top하고 있게 된다.

 

초기 top= -1

push: 현재 top이 stacksize중 어디까지왔는지 체크하고 아직 여유가 있다면 ++top을 먼저 올린 후 원소를 삽입시킨다.

pop: top이 -1이라면 스택의 top 원소를 먼저 비운 후 top--을 실행한다.

 

 

6. 큐: 선입선출(rear, front)

rear: 새로운 원소가 삽입되는 끝

front: 원소가 삭제되는 끝

 

 

 

 

 

 

3차원 배열 주소 구하기

 

후위식 -> 스택에서의 표현

 

이진트리의 후위식/레벨 -> 순회식 쓰기

 

링크리스트를 배열로 바꾸었을때 문제점과 해결방법

 

원형 큐 first, last 로 표현하여 어떤구조인지 그리기

 

주어진 후위식을 TOKEN 으로 그리기 [표형식]