배열과 포인터

 

배열과 포인터는 아주 유사한 성격을 갖고 있습니다. 배열은 뭘까요?

 

우선 배열에 대해서 알아봅시다. 배열은 같은 자료형이 연속된 공간으로 나열되있는 것을 뜻합니다. 배열에 대해서 조금 더 쉽게 접근하기 위해서 index를 갖는데요. index를 통해 빠르게 배열 원소에 접근하게 됩니다.

 

int a[5]={5, 3, 1, 2, 4};

 

이와 같은 배열이 있다면 메모리의 구조는 바로 이렇게 구성될겁니다.

 

 

왜 이런식으로 배열이 구성이 될까요??

 

왜 배열의 원소는 4바이트나 되는 걸까요.

그 이유는 int가 4바이트이기 때문입니다. 따라서 4바이트씩 주소가 증가하고 있는 겁니다.

그렇다면 char형의 배열은 한 원소의 크기가 1바이트이고, long long배열의 한 원소 크기는 8바이트가 되는 겁니다. got it?

 

 

사실 a라는 변수는 a[0]의 주소값을 갖고 있습니다. 배열의 시작주소를 가지고 있다는 거지요.

 

따라서 a는 &a[0]와 같은 값을 나타냅니다. a는 a[0]의 주소를 가리키고 있다는 겁니다. 

a가 주소값을 가지고 있다고??

그렇다면 a가 가지고 있는 주소를 참조한다면 *a로 a가 참조하는 값을 구할 수 있겠네요. 그러면 정말 a[0]의 값을 참조할까요? 

코드로 확인해보세요.

 

 

이제부터는 다른 배열의 다른 연산법을 알아보겠습니다. a는 a[0]을 가리키고 있는 포인터라고 했습니다. a[0]은 5의 값을 가지고 있습니다. 

헌데, a가 a[0]를 가리키고 있으니, *a는 a[0]의 값을 나타내게 되는 것이지요.

 

그렇다면 이렇게 변형해볼까요?

*(a+0) 는 *a와 같은 뜻이 될까요? 아마 그렇겠죠?

그렇다면 *(a+1)은 어떤 값을 나타나게 될까요?? 결론부터 말씀드리면 a[1]의 값을 갖게 됩니다. 어떤 포인터의 +1은 그것이 참조하고 있는 자료형의 크기만큼 주소를 더하라는 의미가 됩니다. 

 

그렇다면 *(a+i)는 a[i]가 되겠네요!! 와우!!

 

이제껏 지껄인 말이 확실한지 코드로 확인해보도록 하겠습니다.

 

#include <stdio.h>

int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	
	
	
	printf("a의 주소 &a[0] = %p, a = %p \n", &a[0],a);
	printf("a의 값: %d\n", *a);
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  a[%d] : %d, *(a+%d) : %d\n",(a+i),i,a[i],i,*(a+i));

}

 

 

다음 사진은 결과를 보여줍니다.

 

 

 

제가 설명한 내용이 맞나요??

a의 값은 a[0]의 주소와 같네요!! 주소 값은 역시 4바이트씩 증가합니다. 

아까 포인터 연산 역시 제가 설명한 대로 나오고 있습니다.

포인터로 배열을 참조할 수 있습니다.

 

방금 전 배열 a를 포인터 ptr로 참조해보도록 하지요.

 

int *ptr = a;

 

로 간단하게 a라는 배열을 포인터로 참조할 수 있습니다.

a 역시 배열의 주소를 가지고 있고 ptr 역시 배열 a를 가리키고 있습니다. 그래서 a와 ptr은 같은 곳을 바라보게 되는 거죠.

 

 

그러면 ptr 역시 a가 가지는 특성을 그대로 가지고 있을까요?

코드로 확인해봅시다. 컴퓨터는 거짓말을 하지 않으니까

 

 

#include <stdio.h>

