깊이 우선 알고리즘 구현에 있어

gnoygnas의 이미지

깊이 우선 알고리즘에서 자주 나오는 8퍼즐을 허접한 실력이지만,
나름대로 구현을 해 보았습니다.
아직 스택은 사용하지 않았습니다...

DFS라는 함수에서 재귀 호출을 하는데, 깊이 2에 들어가면 값이 제대로 바뀌지 않습니다....혼자 해결하려고 발버둥을 치지만 실력이 미천하여 감히 고수님들의 조언을 부탁드릴까 합니다.

소스 첨부합니다.

참고로 배열중에 0의 값이 커서를 나타냅니다.

출발 노드
2 8 3
1 6 4
7 0 5

목표 노드
1 2 3
8 0 4
7 6 5

또 부탁드릴게 있다면, 제 소스를 보시고 (문제되는 부분이 많을거라 생각하는데) 많은 지적을 부탁드립니다. (내가 구현하면 이부분은 이렇게 하겠는데라는등...아무거나 상관없습니다...)

File attachments: 
첨부파일 크기
파일 DFS_V4.cpp12.71 KB
파일 DFS_V5.cpp11.41 KB
winner의 이미지

source code 를 보면 Visual C++ 를 사용하실 것으로 생각되는 BOOL 도 있네요.

하지만 source code 는 명확히 C source 인데.

확장자를 cpp 로 하면 C++ 문법으로 번역하기 때문에 잘못된 습관이 들 수 있습니다.

확장자 바꿔서 compile 해도 완벽하군요.... -_-

winner의 이미지

저도 지난 학기 Algorithm 수업 때 해서 정겹네요.

저희 교수님은 5*5 puzzle 를 내서 얘들 완전히 죽였다는.....(-_-).

원래 Sam Loyd 가 처음 이 문제를 냈을 때는 15(4*4) 였었다고 하는데...

winner의 이미지

우선 BOOL 은 enum 을 통해 정의했을 겁니다.
typedef enum {FALSE, TRUE} BOOL;

그리고 두개의 값을 나타내는 구조체를 정의한 후 이를 좌표로 정의합니다.
이 경우 좌표평면보다는 행렬표기가 더 적합하므로
typedef struct {int row, int column;} coordinate;

이것은 좌표뿐 아니라 이동방향에도 쓸 수 있습니다.

const coordinate available_direction[] = {
    {0, 1}, {0, -1},
    {1, 0}, {-1, 0}
};

물론 이를 좌표를 이동시키는 연산방법이 필요하겠죠.
대게는 함수로...

BOOL move(coordinate zero_position, coordinate direction)

확장자가 .c 로 바꾸면 malloc 앞의 명시적 형변환은 필요없습니다.
C 에서는 void * 가 자동변환되니까요.

오히려 명시적 형변환은 적법한 변환인지 검사를 안하기 때문에 피하라고 추천하는 분도 있습니다.

C++ 와의 호환을 생각한다면 어쩔 수 없습니다만 실력있는 분들일 수록 C, C++ 의 compiler 호환은 생각하지 않더군요.

물론 양 쪽의 object code 를 link 할 수 있는 방법을 적용합니다.

winner의 이미지

아시겠지만

조건검사

처리
재귀호출
역처리.

입니다.

잘은 모르겠습니다만 역처리가 빠진 느낌입니다.

gnoygnas의 이미지

