[공부] 인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고 1,2주차

본 포스팅은 강의를 바탕으로 공부하기 위해 작성되었습니다.

http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2022_T2/course/ 

강좌 | SKKU_46 | K-MOOC

 

array

• 자료의 값들을 모아놓은 자료구조
• 각각의 자료들은 array index로 확인 할 수 있다.
• 보통의 programming language는 array index가 0에서부터 시작
• 이런 array를 선언하려면 데이터타입 및 사이즈 명시 필요(JAVA C# C)
• 램이라는 메모리에서 연속적인 공간을 할당 받음.
• array index상의 순서대로 메모리에도 같은 순서로 매핑 되어있다.
• 동적으로 array에 크기 할당하기 위해서는 포인터 및 오퍼레이터 이용 (Type *d = new Type[size];)
• 메모리에 돌려주기 위해서는 delete oprator 이용 (delete [] d;)

 

1차원 어레이(예시)

int arr [10];
int *arr = new int[10];

 

2차원 어레이(예시)

int a[3][4];
int **a = new int * [3]; 
for (int i = 0; i<3; i++)
	a[i] = new int [4];

 

포인터(Pointer)

메모리의 주소를 담고있는 변수이다.

 

& (reference operator)

변수의 주소를 받아올 수 있는 오퍼레이터이다.

 

* (deference operator)

포인터에 *를 붙이면 포인터가 가르키고 있는 값 자체에 직접 접근 가능(주소 아님)

 

call by value

값만 불러오는 것, 변수에 영향 줄 수 없음

 

call by reference

주소값을 가져가는 것이기 때문에 변수에 영향을 줄 수 있음

 

linked list

• 값을 추가하거나 삭제할 때, 데이터를 옮겨줘야 해서 비효율적임.
• 이런 문제점을 해결하는 자료구조가 linked list이다.
• linked list는 모든 element들이 자신의 값과 다음 값을 pointing 하는 자료구조이다.
• 각각의 노드는 데이터의 값과 다음 노드의 포인터를 가지게 된다.

 

typedef int Data;

typedef struct _Node
{
    Data item;
    struct _Node* next;
} Node;

typedef struct
{
    Node* head;
    int len;
} LinkedList;

head라는 포인터가 첫 번째 데이터를 포인팅하고 있고 각 노드들은 자신의 다음 노드를 포인팅하고 있다.

 

스택 

• 선형자료구조의 하나로써 LIFO라는 부르는 특성을 가지고 있는 자료구조이다.
• LIFO란 last-in first-out의 약자이다. 마지막으로 들어간 element가 처음으로 나온다는 것.
• 스택에서는 삽입하거나 제거하는 행위가 최상단(Top)에서만 이루어진다는 것
• 스택은 괄호의 집합 등이 밸런스하게 이루어져있는지 안 이루어졌는지 등을 체크하기 위해 스택을 사용한다.

 

스택을 이용한 괄호 매칭

• 괄호들이 포함된 문자열을 입력을 받는다.
• 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 최상단에서 하나를 꺼낸다.
• 문자열을 다 확인 했으며, 스택이 비어있으면 괄호의 밸런스가 맞다.

 

큐

• 스택과 다르게 FIFO(first-in first-out) 구조이다. 먼저 들어간 데이터가 제일 먼저 나오는 자료구조이다.
• 인터넷 웹서버 등이 먼저 들어온 사람을 먼저 처리해주는 큐 구조로 구현 되어있다.
• 삽입할 때에는 맨 뒤에, 삭제할 때는 맨 앞에서 이뤄진다.

 

큐 용어

• Front(head) : deletion이 이루어지는 위치
• Rear(back, tail) :  insertion이 일어나는 위치
• Enqueue : 큐에 아이템을 Rear에 insertion 하는 것
• Dequeue : 큐에 아이템을 Front에서 deletion 하는 것

 

큐 문제점

• 비어있는 공간이 있더라도 더 이상 추가가 불가능
• 이런 문제점을 해결하기 위해 circular queue를 많이 사용한다.

 

STL(Standard Template Library)

• C++에서 사용되는 소프트웨어 패키지. 
• pair, vector, list, stack, queue 등 굉장히 많은 종류의 데이터 컨테이너들을 제공한다.