int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	int *ptr = a;
	
	
	
	printf("a의 주소 &a[0] = %p, a = %p \n", &a[0],a);
	printf("a의 값: %d\n", *a);
	
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  a[%d] : %d, *(a+%d) : %d\n",(a+i),i,a[i],i,*(a+i));

	printf("\n");

	printf("ptr이 가리키는 주소 : %p\n", ptr);
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  p[%d] : %d, *(p+%d) : %d\n"
			,(ptr+i),i,ptr[i],i,*(ptr+i));
	
	
}

그 결과입니다.
 

 

정확히 똑같은 성질을 갖고 있다는 것을 알 수 있습니다.

 

그러면 둘의 차이는 없을까요??

 

이 둘의 차이는 크기에서 차이가 납니다.

sizeof연산을 한 번 해보도록 하지요.

 

 

#include <stdio.h>
int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	int *ptr = a;

	printf("a의 사이즈 :%d, ptr의 사이즈 :%d\n", sizeof(a), sizeof(ptr));
}

 

결과

 

음.....

a의 사이즈는 20이고, ptr의 사이즈는 4바이트네요.

a는 배열의 크기를 갖고 있습니다.

a는 int형(4바이트) 배열로 5개가 할당되어있으니 20바이트이지요.

 

하지만 ptr은 단순히 그 배열을 참조해야하기 때문에 주소값만 저장할 수 있는 공간이면 충분합니다. 따라서 4바이트면 충분합니다.

 

그리고 배열은 상수화가 된다는 것이 특징입니다. 배열의 원소는 변경가능합니다. 하지만 배열 변수를 다른 값으로 변경할 수는 없습니다.

 

int a[5];

int b[5] = {5, 3, 1, 2, 4} ;

 

a=b;

 

a는 b와 크기가 같고 자료형이 같음에도 불구하고 이와 같은 코드는 컴파일 에러를 불러일으키게 되는 겁니다.

 

a는 a[0]의 주소입니다. b 역시 b[0]의 주소입니다.

주소는 read-only입니다. 즉, 값을 대입할 수가 없습니다 절대로!

 

 

위의 코드는 이것과 같은 얘기가 됩니다. 

&a[0] = &b[0] 이라는 거죠.

이제까지 이야기한 내용을 이해하셨다고 한다면 이해가 갈겁니다.

 

주소는 포인터만이 참조할 수 있는 포인터만의 특성입니다.

 

그러니까 위의 코드는 이렇게 바뀌어야합니다.

 

int *a;

int b[5] = {5, 3, 1, 2, 4} ;

 

a=b; //a=&b[0]과 같음.

 

배열과 포인터의 관계 이해하셨는지요??

이것으로 배열과 포인터의 관계를 마치겠습니다~~~

반응형
블로그 이미지

REAKWON

와나진짜

,

BFS(Breadth First Search, 너비우선탐색)


그래프 이론 DFS와 BFS 중 BFS는 그래프를 가까운 정점부터 순서대로 탐색하는 그래프 탐색 알고리즘이랍니다. 그래프에서 탐색 시 아주 많이 사용되는 탐색기법이지요. 우선 다음과 같은 무향그래프가 있다고 가정해보겠습니다. 


우선 그래프 탐색을 하기 전에 조건이 있습니다.

1. 처음 정점 0부터 시작한다고 칩시다.

2. 정점을 방문한 적이 있다면 다시 방문하지 않는다.

3. 방문해야 할 정점이 여러 개일 경우 가장 번호가 낮은 정점부터 방문한다.




BFS로 위 그래프를 탐색하는 과정을 보겠습니다 


1. 0을 방문한다.

2. 0과 가장 가까운 정점을 찾는다 ( 1, 5, 6).

3. 1이 방문되지 않았으므로 1을 방문한다.

4. 5가 방문되지 않았으므로 5를 방문한다.

5. 6이 방문되지 않았으므로 6을 방문한다.