솔직히 말씀드리면, 인공지능이라는 과목에 있는 문제입니다..
숙제가 되었건, 하고 싶어 했건...어찌되었건간에,
이 문제를 풀면서 제 나름대로의 프로그래밍 수준을 파악(제 자신을 알았죠.. :( )했고,
반대로 이론에 대한 이해를 높이는데 좋은 계기가 된거 같습니다..

winner님께서 말씀하셨듯이 사소한 문제부터 (확장자) 고쳐나가야겠습니다.
그동안 c, cpp를 그리 구별하지 않고 사용해서인지 별로 느끼지 못했는데, 지적 고맙습니다.

int *p[4];

p=(int*)malloc(sizeof(int));
여기서 구지 int*를 명시하지 않아도 된다는 얘기죠? default로 void*?

그리고 이해가 가지 않는 부분이 있는데, 역처리라 하면 구체적으로 무엇을 말하는 건가요? 역처리라......

One must, In fact, Love your pursuit
My home is below...Well, just go own your gait!

winner의 이미지

저는 되추적 Algorithm 구현시 전역변수를 즐겨 만듭니다.

이것이 data hiding 관점에서 좋은 것이 아니라는 것은 압니다만 편하다는 생각에 막 씁니다.(-_-)

block 안에 생성되는 자동변수는 block 이 종료되면서 사라지는데 이를 이용해서 보통 되추적 Algorithm 을 pseudo code 로 설명할 때는 역처리가 빠지기 마련입니다.

즉 재귀호출이 이루어지면서 매개변수에 필요한 정보를 몽땅 넣어 복사하는 거죠.
이렇게 되면 해당깊이에서 빠져나오면 원래대로 돌아가게 됩니다.

하지만 전역변수를 건드리면 수작업으로 원래상태로 돌려놔야 합니다.

이 방법을 제가 즐겨쓰는 이유는 우선 memory 가 아껴지기 때문이죠.
몽땅 매개변수에 넣어 복사하면 재귀의 깊이에 따라 memory 요구량이 늘어나니까...
또한 복사를 몽땅하는 것에 비해 처리량이 즐어들지 않을까라는 막연한 기대심리도 있습니다...(-_-)... 이부분은 제가 잘못생각하는거죠. (경우에 따라 다릅니다. 특히 최신의 Itanium 은 공유변수를 사용하는 것보다 자동변수가 최적화를 통해 더 좋은 성능을 내는 경우가 많다고 하더군요.)

즉 저는 puzzle table 하나가지고 바꿨다가 돌려놓으면서 작업을 합니다.
이 경우 추가적으로 생성했다가 없애는 작업은 direction 만 하면 되죠.

gnoygnas 씨가 작성하신 것은 비록 동적할당을 사용한 수작업입니다만 부모 node 의 value 는 보존되고, 자식 node 에 value 를 복사하므로 문제될 것은 없다고 생각합니다.

다만 이렇게 할 경우 동적할당된 자식 node 들은 재귀호출을 빠져나오기 전에 해제해주셔야 memory 가 반환되겠죠.

source 어디에서도 malloc 은 있으나 free 는 없네요.

최대재귀깊이가 3일때는 그나마 괜찮지만 아마도 8 puzzle 이 3 에서 끝날 거라고 생각되지 않는군요.

아마도 더 늘리실텐데 그 때에는 memory 가 감당 못할 수도 있습니다.

또한 iPuzzle과 gPuzzle 은 동적할당할 이유가 없어보입니다.

마찬가지로 가급적 각 node 의 생성은 자동변수로 생성하는 것이 좋겠습니다.
(그렇게 하면 free 도 필요없죠.)

물론 각 node 를 재귀를 통해 decision tree 를 남겨두는 것이 목적이 아니라면 말입니다만...

동적할당과 해제는 상당히 재미있는 기법입니다만 작은 program 이나 환경에 따른 문제가 아니라면 필요한 경우는 자료구조를 만드는 것 이외에는 없습니다.

동적할당과 해제는 OS 에 의해서 처리되는데 그것이 kernel mode 로 넘어가서 처리되든 그렇지 않든 system call 을 사용하고, OS 의 memory 관리작업에 의해 성능저하를 불러올 수 있습니다.

또한 memory 의 동적관리로 인해 OS 는 추가적인 memory 를 소모해야 합니다.

다른 이야기로 넘어가서 이전에 제가 적었던 coordinate 는 이차원 배열로 table 을 표현할 때 적당한 방법입니다.

gnoygnas 씨는 일차원배열을 사용했더군요.

Programming Language 의 풍부한 능력을 제대로 사용하지 못하고, 제한된 기능만 가지고서는 Algorithm 의 표현도 제한됩니다.

또한 source 를 보면 제가 보기에 중복되었다고 생각되는 부분이 많습니다.
우선 Initialize 와 DFS 는 중복이 너무 많습니다.
저라면 꼭 필요한 Initialize 는 main 에서 처리하고 DFS 하나로 통일했을 겁니다.

swapNodeValue 에서도 역시 중복이 너무 많아보이고요.
사실 저도 이런식으로 puzzle 을 이동시키려다 만든 것이 coordinate 와 available_direction 이었습니다.

이차원배열을 행렬위치표기를 사용해서 blank 의 위치에 direction 을 더해서 새로운 위치를 만들고, 값을 바꾸는 거죠. direction 의 반대방향검증도 편할테구요.

value 의 값을 복사하거나 비교할 때는 함수를 사용하심이 좋을 거라고 생각합니다. 문자배열로 만든다면 strncpy, strcmp, 정수배열을 그대로 쓰신다면 memcpy, memcmp...

참고로 memcpy 와 memcmp 는 쌍으로 사용하심이 좋습니다. element 단위 복사와 element 단위 비교또한 쌍으로 쓰셔야 합니다.

만약 element 단위로 복사하고, memcmp 로 비교하시면 padding bit 로 인해 다른 결과가 나올 수 있습니다.

시간여유가 있으시다면(아마 없겠지만... -_-... 숙제제출하고 나서도 시간을 내셔서 하신다면) 구조적인 측면을 간소화시키기 위해 source 를 이리저리 뒤집어보는 것이 공부에 좋을 거라고 생각합니다.

또한 Programming Language 를 좀더 자세히 공부하시고, 표준 library 의 기능을 활용하시기 바랍니다.

제가 생각하기에는 학부과정에서 필요한 C library 는 stdio.h, stdlib.h, string.h, ctype.h, math.h 에 다 들어있다고 생각됩니다.

음.. 지금보니 memcpy, strncpy 도 필요없이
*childNode[i] = *pNode[pCount];
하신 후 변경되는 정보만 고쳐도 되겠군요.

gnoygnas의 이미지

Quote:
Programming Language 의 풍부한 능력을 제대로 사용하지 못하고, 제한된 기능만 가지고서는 Algorithm 의 표현도 제한됩니다.

위에 말씀하신것에 느끼는 바가 큽니다..
그동안 C를 해 왔다하지만, memcpy는 알고 있어도 사용할 줄 몰랐고, memcmp라는 함수는 처음 들어보듯이 C의 1% 능력조차도 제대로 사용했나 쉽더군요..

실력이 모자라 winner님이 말씀하신것을 100% 수용하진 못했어도,
많은 도움이 되었습니다....

다행히 본 문제에 대해 시간제약이 없어 그동안 짰던 것을 차근차근 뜯어보고 수정해봐야겠네요....^^

PS. 지금 제게 필요한 것은 고기 낚는 법을 배우는 것입니다. :D

One must, In fact, Love your pursuit
My home is below...Well, just go own your gait!

winner의 이미지

솔직히 저 역시 쥐뿔도 모릅니다.

BBS 에 제 이름으로 검색해보시면 헛소리만 늘어놓고 있던 것을 알 수 있습니다.

또한 저 역시 memcmp 를 사용한 적이 없습니다...(-_-)

기타 여기에 적어 놓은 C 언어에 대한 것도 1년 전만 해도 몰랐던 것이었고, 또한 Algorithm 수업에서 동일한 문제를 풀어본 적이 있었기에 다행히 답변을 드릴 수 있었던 것 같습니다.

겸손하신 모습이 보기 좋네요.
저도 좀 자중이 필요할 듯... (-_-)

1% 도 못쓴다고 하셨지만 조금만 노력하시면 금방 실력이 좋아지실 것 같습니다.

어쩌면 그 이후에 왜 이렇게 별 것도 아닌 것 가지고 낑낑댔지라는 생각이 드실지도...(제가 그랬었거든요... ^^)

그럼 열심히 하세요!!!

그리고 모르시는 것이 있으면 또한 물어보셔도 좋습니다...
원래 community 라는 것이 정보의 공유이니까요.
열심히 노력하시고, 그 이후에 물어보시는데다 그냥 숙제 해달라는 것도 아니니까요.
(단 숙제라는 티는 내지 않음이 좋을 듯... -_-)

gnoygnas의 이미지

winner님 해결했습니다...
기뻐해 주세요~~ :D :D

고생끝에 낙이라~

이럴때 두고 하는 얘기가 아닌가 싶네요....
내가 원하는데로 프로그램이 돌아가 줄때 그 기쁨이란!!!~~~~

이제 해결하고픈 것은 출발 노드와 목표 노드를 동적으로 변경해주는거하고,
출발노드로부터 찾아간 경로를 표시해주는 일이네요...

동적으로 값을 변경하는 것은 rand()를 쓰면 될것 같은데, 경로를 표시해주는 것은 당장은 아이디어가 떠오르지 않네요..옛날에 TREE구현해서 비슷하게 한적이 있어서 참조하면 될것 같은데....

지금까지 짠 소스입니다...
님 말씀대로 중복되는 부분을 없애는데 노력했고요...동적할당도 그렇고...
version으로 따지자면 0.5 정도 되겠네요..

직접적으로 소스를 고쳐주시진 않았어도, winner님이 힘이 되어 주셨습니다.. :lol:

댓글 첨부 파일: 
첨부파일 크기
파일 0바이트

One must, In fact, Love your pursuit
My home is below...Well, just go own your gait!

gnoygnas의 이미지

아래 소스와 같이 1~10까지 랜덤한 숫자를 출력하고 싶습니다.
단 중복이 안되게 해야 하는데, 잘 되지 않네요~
어떻게 해결할 수 있나요?

	
int tRand[9];
	
srand((unsigned) time(NULL)); 
	
for (i=0; i<MAX_VALUE; i++) {
	tRand[i]=rand() % 10 + 1;
	printf("%d", tRand[i]);
}

One must, In fact, Love your pursuit
My home is below...Well, just go own your gait!

맹고이의 이미지

단순 무식하게 매번 뽑을때마다 저장된 배열과 비교를 해볼 수도 있고

10개 짜리 배열을 미리 만들어서 번호를 적절히 체크를 한다던지...

random_shuffle() 이라는 STL을 사용할 수도 있고

효율을 떠나서 연구를 해보심이... 8)

