Brady kim（阿金）

Brady kim（阿金）

몰라요. 그래서 배우고 있어요.

[자료구조&알고리즘] 2-1 배열과 리스트

3 분 소요

## 이 문서는 성균관대학교 성재필 교수님의 강의인 인공지능을 위한 알고리즘과 자료구조를 정리한 내용입니다.

강의 목표

1.Discuss key data structures and algorithems essential for solving problems with computers

2.Programming skills -Translate your idea into languages that computers can understand

3.Computational thinking -Problem formulation(abstraction) -solution expression(automation) -solution execution and evaluation(analysis)

Array의 생성, 접근

A data structure consisting of a collection of values

Array는 자료의 값들을 모아놓은 자료구조이다. 우리가 자료를 모아서 array로 생성해놓았다면, 각각의 자료들은 Array index로 식별할 수 있다. C++/C나 JAVA같은 프로그램 언어는 Array index는 보통 0부터 시작한다.

Array를 선언하려면 먼저 데이터 타입을 명시해야 하는데,

int score[10];

위와 같이 코딩을 한다면 10개의 integer를 담을 수 있는 배열이 생기게 되며, 각각의 점수(Score)를 0~9까지 선택을 할 수 있게 되는 것이다. 그래서 실제로 C나 C++ 프로그래밍 랭귀지에서 어레이를 선언하면 실제로 램이라고 불리는 메모리의 연속적인 공간을 할당받게 되고, 실제로 메모리 상에서도 같은 순서로 매핑이 되어 있다.

Creation of an array 어레이를 생성하는 방법은 크게 두가지가 있다.

  1. 타입을 선언하고, 어레이의 이름, 크기를 설정하는 방법
  2. 동적인 생성 방법으로, Type, 그리고 d를 포인터로 선언하고 new 오퍼레이터를 통해 어레이 사이즈라는 숫자에 맞춰서 할당을 할 수 있음
Type d[10];
Type *d=new Type[ size ];

Accessing an element by array index 어레이는 인덱싱을 통해 데이터 value에 접근할 수 있다.

d[5] =2;

Release the allocated 에레이에 할당된 것을 제거 할 수 있다.

delete[] d;

Creation of Arrays in c++ programming Language 1차원 및 2차원 어레이를 다음과 같이 생성할 수 있다. 1-dimensional array

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

2-dimensional arry

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

실제로 어레이를 생성하면 아래의 그림과 같이 int는 메모리상에서 4바이트를 요구한다.

int score[3] = {52,17,61};

image

  • 어레이를 선언하게 되면 물리적인 램에서도 위와 같이 연속적인 공간을 할당받게 된다.

pointer

image

포인터는 Variable이며, 일반적인 값을 저장하는 것이 아니라 메모리의 주소를 저장하는 변수이다. 어떤 variable을 크게 3축으로 이름, 값, 주소 이렇게 나타낸다고 했을 때, 만약 int n =3; 이라는 변수를 선언하고 값을 3으로 초기화를 했다면 n이라는 variable이 생기게 되고, 실제로 저장되어 있는 값은 3이다.

여기서 int* pn= &n; 포인터 pn이라는 것을 만들어, 포인터가 가지는 값을 확인해보면 위에서 만든 n의 주소 00FDF18이라는 값을 가지게 된다. 이렇게 pn이라는 포인터를 통해 n이라는 변수에 접근할 수 있다.

&(Ampersand)Operato

Reference operator

  • Returns the address of a variable
#include<cstdio>

int main()
{
 char c = 'A';
 char* pc = &c;
 
 printf("%c %p\n", c,pc);
 printf("%p %p\n", &c,&pc);
 printf("%d %d\n", sizeof(c),sizeof(pc));
 
 return 0;
 }

 A 00FDFC1C
 00FDFC1C 00FDFC18
 1 4

*(Asterisk)Operator

  • Dereference operator

포인터에 *를 붙이게 되면, 이 포인터가 가르키고 있는 값 자체를 직접 접근할 수 있으며 포인터로 직접 변수의 값을 수정할 수 있다.

#include<cstdio>

int main()
{
 char c = 'A';
 char* pc = &c;
 
 printf("%c %p\n", c,*pc);
 
 *pc = 'C';
 printf("%c %d\n", c, *pc);
 
 return 0;
 }


A A
C C

Function Call with Pointers

함수를 호출할 때 argument를 넣어줄 수 있는데, 방법이 2가지가 있다.

  1. Call by value:passing values -> 함수를 호출하는 곳에 있는 변수의 값을 변경할 수 없다.
  2. Call by reference:passing addresses ->주소값을 가지고 가는 것이기 때문에, 함수를 호출한 곳의 값을 변경할 수 있다는 특징이 있다.

linked list

5라는 값을 3과 10사이에 추가하고 싶다면, 10,7,6을 다 뒤로 1칸씩 밀고, 생긴 빈자리에 5를 넣어주는 방법처럼 굉장히 비효율적이다. 이러한 문제점을 해결하는 자료구조가 linked list이다.

자료들의 선형적인 collection이라는 것은 어레이와 같은데, 대신에 각각의 element가 어레이 같은 경우엔 어레이 인덱스로 3번째 데이터, 4번째 데이터 처럼 바로 접근 할 수 있었다면, 이 linked list에는 모든 element들이 자신의 값과 나의 다음 값을 pointing하는 자료구조이다. 그래서 모든 노드가 데이터와 다음 값에 대한 링크, hook이라고 부르는 식의 자료구조로 되어 있다.

이것의 장점은 사이에 5를 넣고 싶다면 20의 다음 친구인 45의 hook을 빼주고 5를 넣어 45를 이어주게 되면 자연스럽게 insertion이 이루어지게 된다, deletion도 마찬가지이다.

linked list의 구조는 데이터의 값 자체와 다음 next 노드의 포인터를 가지게 되고, 전체의 linked list는 head, 즉 어디가 시작점인지를 지칭하는 포인터와 현재 몇 개의 element를 가지고 있는지에 대한 데이터를 가지고 있다.

linked list는 주로 박스와 화살표를 통해 표현하며, 아무것도 지칭하지 않는 NULL 포인터가 있으면 이것이 linked list의 끝 데이터이다.

참고