6. 1에서 가장 가까운 정점을 찾는다 (0, 2, 3).

7. 0은 이미 방문했으므로 skip한다.

8. 2는 방문되지 않았으므로 2를 방문한다.

9. 3이 방문되지 않았으므로 3을 방문한다.

10. 5에서 가장 가까운 정점을 찾는다 (0, 6).

11. 0과 6은 방문됐으므로 skip한다.

12. 6과 가장 가까운 정점을 찾는다 (0, 5).

13. 0과 5는 이미 방문됐으므로 skip한다.

14. 2와 가장 가까운 정점을 찾는다 (1, 4). 

15. 1은 이미 방문됐으므로 skip한다.

16. 4는 방문되지 않았으므로 4를 방문한다.

17. 모든 정점을 지나쳤으므로 종료한다.


이제 방문된 점을 차례대로 나열해본다면  0 - 1 - 5 - 6 - 2 - 3 - 4 로 방문이 되는 것을 확인 할 수 있습니다. 코드로 표현하면 어떻게 될까요? 아래 C++ 소스코드로 BFS를 구현해보았습니다.


#include <cstdio> #include <vector> #include <queue> #define V 7 using namespace std; int g[V][V] = { {0,1,0,0,0,1,1}, {1,0,1,1,0,0,0}, {0,1,0,0,1,0,0}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {1,0,0,0,0,0,1}, {1,0,0,0,0,1,0} }; vector

bfs(int start) { vector discovered(V, false); queue next; vector order; visited[start] = true; next.push(start); while (!next.empty()) { int from = next.front(); next.pop(); order.push_back(from); for (int to = 0; to < V; to++) { if (g[from][to] == 1 && !visited[to]) { next.push(to); visited[to] = true; } } } return order; } int main() { vector bfsOrder = bfs(0); for (int i = 0; i < V; i++) printf("%d ", bfsOrder[i]); }


이 코드가 어떻게 동작이 되는 지 하나하나 살펴봅시다. 그 전에 준비물이 있습니다. 바로 자료구조 큐를 준비해야 된다는 겁니다. 큐를 통해서 어떻게 BFS가 구현될까요? 다음과 같이 하늘색 상자는 큐를 나타낸다고 하겠습니다. 0부터 노드가 방문되기 때문에 큐 안에는 0이 저장되어 있습니다.



이 후 0은 방문될때 큐에서 꺼내어 집니다. 그 다음에 0에서 가장 가까운 정점 중에 방문되지 않은 정점을 큐에 저장합니다. 이렇게 말입니다.


0을 방문합니다. 0은 큐에서 꺼내어 지고 0과 가장 가까운 정점 1 5 6이 큐에 저장됐습니다. 그 후에는 다시 1을 큐에서 꺼내오고 1과 가장 가까운 정점을 큐에 집어 넣습니다.

단, 방문되지 않은 녀석들로요.



1은 방문이 되어 큐에서 나오고 2와 3이 추가 돼었군요. 역시 과정은 계속 반복됩니다. 다음 5가 방문될 차례입니다. 5를 꺼내고 5와 가장 가까운 정점을 추가합니다.



5와 가장 가까운 정점 0과 6이 있는데, 6은 아직 큐에 존재하니까 방문하지 않은 걸로 간주합니다. 그래서 6을 다시 큐에 집어 넣습니다. 다음 6을 방문합니다. 



6과 가장 가까운 정점 0과 5는 이미 방문된 상태랍니다. 그래서 큐에 집어 넣지 않습니다. 다음 2를 방문합니다. 





2과 가장 가까운 정점은 1, 4로 1은 이미 방문된 상태로 넘어가고 4는 큐에 들어갑니다. 왜냐면 방문될 정점으로 큐에 아직 존재하니까요. 다음 3을 방문합니다.


3과 가장 가까운 정점 1은 이미 방문된 상태라 넘어갑니다. 다음 4를 방문합니다.