Tony의 이미지

RAND 계열의 모든 함수는 중복을 피할 수 없습니다. 일단 순서대로 나열해 놓고
섞어주는 함수를 RAND로 돌려서 순서를 바꾼 후 순서대로 처리하는게 옳습니다.
원하시는게 랜덤한 '숫자'인지 랜덤한 '순서'인지가 확실해지면 고민꺼리는
아니라고 생각됩니다. ^^;

fantom의 이미지

srand( (unsigned)time( NULL ) );

이런식으로 해서...

rand() %10 이렇게 하면...

:shock:

열심히 프로그램 짠 당신... 버그 잡아라...

gnoygnas의 이미지

위에 말씀하신대로 0~8까지 배열에 잡아 놓고, rand()함수로 인덱스 값을 변경 했더니 잘 돌아가는군요....^^ 감사합니다...

	int iDimension[9]={0,1,2,3,4,5,6,7,8};
	int i, t, temp, n;

	// 0~8까지 랜덤한 숫자를 얻기 위해
	srand((unsigned) time(NULL)); 
	t=rand() % 9;

	for (i=0; i<MAX_VALUE; i++) {
		if (t >= 0 && t <= 7) {
			n = 1;
		}
		else if (t == 8) {
			n = -1;
		}

		temp=iDimension[t];
		iDimension[t]=iDimension[t+n];
		iDimension[t+n]=temp;

		t=rand()%9;
	}

