이 문제가 쏘아올린 작은 공이 나에게서 7시간을 앗아갔다. 믿겠는가..?
일단 이 글에 대한 내용은 아래 글과도 연관이 있다.
백준 11650번
11650번부터해서 이 문제도, qsort 사용으로 풀었다. 이 함수는 포인터에 대한 개념을 요하기 때문에 사용하기가 개인적으로 까다롭다.(1차원을 넘어가면). 그래서 사용하지 않으려고 하는데, 자꾸 피하기만하는 것 같아서 개념도 제대로 익혀볼 겸 자꾸 사용하려 하고 있었다.
좋은 마음으로 공부하려다가 아주 개념이 뒤집어 엎어졌다가 세워졌다가 하루종일 혼동 속에 정신없는 시간을 보냈다.
이 함수를 쓰면 쓸수록 포인터에 대한 개념이 헷갈려서 11650번으로 돌아갔다가 11650번이 다시 헷갈려지고..
결론부터 말하자면, 2차원 배열을 void *로 덮어쓰면서 생기는 분열?.. 그리고 이중포인터와 2차원 배열의 숨은 차이 정도..
(메모리 구성에는 차이가 있어도 사용하는 면에 있어서는 둘 각각의 약속이 존재하기에 차이가 없으나, void *로 덮어쓰면서 헷갈려지는느낌)
우선 정답 코드부터 공개하고 고된 과정을 적어보려고 한다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(char *a, char *b) {
int x = strlen(a);
int y = strlen(b);
if(x < y)
return -1;
else if(x > y)
return 1;
else {
return strcmp(a, b);
}
}
int main() {
char a[20000][51]; //입력되는 문자 길이가 50 이하라고 주어졌으나, 마지막에 널문자가 들어가야 할 자리가 마련되어야 하므로 51로 해야함 주의!
int nx;
scanf("%d", &nx);
for(int i = 0; i < nx; i++) {
scanf("%s", a[i]);
}
qsort(a, nx, sizeof(a[0]), (int(*)(const void *, const void *))cmp);
for(int i = 0; i < nx; i++) {
if(i > 0 && !strcmp(a[i], a[i-1]))
continue;
printf("%s\n", a[i]);
}
}
- 참고로 비교함수 인자를 더블포인터로 하던, 싱글로 해서 더블로 캐스팅하던 용도에 맞다면 상관없다.
- 그리고 qsort로 넘겨줄때 배열을 싱글포인터로 캐스팅 하나 안하나 똑같다. 어차피 void *로 캐스팅.
- 2차원 배열 종류를 넘겨줄 때에는 배열 요소 간격 사이즈를 sizeof(요소)*요소갯수 보다는 a[0] 이런식으로, 1차원 배열의 크기만큼으로 해주는게 깔끔하고 좋다.
[ 장장 7시간의 긴 여정 ]
나는 이 문제를 배열이 아닌 동적할당으로 이중포인터 구현을 하던 도중 헤매기 시작했다.
열 데이터가 50개인 char이여서 sizeof(char) * 50 했다가 한참을 틀렸다.. 출력해보니 데이터가 8이더라..
char **a;
int nx;
scanf("%d", &nx);
a = (char **)calloc(nx, sizeof(char *));
for(int i = 0; i < nx; i++) {
a[i] = (char *)calloc(50, sizeof(char));
}
a[i] = (char *)calloc(50, sizeof(char)); 가 결국 a[i]에는 char 포인터가 들어갈 공간이므로..50은 무의미한 것이였던게 아닐지..
라는 생각에 실험을 시작했다. 물론 실험결과부터 말하자면 이 말이 맞았다. a[i]는 문법 그대로 포인터 변수이며, 할당받은 char * 형 데이터의 주솟값이 들어가게 된다.
실험
//2차원 배열과 2중 포인터 메모리 구조가 다르다는 증거
실험
1.
char a[20000][50];
printf("%ld", sizeof(a[0]));
Output : 50 (a[0]의 주소의 메모리 크기 50)
2.
char **a;
a = (char **)calloc(nx, sizeof(char *));
for(int i = 0; i < nx; i++) {
a[i] = (char *)calloc(50, sizeof(char));
}
printf("%ld", sizeof(a[0]));
Output : 8 (char *형 변수 a[0]이 담고 있는 공간의 크기 8) // sizeof(char *) = 8
내 예상이 맞았다.. 이상한 할당을 하고 있었다. 포인터변수에 50데이터를 할당한 주소를 대입?해봤자 포인터변수의 크기는 50이 아니지. 근데 50을 간격으로 넘겨줬으니 이상하게 작동한것.
*/
sizeof()를 해보면 알다시피, 2차원 배열 그 자체와 2중포인터로 구현한 2차원배열은 조금 다르다. 하지만 메모리 구조가 조금 다를 뿐 사용하는 방식은 동일하다( 둘다 변수명에 이중으로 포인터나, []를 사용해서 참조, ) sizeof()의 결과를 통해 알 수 있듯이 2차원 배열일 때 a[0] 소유로 칭해지는 메모리 크기는 '열'의 요소의 크기 전체이고, 2중 포인터 일 때에는 a[0]은 어차피 포인터 변수이므로 요소의 크기의 상관없이 일정하다는 것이다.
변수의 크기 vs 메모리의 크기 느낌이다.
메모리 구조는 다른데, 데이터를 참조하여 사용하는 방법에 대해선 약속이 있어서 둘 다 동일하다고 보면 된다.
(둘 다 변수명에 이중으로 * 나 []를 사용해야 한다)
그리고 이중 포인터와 이차원 배열이 사용 방식은 같다는 것에 대한 정리도 했다.
// 2차원 배열과 이중 포인터가 위 실험에서 보듯이 메모리 구조는 다르되, 사용은 같다는 증명
// 2차원 배열
#include <stdio.h>
#include <stdlib.h>
int main (){
int a[2][2];
int nx;
long t1, t2, t3, t4;
scanf("%d", &nx);
for(int i = 0; i < nx; i++) {
scanf("%d %d", &a[i][0], &a[i][1]);
}
putchar('\n');
t1 = *(a[0]);
t2 = *(a[0]+1);
t3 = **(a+1);
t4 = *(*(a+1)+1);
printf("%ld %1d %ld %ld \n", t1, t2, t3, t4);
}
Input :
2
1 2
3 4
Output :
1 2 3 4
//2중 포인터
#include <stdio.h>
#include <stdlib.h>
int main (){
int **a;
int nx;
long t1, t2, t3, t4;
scanf("%d", &nx);
a = (int **)calloc(nx, sizeof(int *));
for(int i = 0; i < nx; i++) {
a[i] = (int *)calloc(2, sizeof(int));
}
for(int i = 0; i < nx; i++) {
scanf("%d %d", &a[i][0], &a[i][1]);
}
putchar('\n');
t1 = *(a[0]);
t2 = *(a[0]+1);
t3 = **(a+1);
t4 = *(*(a+1)+1);
printf("%ld %1d %ld %ld \n", t1, t2, t3, t4);
}
Input :
2
1 2
3 4
Output :
1 2 3 4
추가로 둘 다 **a의 결과도 같다.
이렇듯 둘은 내부 메모리 구조가 조금 다를 뿐, 둘다 동일한 방식으로 참조하여 사용한다.
하지만 아래와 같은 qsort같은 함수를 사용할 때, 두 방식에 대한 구현이 조금 다르다는 것에 주의해야 한다.
첫 번째는 qsort가 void *를 사용하기 때문에 2차원 배열은 그냥 1차원 배열처럼 다뤄지는 데 비해(2차원 배열일 때의 약속들도 깨져서 다소 헷갈릴 수 있다) 이중 포인터는 메모리 구조가 그렇지 못해서 두번 참조해야 되는 점에서 차이 나는 요인도 있고, 위에서 말한 sizeof() 문제에 대해서도 있다.
// 두 방식이 동일하다고 했던 '참조에 관한 사용' 관련해서도 qsort에서 사용이 다른 이유는 이중 포인터가 싱글 포인터로 캐스팅되기때문.
// 이중 포인터와 이중 배열의 메모리 구조는 다르기 때문에 차이가 나는 것.
2중 포인터 에서의 qsort 사용 예시(코드 일부)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(char *a, char *b) {
int x = strlen(*(char **)a);
int y = strlen(*(char **)b);
//x = 입력한 첫 문장 길이
//y = 입력한 두번째 문장 길이
}
int main() {
char **a;
int nx;
scanf("%d", &nx);
a = (char **)calloc(nx, sizeof(char *));
for(int i = 0; i < nx; i++) {
a[i] = (char *)calloc(50, sizeof(char));
}
for(int i = 0; i < nx; i++) {
scanf("%s", a[i]);
}
putchar('\n');
qsort(a, nx, sizeof(a[0]), (int(*)(const void *, const void *))cmp);
for(int i = 0; i < nx; i++) {
printf("%s \n", a[i]);
}
}
2차원 배열에서의 qsort 사용 예시 (코드 일부)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(char *a, char *b) {
int x = strlen(a);
int y = strlen(b);
//x = 입력한 첫 문장 길이
//y = 입력한 두번째 문장 길이
}
int main() {
char a[20000][51];
int nx;
scanf("%d", &nx);
for(int i = 0; i < nx; i++) {
scanf("%s", a[i]);
}
putchar('\n');
qsort(a, nx, sizeof(a[0]), (int(*)(const void *, const void *))cmp);
for(int i = 0; i < nx; i++) {
printf("%s \n", a[i]);
}
}
주의할 점은
qsort의 인자로 요소 간 사이즈 값을 전달할 때 sizeof(char)*51 같은 방식이 2차원 배열의 경우에선 먹히나, 이중 포인터 경우에선 먹히지 않는다는 것. 반대로 sizeof(char *) 방식이 2차원 배열의 경우에선 안먹히나, 이중 포인터 경우에선 먹히는것. 이런 차이 때문에 깔끔하게 sizeof(a[0])로 해주는 것이 더 편하긴 하다. 그리고 말했듯, 2중 포인터와 2차원 배열의 메모리 구조가 조금 다르기 때문에, 2차원 배열은 그냥 void *로 캐스팅되면서 1차원 배열처럼 진행되겠으나 2중 포인터는 그런 메모리 구조가 아니기 때문에 저렇게 이중으로 넘어가야만 한다.
2차원 배열과 2중 포인터가 다른 메모리 구조라는 것 출력.
둘다 이중참조를 해야하긴 하지만 이는 약속일 뿐 사실상 메모리 구조는 다르다(위에서 설명했듯 2차원배열 a == a[0] 이지만, *a != *a[0] 이라는 것 등 ) 그리고 이러한 증거는 아래 결과를 통해 알 수 있다.
대표적인 차이점으로,
2차원 배열 a와, 2중 포인터 변수 b가 있을 때, a == a[0] 이지만, b != b[0] 이다.
하지만 a[0][0] , b[0][0]의 요소를 얻기 위해선 둘다 **a **b를 해줘야 한다는 약속. (또는 *a[0], 즉 이중 작업을 거쳐야 한다)
int ** 형 변수 b에는 int *형 변수들의 뭉텅이의 주소를 받고, int *형 변수들은 int형 열의 요소들의 뭉텅이의 주소를 참조한다.
int[][]형 변수 a는 a[0]과 같은 값을 갖고 a[0]은 int형 열의 요소들의 뭉텅이의 주소를 갖는다.
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[2][2];
int **b;
a[0][0] = 1;
a[0][1] = 2;
a[1][0] = 3;
a[1][1] = 4;
b = (int **)calloc(2, sizeof(int *));
for(int i = 0; i < 2; i++) {
b[i] = (int *)calloc(2, sizeof(int));
}
printf("a = %p\n", a);
printf("a[0] = %p\n", a[0]);
putchar('\n');
printf("b = %p\n", b);
printf("b[0] = %p\n", b[0]);
}
Output:
a = 0x7ffeefbff520
a[0] = 0x7ffeefbff520
b = 0x100664120
b[0] = 0x1006631e0
참고
헷갈리는 규칙이 많은 것 같다. 2중 포인터가 오히려 1차원 배열의 2차원 버전이랄까..
1차원 배열에서는 a != a[0] 이고, a+1 = &a[1], *(a+1) = a[1] 이지만,
2차원배열에서는 a == a[0]이며 a+1 = a[1]인데도 여전히 *(a+1) != *a[1] 이며, **(a+1) == *a[1] 이렇게 더블포인터로 해줘야 같다고 나온다.. 갖고 있는 주솟값은 같은데, 더블포인터를 안하면 값이 안나온다는 마인드... 2차원 배열도 2중의 특성을 가져야 하나보다.
a == a[0]인데도 *a 하면 안됨 ㅋ.. 꼭 2차원 배열은 포인터를 쓰면 꼭 더블로 해줘야 값이 나옴. 애초에 이런 규칙이 있는데 qsort에서 예외 아닌 예외로 인해 약속들이 파괴되어서 덕분에 나까지 포인터의 기초 개념부터 흔들리기 시작했던듯..
정리
정리하면, 내가 알고 있던 포인터와 2차원 배열에 대한 개념이 맞는데, qsort에서 void *로 캐스팅하면서 생겨나는 분열로 인해
기존의 이중포인터와 2차원 배열 사이에 약속으로 정해져 있던 부분들에 대한 개념이 모두 흔들렸다. qsort 안썼으면 이런일도 없는데..
이차원 배열의 변수에 대해 포인터로 사용하려면 이중으로 포인터를 사용해야하고, 그런 이유로 a == a[0]이라는 점에서 *a[0]은 되지만 *a는 안되는 그런 약속도 있는데, qsort에서 void *로 캐스팅하면서 이런 약속들이 무너져 내려 내 머릿속도 무너졌다.
어쨌든, 이중 포인터와 이차원 배열은 메모리 구조적으로는 다르나 요소를 사용함에 있어서는 동일하게 설계되었다.(약속들이 존재)
대신 sizeof()를 통한 메모리의 크기를 알아 올 때엔 메모리 구조의 차이가 있으니 당연히 차이가 존재하고, 또한 int **a, int b[x][x] 에서
a != a[0] , b== b[0] 인 것처럼 메모리 구조가 조금 다르기 때문에 기본적으로 약속되어 사용하는 것 이외에 void *로 덮어쓴다던가 하면 다시 그 본질이 드러나기에 차이가 생길 수 있다.(2차원 배열을 사용함에 있어 약속이 존재하는데, void * 같은 일차원으로 덮어쓴다든가 하면
2차원의 성질을 잃고 단순히 1차원으로 다뤄짐)
간단하게, 메모리 구조는 다른데, 약속이 있어서, 변수명을 통해 '요소 값'을 이르는 데 까지의 방법에 차이는 없다는 것.
(ex 2차원 배열에는 a = a[0] 이지만 *a != *a[0] 같은 약속이 있음. **a 해야 값 참조 가능.)
이런 종합적인 차이에서 void * 같은 일차원 포인터로 덮어쓰기라도 하면 요소값에 이르는 데에도 차이가 생길 수 있다는 것.
하지만 언제나 제일 큰 이유는 '메모리 구조가 달라서'(이중포인터 a와 2차원배열 b에서 애초에 요소의 포인터인 c가 가리키는건 &a[0], b[0] 이렇게 벌써 나뉨) 비롯된 것. 하지만 이게 원래같았으면 같아지게 약속된 규정이 있는데, void * 같은 포인터로 덮어쓰니 1차원으로 보게 되어서 그런 점도 큼.
int형 예시코드
// int 형 2차원배열
#include <stdio.h>
#include <stdlib.h>
int compa(int *a, int *b) {
int x = *a;
int y = *b;
if(x < y)
return -1;
else if(x > y)
return 1;
else
return 0;
}
int main() {
int x[2][2];
int nx;
scanf("%d", &nx);
for(int i = 0; i < nx; i ++ ){
scanf("%d %d", &x[i][0], &x[i][1]);
}
qsort(x, nx, sizeof(x[0]), (int(*)(const void *, const void *))compa);
for(int i = 0; i < nx; i ++ ){
printf("%d %d\n", x[i][0], x[i][1]);
}
}
//int형 2중포인터
#include <stdio.h>
#include <stdlib.h>
int compa(int **a, int **b) {
int x = **a;
int y = **b;
if(x < y)
return -1;
else if(x > y)
return 1;
else
return 0;
}
int main() {
int **x;
int nx;
scanf("%d", &nx);
x = (int**)calloc(nx, sizeof(int *));
for(int i = 0; i < nx; i++) {
x[i] = (int *)calloc(2, sizeof(int));
}
for(int i = 0; i < nx; i ++ ){
scanf("%d %d", &x[i][0], &x[i][1]);
}
qsort(x, nx, sizeof(x[0]), (int(*)(const void *, const void *))compa);
for(int i = 0; i < nx; i ++ ){
printf("%d %d\n", x[i][0], x[i][1]);
}
}
추가로, 포인터변수와 배열에 대한 문자열 길이 실험
char a[10] = "hello";
char b[10] = "hi";
char *c = a;
char *d = b;
printf("%ld \n", strlen(a));
printf("%ld \n", strlen(b));
printf("%ld \n", strlen(c));
printf("%ld \n", strlen(d));
OutPut :
5
2
5
2
이렇게 포인터 변수에 값을 대입해도 길이는 같게 나온다.
추가로, 2차원 배열 주소 확인
#include <stdio.h>
int main() {
int a[2][2];
a[0][0] = 1;
a[0][1] = 2;
a[1][0] = 3;
a[1][1] = 4;
printf("%p\n", a+1);
printf("%p\n", *(a+1));
printf("%p\n", a[1]);
}
Output :
셋 다 같음.
글쓰는거 포함해서 12시간썼네..
Q&A 참고 추가! 괜찮은 내용인 것 같음.
'[백준]' 카테고리의 다른 글
| [BaekJoon/백준] 15649번 (0) | 2020.12.05 |
|---|---|
| [BaekJoon/백준] 10814번 (0) | 2020.12.03 |
| [BaekJoon/백준] 11651번 (0) | 2020.12.01 |
| [BaekJoon/백준] 11650번 & 나중에 다시보기 (0) | 2020.12.01 |
| [BaekJoon/백준] 1427번 (0) | 2020.11.29 |