4와 가장 가까운 정점 2는 이미 큐에서 나와 방문이 되었습니다. 어느 정점하나 큐에 들어가지 않습니다. 이제 큐에 남아있는 방문될 정점 6과 4는 이미 방문이 되었으므로 큐에서 그냥 빠져나옵니다. 방문되지 않는 다는 뜻입니다. 버립니다.


이로써 큐는 모두 비워졌습니다. 큐가 비워졌으니 더 이상 방문할 정점이 없으니 BFS과정은 끝나게 됩니다. 이로써 BFS가 어떻게 동작하는 지 살펴보았습니다. BFS는 그럼 도대체 언제 사용하게 될까요? 그건 다음에 알아보도록 하겠습니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

C언어 포인터란?  포인터라쓰고 탈모라 읽는다

C언어에서 포인터는 프로그래밍을 하면서 아주 어렵게 배우는 주제이기도 합니다. 어렵다기보다는 헷갈리는 경우가 많아서 멘탈붕괴가 오고는 하죠. 포인터는 말 그대로 무엇을 가리키는 놈입니다. 무엇을 가리킬까요??

다른 변수의 주소를 가리킵니다! 

모든 변수는 그 데이터가 저장되는 공간의 주소를 갖고 있습니다.

그것을 어떻게 표현할까요??

int B = 4;

int *A = &B;

이렇게 표현하게 됩니다. A는 B의 주소를 값으로 갖고 있다는 의미랍니다. 만약 B의 주소가 0x20이고 B의 값은 4라고 할때 A의 값은 0x20이 됩니다.

만약 B가 가지고 있는 값을 가져오고 싶다고 할때는 *A로 값을 참조할 수 있습니다.

그림으로 나타내면 이런 식으로 나타낼 수 가 있겠지요.

 

정말 제 말대로 되는 지 코드로 살펴보도록 하지요.

#include <stdio.h> 
int main() { 
        int B = 4;   
        int *A = &B;    
        printf("B의 값:%d\n", B);
        printf("B의 주소 :%p\n", &B);   
        printf("A의 값:%p\n", A);       
        printf("A가 참조하는 값 :%d\n", *A);     
}

 

네, 그렇게 나오네요
 
그렇다면 이중포인터는 무엇을 말할까요??
똑똑하신 여러분은 이미 알고 계시겠지만 포인터를 2번 쓰는 것을 말합니다.
아래 그림과 같은 상황이 바로 이중 포인터라는 것이죠, 포인터의 포인터! 스트레스의 향연

A는 B를 가리키고 있고, B는 C를 가리키고 있습니다.

int C = 10;

int *B = &C;

int **A = &B;

이렇게 쓸 수 있다는 거지요. A에 **(포인터의 포인터, 이중포인터)가 붙어있는 것을 확인 할 수 있네요

A는 B의 주소값을 값으로 가지고 있고, B는 C의 주소값을 값으로 갖고 있습니다. 그렇다면 A가 B의 값을 참조하려고 한다면 *A가 되겠죠?? 그러면 무슨 값이 나올까요??

바로 B가 가지고 있는 값, C의 주소입니다. A가 C의 값을 참조하기 위해서는 한 번 더 가리켜야하는데요.

그때 더블포인터가 사용이 되는 것입니다.  **A는 10을 확인할 수 있을 겁니다.

코드로 확인해 보도록 하죠.

#include <stdio.h>

int main() { 
        int C = 10; 
        int *B = &C;
        int **A = &B;

        printf("C의 값 : %d\n", C); 
        printf("C의 주소 : %p\n", &C); 
        printf("B의 값 : %p\n", B); 
        printf("B의 주소 : %p\n", &B); 
        printf("B가 참조하는 값 : %d\n", *B);
        printf("A의 값 : %p\n", A); 
        printf("A가 참조하는 값 : %p\n", *A); 
        printf("A가 참조하는 값이 참조하는 값 : %d\n", **A);
}