하나하나 해결해 나가니 참 기분 좋네요~~ :D

궁금한 것이 있는데요~
동적(malloc())으로 메모리 할당을 해주면 free를 사용하지 않는한
heap에 남아 있다고 알고 있습니다.

그런데 이상한게 윈도우 작업 관리자에서 메모리 할당하는 것을 보면 그리 크게 늘지 않습니다. 더군다나 재귀호출 후 돌아올때는 메모리가 줄어드는 현상을 볼 수 있더군요....재귀 호출후 돌아올때 동적 할당된 메모리까지 회수하는 것인지 지금 좀 햇갈리네요~~

One must, In fact, Love your pursuit
My home is below...Well, just go own your gait!

winner의 이미지

대학원 선배가 만든 puzzle 의 test program 에서 malloc 은 있는데 free 는 없어서 물어봤더니 선배왈
"요새는 compiler 가 좋아서 다 알아서 해줘!"

-_- 저는 잘 속습니다...

exit 호출 전에 getchar() 를 써서 대기시켜 놓아보세요.
그대로입니다.

깊이 5로는 그다지 memory 소모가 안되니 점유를 별로 안하겠죠.

참고로 제가 만든 program 은 250MB 를 씁니다.(-_-)
처음에는 1.8GB 를 써서 Server 관리자였던 친구한테 한 소리 들었습니다.

random shuffle algorithm 을 제가 처음 본 것은 'C How to Program' 에서였는데 상당한 충격이었습니다.('C++ How to Program' 으로 편견을 갖고 봐서인지 그 책 bubble sort 의 안쪽 loop 의 초기화표현식이 틀린 걸보고, 전혀 안봤었죠. 그리고는 친구 줘버렸답니다... 지금 생각하면 매우 아깝군요. 'C++ How to Program' 도 사실 남의 말만 듣고 편견을 가졌던건데... -_-)

어젯밤에 심심해서 확률을 계산하니 정확하더군요.

그 전에 한번 random shuffle 이 필요한 적이 있었는데 linked list 를 써서 했었다는... -_-...

C++ 의 STL 은 가만히 보면 정말 흥미로운 것이 많습니다. rotation 도 쉬울 줄 알았는데 추가적인 memory 의 소모를 절약하기 위해서는 상당히 재미있는 source 가 나왔죠. next_permutation 이것도 예술이었습니다.

gnoygnas 씨께 묻고 싶은 것이 있는데 전의 source 의 bug 에 대해서 간략히 설명해 주시면 감사하겠습니다. 궁금해서요.

Program 은 거의 완성이 되어가는 모양입니다.

이제 경로추적만 남았나요?
어렵지 않게 해내리라 봅니다.

전의 제가 썼던 글을 다시 정리해서 gnoygnas 씨의 source 에 대해서 질문을 하겠습니다.

