Search
moon
sun
📝

3월26일(화)

지난 시간 복기

반복적 방법은 구현이 쉽고, 대다수는 걸리는 시간도 순환적 방법보다 빠르다. 그리고 순환적 방법은 함수를 계속 호출을 함으로써 메모리도 많이 잡아먹고(메모리의 스택공간), 결국 스택공간이 가득차서 더이상 연산할 수 없는 상황이 발생하기도 한다(오버플로우) 그렇지만, 어려운 알고리즘을 구현하는 상황이나, 거듭제곱을 구하는 경우(정말 예외적 경우에 가까움)에는 순환적 방법이 오히려 걸리는 시간도 짧고, 구현하기가 더 편하다.

피보나치 수열 계산

순환 호출의 경우의 비효율성
•
같은 항이 중복해서 계산됨
•
fib(6)을 호출하는 경우에, fib(3)이 4번이나 중복되어 계산됨
◦
스택에도 중복적으로 쌓이고 해서 좋지 않다!
이제 본격적으로 자료구조 내용 시작!

리스트(Lists)

List

•
선형 리스트
◦
배열
•
연결 리스트

Stack

•
선형 리스트
◦
배열
•
연결 리스트
•
동적 배열

Queue

•
선형 리스트
◦
배열
•
연결 리스트
•
동적 배열

학습 목표

•
리스트의 개념
•
리스트를 배열 이용해서 구현
•
리스트를 연결 리스트를 이용해서 구현

내용

•
List ADT
•
Sequential List(배열로 구현된 리스트)
•
Linked List(연결리스트)
•
Singly Linked List(단순 연결 리스트)

List vs Set

List

순서O, 중복O ← Index

Set

집합
순서X, 중복X

Array List VS Linked List

무조건 좋거나, 무조건 나쁜 리스트는 없다 모두 장단점이 존재한다

Array List

•
순서가 있고, 연속성이 있다
◦
insert한다면, 무조건 인덱스값이 작은 순서대로 넣어줘야한다.
◦
연속성을 유지해야하므로, 중간에 비어있으면 안되고 만약 중간값이 배열에서 삭제된다면, 데이터를 앞으로 당겨줘야한다. 즉, 데이터의 삽입과 삭제가 비효율적이다
▪
그러나, 빠르기는 ArrayList가 빠르다. 연결리스트는 overhand가 필요해서 찾는데 시간이 좀 걸리기 때문이다.

Linked List

•
물리적으로는, 순서가 존재하지 않아도 된다
그러나
•
논리적으로는, 순서가 존재해야한다.
◦
연결되어있는 다음 데이터값의 주소를 알아야한다(Overhand 필요)
데이터의 삽입과 삭제가 편리하고 효율적이다 데이터가 추가로 들어오거나 나가는 경우에, 그냥 연결만 해주면 됨

ArrayListType 구현

#define MAX_LIST_SIZE 100 typedef int element; typedef struct { element array[MAX_LIST_SIZE]; int size; } ArrayListType;
C
복사