결과는 아래와 같습니다.

 

 

앞서 말한 대로 C의 주소를 B가 값으로 가지고 있고, B의 주소를 A가 값으로 가지고 있는 걸 확인할 수 있겠죠?? *A는 C의 주소값을 갖고 있습니다. 왜냐면 *A는 B의 값을 가리키고 있는 데 B의 값은 C의 주소이니까요!

그렇다면 삼중포인터는 어떻게 될까요??

뭐하러 어려운 포인터를 쓰나?

포인터는 언제 써먹을 수 있을까요? 대표적으로 다음과 같은 상황일때 사용합니다. 

어떤 함수가 있다고 칠게요. 아주 단순합니다. 그저 매개변수인 a와 b의 값을 교환하는 swap이라는 함수입니다.

void swap(int a, int b) {
        int temp; 
        temp = a; 
        a = b;
        b = temp;
}  

int main() {
        int x = 10;
        int y = 20; 
        swap(x, y); 
        printf("x: %d, y: %d\n", x, y); 
}

 

call-by-value

우리는 x와 y의 값을 바꾸고 싶다 이겁니다. 그 과정을 살펴보지요.

1. 우선 temp에 a의 값을 넣습니다. 그렇다면 10이 temp의 값에 들어있겠네요.

2. 그리고 b의 값을 a에 집어 넣습니다. 그렇다면 a의 값은 b의 값인 20이 들어가겠군요.

3. 마지막으로 변수 b에 temp값을 넣습니다. temp는 10이었으니까 b는 10이 되어지겠군요.

이제 함수에서 빠져나옵니다. 그 값이 바뀌어있을까요? 아닙니다. 이 함수는 a와 b를 함수 내부에서만 교체할 뿐이지, 함수 호출이 끝나고 반환되서도 x와 y의 값은 변함이 없습니다. 왜 그럴까요?

함수인자 a와 b는 전달받은 매개변수의 값(x, y)만 복사해오기 때문입니다.

예를 들면 졸업증명서 원본이 있고, 그걸 복사해서 사본을 갖고 있습니다. 사본을 불에 태워도 원본이 같이 탈까요? 동시에 같이 태우지 않는 한 원본은 살아있습니다. 이렇기 때문에 main에서 swap을 호출하고 나서도 x와 y의 값은 변함이 없습니다.

이런 함수 호출 방법을 Call-By-Value라고 부르는 것입니다.

 

call-by-reference

그렇다면 우리는 어떻게 함수를 변경해야 할까요?

그럴때 포인터가 사용이 됩니다.

void swap(int *a, int *b) { 
        int temp; 
        temp = *a; 
        *a = *b; 
        *b = temp;
}

int main() { 
        int x = 10; 
        int y = 20; 

        swap(&x, &y);
        printf("x: %d, y: %d\n", x,y);
}

a는 x의 주소를 가리키고 있고, b는 y의 주소를 가리키고 있습니다. a는 x의 주소를 참조하고 있기 때문에 x에 영향이 주게 되는 겁니다. b 역시 마찬가지가 되겠구요.

그림을 통해서 설명해보도록 하지요.

1.  temp = *a

temp에 a가 가리키는 값을 대입합니다. a가 가리키는 값은 10입니다.

 

2.  *a = *b

a가 가리키는 값에 b가 가리키는 값을 넣습니다. 그림과 같이 x의 값이 변경됩니다.

3. *b = temp

b가 가리키는 값에 temp의 값을 저장합니다. temp는 방금전 10이었기 때문에 b가 가리키는 곳(y)의 값은 10으로 변경됩니다.

 

결과는 어떨까요?

결과 역시 우리가 예상했던 대로군요. 우리는 이와 같이 함수에서의 조작이 외부 변수에 조작이 가해질때, 그럴때를 Call-By-Reference라고 합니다.

반응형
블로그 이미지

REAKWON

와나진짜

,