1. 왜 C 언어로 작성했는가?
2. 왜 동적할당을 사용했는가?
3. 왜 동적할당을 사용하고 해제는 하지 않았는가?
4. 왜 malloc.h 를 include 했는가?
5. 왜 TRUE, FALSE 를 define 했는가?
6. MAX_STACK, initStack, isEmptyStack, push, pop, printCurrentNode, curent_stack, stack 의 의미는?
7. 왜 1차원배열을 사용했는가?
8. 왜 PUZZLE 내부에 depth 를 저장하는가?
9. 문제출제자(교수일 수도 있고, gnoygnas 일 수도 있고...)는 재귀를 통해 결정(decision) tree 를 남기길 원했는가?

확장자는 여전히 cpp 이군요.

아직도 source 는 refactoring 의 여지가 많습니다.
최대한 단순화시키도록 하세요.

aspilla의 이미지

malloc 함수가 void* 형을 return한다는 것을 알고 있을 것입니다.
저는 embedded 환경에서 주로 c로 coding을 합니다만 void*형을 casting을 해주지 않는 것이 더 좋다는 이야기는 금시초문입니다.
요즘 compiler가 좋아서 void*형을 malloc에서 자동 casting한다고 해서 void* 가 casting없이 사용가능하다고 생각하면 오산입니다.

#include<stdlib.h>
#include<stdio.h>

int main(void) {

	int* i;
	void* a;
	int	j;

	i = malloc(10);

	i[9] = 8;
	
	j = 4;	
	
	a = &j;
	
//	printf("a[0] = %d\n", *a);
	printf("a[0] = %d\n", *(int *)a);
	printf("a[0] = %d\n", i[9]);
	

	return(0);

}

malloc은 error가 없습니다. (심지여 sizeof(int)를 뺐는대도 gcc에선 잘 동작하는군요.)
하지만 다른 부분에서 *a의 사용은 invalid void expression이란 error를 발생시킵니다. void*를 다른 형태로 사용할려면 반드시 casting되어야 합니다.
다른 compiler에서 error를 발생시킬 여지가 있는 비표준 코드는 사용하지 않는 것이 좋습니다.

winner의 이미지

일단 aspilla 씨가 작성하신 code 중

i 와 관련된 것은 비록 사용방법에서는 문제가 있지만(i[9] = 8; 이 표준에 정의되지 않는 행동일 겁니다.) 문법상 오류가 없는 것으로 압니다. 그러므로 gcc 는 설령 -ansi -Wall -pedantic 을 다 줘도 경고 하나 안냅니다.
a 는 물론 역참조하기 전에 casting 을 해줘야죠.
void * 는 그야말로 주소값만 가지고 있으니까 어떤 방법(type)으로 해석할 지 결정을 해줘야 합니다.

malloc 으로 return 된 void * 는 int * 로 자동형변환 되어 i 에 저장되는 겁니다.

제가 알기로는 void * 는 어떤 pointer 로도 변환이 가능하며 또한 그 역도 가능한 것으로 알고 있습니다.

좀더 공부해서 명확한 답변을 드릴 수 있으면 좋겠습니다만 여기까지가 지금의 제 한계군요... (-_-)

시간이 나는데로 찾아보도록 하죠.

eungkyu의 이미지

aspilla wrote:
malloc 함수가 void* 형을 return한다는 것을 알고 있을 것입니다.
저는 embedded 환경에서 주로 c로 coding을 합니다만 void*형을 casting을 해주지 않는 것이 더 좋다는 이야기는 금시초문입니다.
요즘 compiler가 좋아서 void*형을 malloc에서 자동 casting한다고 해서 void* 가 casting없이 사용가능하다고 생각하면 오산입니다.

void *들 casting 없이 사용하자는 얘기가 아닙니다. 단지, malloc에서 리턴되는 주소값을 다른 형의 주소로 대입할 때 "명시적인" casting이 없어도 된다는 것이며, 실제로 "명시적으로" casting하지 않는 것이 좋은 경우가 있다는 것입니다.
Quote:

#include<stdlib.h>
#include<stdio.h>

int main(void) {

	int* i;
	void* a;
	int	j;

	i = malloc(10);

	i[9] = 8;
	
	j = 4;	
	
	a = &j;
	
//	printf("a[0] = %d\n", *a);
	printf("a[0] = %d\n", *(int *)a);
	printf("a[0] = %d\n", i[9]);
	

	return(0);

}

malloc은 error가 없습니다. (심지여 sizeof(int)를 뺐는대도 gcc에선 잘 동작하는군요.)
하지만 다른 부분에서 *a의 사용은 invalid void expression이란 error를 발생시킵니다. void*를 다른 형태로 사용할려면 반드시 casting되어야 합니다.


malloc에서 에러가 없는 것과 *a의 사용에서 에러가 나는 것은 아무 관계가 없습니다. 무엇을 주장하시려 하는 것인지 이해가 잘 안되네요.
mach337의 이미지

aspilla wrote:
malloc 함수가 void* 형을 return한다는 것을 알고 있을 것입니다.
저는 embedded 환경에서 주로 c로 coding을 합니다만 void*형을 casting을 해주지 않는 것이 더 좋다는 이야기는 금시초문입니다.
요즘 compiler가 좋아서 void*형을 malloc에서 자동 casting한다고 해서 void* 가 casting없이 사용가능하다고 생각하면 오산입니다.

#include<stdlib.h>
#include<stdio.h>

int main(void) {

	int* i;
	void* a;
	int	j;

	i = malloc(10);

	i[9] = 8;
	
	j = 4;	
	
	a = &j;
	
//	printf("a[0] = %d\n", *a);
	printf("a[0] = %d\n", *(int *)a);
	printf("a[0] = %d\n", i[9]);
	

	return(0);

}

malloc은 error가 없습니다. (심지여 sizeof(int)를 뺐는대도 gcc에선 잘 동작하는군요.)
하지만 다른 부분에서 *a의 사용은 invalid void expression이란 error를 발생시킵니다. void*를 다른 형태로 사용할려면 반드시 casting되어야 합니다.
다른 compiler에서 error를 발생시킬 여지가 있는 비표준 코드는 사용하지 않는 것이 좋습니다.

gcc 로 컴파일 하고 실행하면 되는것 같지만 -lefence 옵션을 사용하면 즉 Electric Fence 를 사용하면
i[9] = 8;
에서 Segmentation Fault 를 일으키는군요.

sangwoo의 이미지

mach337 wrote:

gcc 로 컴파일 하고 실행하면 되는것 같지만 -lefence 옵션을 사용하면 즉 Electric Fence 를 사용하면
i[9] = 8;
에서 Segmentation Fault 를 일으키는군요.

당연히.. i[9]는 *(i + 9)이고, i는 pointer to int 이니까

i = malloc(sizeof(int) * 10);

라고 해야죠..
이건
i = (int *)malloc(10); 

라고 해서 해결되는 문제가 아닙니다.
"명시적인" 타입 캐스팅과는 무관한 문제고, 단순히 malloc된 메모리 바깥을
참조함으로써 생기는 문제입니다. (i386에서는 보통 sizeof(int) == 4이니까요..)
참고로, C99에서 void * type은 명시적으로 타입 캐스팅을 해주지 않아도
틀린 표현이 아닙니다. 가령
void *generic_ptr;
int *int ptr;

generic_ptr = int_ptr;        /* OK */
int_ptr = generic_ptr;        /* OK */

가 모두 적절합니다.

----
Let's shut up and code.

mach337의 이미지

Quote:
당연히.. i[9]는 *(i + 9)이고, i는 pointer to int 이니까
i = malloc(sizeof(int) * 10);

라고 해야죠..
이건
i = (int *)malloc(10); 

라고 해서 해결되는 문제가 아닙니다.
"명시적인" 타입 캐스팅과는 무관한 문제고, 단순히 malloc된 메모리 바깥을
참조함으로써 생기는 문제입니다. (i386에서는 보통 sizeof(int) == 4이니까요..)
참고로, C99에서 void * type은 명시적으로 타입 캐스팅을 해주지 않아도
틀린 표현이 아닙니다. 가령
void *generic_ptr;
int *int ptr;

generic_ptr = int_ptr;        /* OK */
int_ptr = generic_ptr;        /* OK */

가 모두 적절합니다.

예...맞습니다. 저도 그말이 하고 싶었습니다.
포인터에 형(type)을 지정하는 큰 이유중의 하나는 가르키는 변수의
바이트로 표현되는 크기가 형 마다 틀리기 때문에 위에서 처럼 포인터 연산을 할경우
포인터가 4씩 증가하는 경우가 있거나 1씩 증가하는 경우가 생깁니다.
때문에 Type Casting 을 적절하게(?) 사용해야 하겠죠...
gnoygnas의 이미지

그동안 학교일로 인해 정신이 없었네요..
답변이 조금 늦었습니다... :lol:

winner wrote:
gnoygnas 씨께 묻고 싶은 것이 있는데 전의 source 의 bug 에 대해서 간략히 설명해 주시면 감사하겠습니다. 궁금해서요.

Program 은 거의 완성이 되어가는 모양입니다.

이제 경로추적만 남았나요?
어렵지 않게 해내리라 봅니다.

전의 제가 썼던 글을 다시 정리해서 gnoygnas 씨의 source 에 대해서 질문을 하겠습니다.

1. 왜 C 언어로 작성했는가?
2. 왜 동적할당을 사용했는가?
3. 왜 동적할당을 사용하고 해제는 하지 않았는가?
4. 왜 malloc.h 를 include 했는가?
5. 왜 TRUE, FALSE 를 define 했는가?
6. MAX_STACK, initStack, isEmptyStack, push, pop, printCurrentNode, curent_stack, stack 의 의미는?
7. 왜 1차원배열을 사용했는가?
8. 왜 PUZZLE 내부에 depth 를 저장하는가?
9. 문제출제자(교수일 수도 있고, gnoygnas 일 수도 있고...)는 재귀를 통해 결정(decision) tree 를 남기길 원했는가?

1. C언어로 작성한 이유는 제가 다른 언어는 그리 잘 모릅니다. 그렇다고 C를 잘한다는 것은 아닙니다..절차적 프로그래밍이 제게 좀 맞는다고 할까요? 다른 이유는 없습니다.

2. 동적할당...지금 생각해보니 왜 저도 동적할당으로 했을까요? 실력이 없다보니 예전 습관 못버린다고 배열보다도 동적할당을 고수했나봅니다. 재귀호출을 하면서 목표노드를 찾았을 경우 부모 노드로부터의 경로를 찾기가 더 수월하지 않나요? 아무래도 배열보다는...

3. free()를 어느 위치에서 해제를 해야하는지 사실 찾지 못했습니다...free() 사용하니 자꾸 메모리 덤프에러가 나서...

4. malloc()를 이용하려면 당연히 추가해야 하지 않나요?

5. TRUE, FALSE는 부모노드를 기억하기 위해 사용했습니다..(수정한 소스에서는 사용했습니다..)

6. 깊이 우선 알고리즘에서 기본적으로 stack 구조를 사용해서 문제를 해결해 나갑니다..비록 제가 짠 소스에서는 사용하지 않았지만요...

7. 1차원 배열로 선언해서 blank 값을 찾는 것이 효율적이라 봅니다..

8. 각 노드마다 깊이를 기억하게 하려고 했으나 사용하지 않아 삭제했습니다.

9. 문제의 의도를 잘 파악하지 못했지만, 결정 트리? 즉 경로를 말씀하시는 건지 모르겠네요...

출발 노드로 부터 목표 노드까지의 경로를 나타나게 했습니다..
알고리즘을 내가 원하는데로 프로그래밍하니 참 기쁘군요~ ^^

One must, In fact, Love your pursuit
My home is below...Well, just go own your gait!

맹고이의 이미지

man malloc 해보면 아시겠지만
malloc()은 stdlib.h에 있습니다.

gnoygnas의 이미지

여태 몰랐습니다..

동적할당이 필요하면 malloc.h를 습관적으로 넣어주곤 했는데,
stdlib.h만으로도 VC++에서도 되네요...^^

감사합니다..

One must, In fact, Love your pursuit
My home is below...Well, just go own your gait!

winner의 이미지

gnoygnas wrote:
1. C언어로 작성한 이유는 제가 다른 언어는 그리 잘 모릅니다. 그렇다고 C를 잘한다는 것은 아닙니다..절차적 프로그래밍이 제게 좀 맞는다고 할까요? 다른 이유는 없습니다.

솔직히 저도 별 뜻 없이 질문했습니다만 저희 학교에서는 숙제는 거의 대부분 무조건 C 로 하라고 합니다. C++ 도 허용해주기도 합니다만...

C 언어는 전산학과 학생들한테는 필수인걸까요?...
C 언어는 물론 중요합니다만 뭐랄까? 선택의 자유를 달라고 하고 싶습니다.

Algorithm 이나 인공지능 같은 수업을 할 때 C 언어에 묶여서 수업을 듣다 보면 조금 화납니다. 최근에는 Java 인가요?

사실은 저도 C/C++ 밖에는 못합니다...(-_-)

gnoygnas wrote:

2. 동적할당...지금 생각해보니 왜 저도 동적할당으로 했을까요? 실력이 없다보니 예전 습관 못버린다고 배열보다도 동적할당을 고수했나봅니다. 재귀호출을 하면서 목표노드를 찾았을 경우 부모 노드로부터의 경로를 찾기가 더 수월하지 않나요? 아무래도 배열보다는...

이 질문한다는 것 깜박했군요.
최단경로를 찾아야 하는가?... 아니면 어떤 경로든 하나만 찾으면 되는가?

아무 경로든 찾기만 하면 된다면 재귀호출을 거슬러 올라 오면서 list 로 저장할 때만 쓰면 될 거라고 생각합니다.(안 그러면 거꾸로 밖에 출력을 못하니까... -_-...) 혹은 list 를 stack 방식으로 동작시키면서 찾고 머리에서부터 출력하면 되겠죠.

즉 경로를 찾았을 때 바로 재귀호출을 탈출하는거죠.

저는 PUZZLE 의 배열도 필요없다고 생각합니다.
하나만 만들면 될거라고 봅니다.

gnoygnas wrote:

3. free()를 어느 위치에서 해제를 해야하는지 사실 찾지 못했습니다...free() 사용하니 자꾸 메모리 덤프에러가 나서...

마지막 질문과 조금 연관되는데 만약 경로를 구축해야 한다면 program 을 종료하기 전에 tree 를 여행하면서(이것도 재귀호출...) 해제해주면 될거라고 봅니다.

그렇지 안다면 자식 node 를 방문하기 위한 재귀호출이 끝나면 그 node 는 더이상 필요없는 겁니다.

위에서 말한 역처리에 해당하죠.

gnoygnas wrote:

4. malloc()를 이용하려면 당연히 추가해야 하지 않나요?

mallo.h 는 Linux 에도 있는데 C 표준 Library 에는 없습니다.
memory 할당함수를 세밀하게 사용하기 위해서 필요한 것 같습니다.

gnoygnas wrote:

5. TRUE, FALSE는 부모노드를 기억하기 위해 사용했습니다..(수정한 소스에서는 사용했습니다..)

부모노드를 TRUE, FALSE 로 어떻게 기억시키죠?
음.. 저는 잘 모르겠군요.

gnoygnas wrote:

6. 깊이 우선 알고리즘에서 기본적으로 stack 구조를 사용해서 문제를 해결해 나갑니다..비록 제가 짠 소스에서는 사용하지 않았지만요...

되추적 혹은 DFS 는 stack 을 사용하다고 합니다만 재귀호출을 사용하는 것이 stack 을 사용하는 것입니다. 보통 더이상 쓸 필요가 없습니다.
이 경우 경로를 바르게 출력하기 위해서 거꾸로 저장하기 위해 필요할 뿐입니다.

하지만 gnoygnas 씨는 경로를 tree 로 구축하셨기 때문에 더이상 필요가 없는 것입니다.

gnoygnas wrote:

7. 1차원 배열로 선언해서 blank 값을 찾는 것이 효율적이라 봅니다..

음.. loop 하나로 해결됩니다만 2차원배열이 중첩loop 을 사용해야 합니다만 성능의 효율이라고 보긴 어렵구요. 아마도 source 차원에서는 간단하겠죠.

하지만 1차원배열을 사용함으로써 어지러운 if/else chain 과 switch 가 필요했습니다.

전체적으로 비효율적이라고 생각합니다. swapNodeValue 가 쓸데없는 중복이라는 생각이 안 드나요?

또 한가지 방법은 blank 의 위치를 계속해서 추적하는 변수를 만드는 것입니다.

gnoygnas wrote:

8. 각 노드마다 깊이를 기억하게 하려고 했으나 사용하지 않아 삭제했습니다.

gnoygnas 씨가 아직 인식이 부족한 부분이 DFS 에서 stack 의 역할입니다.
DFS 가 BFS 보다 효율적인 것은 stack 으로 깊이 하나당 하나의 상태만 저장하면 되기때문에 memory 의 사용이 적게 사용되는 것입니다.

재귀호출과 stack, 그리고 Decision Tree 의 DFS 는 여기서는 모두 같은 의미라고 할 수 있습니다.

gnoygnas wrote:

9. 문제의 의도를 잘 파악하지 못했지만, 결정 트리? 즉 경로를 말씀하시는 건지 모르겠네요...

Decision Tree(의사결정 Tree) 란 작업을 완료하기 위해 필요한 작업을 Tree 로 표현한 것입니다.

음 이경우는 상태공간 Tree 라는 말이 정당하겠군요.

상태공간 Tree 는 상태(이경우는 puzzle 판)를 Tree로 표현하는 거죠.

찾아가는 모든 경로를 Tree 로 저장하길 원했다면 동적할당을 통해 tree 를 구축하는 것이 이해가 가기 때문에 한 질문이었습니다.

이것으로 이 source 에 대한 제 생각을 마칠까 합니다.

더이상 했다가는 gnoygnas 씨의 source 가 제 생각대로만 작성될 위험이 있을 것 같습니다. 저도 실력없는데...(-_-)..

마지막으로 다시 말합니다만 같은 문제도 여러가지 Algorithm 이 나올 수 있듯, 같은 Algorithm 도 개발환경(Hardware, Programming Language 등)과 작성자에 따라 여러가지 source 가 나올 수 있습니다.

숙제는 끝났습니다만 이미 해결된 source 에 대해서 여러가지 생각을 해보고, 다른 사람들의 source 를 분석하는 것 또한 공부에 도움이 되리라고 봅니다.

더이상 단순화시킬 수 없을 때까지 단순화시켜라라고 Einstein 이 말했다고 하더군요.
Design 을 단순하게 유지하도록 노력하세요.

물론 적당히 해야합니다.... 신선놀음은 금물...(-_-)..

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.