현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

[완료]컴공 꼬꼬마가 선배님들께 여쭙니다.

ksl6424의 이미지
글쓴이: ksl6424 / 작성시간: 월, 2010/11/22 - 9:27오후

안녕하세요! 4년제 컴공 2학년을 다니고 있는 꼬꼬마입니다.
여기저기 열심히 찾아봤지만 성과가 없어 선배님들의 작은 관심이 필요해 왔습니다.
자료구조를 충분히 이용한 프로그램을 만드는 프로젝트인데
저희는 구조체와 트리를 이용해 여행친구찾기 프로그램을 만드려합니다. (B트리, AVL트리는 안배웠고 그냥 트리이용할 생각입니다.)
가장 메인 기능이 "조건검색"인데요. 같은 목적지나 같은 연령대를 검색할수있게 하려고 머리를 쥐어짜서
첨부한 그림같은 노드가 나오게 되었는데요.
이름, 목적지, 연령대는 조건검색을 위해 KEY값으로 쓰려고 노드에 포함시켰고,
나머지 검색에 쓰이지 않는 정보들(프로필,취미,학교)등은 주소를 저장해 원하면 가져올수 있게...하는게 제 의도인데..
과연 이게 말이되는것인지,구현가능한건지 선배님들께 여쭙고자 글올립니다.
아님 더 좋은 방법이 있을까요? 조언부탁드립니다.

File attachments: 
첨부파일 크기
Image icon node.jpg46.91 KB
Forums: 
프로그래밍 QnA
kaeri17의 이미지

글쓴이: kaeri17 / 작성시간: 화, 2010/11/23 - 8:36오전

KEY값으로 이름, 목적지, 연령대를 다 쓰는 건가요? 그러면 결국 모든 조건을 같이 검색할때만 유용합니다. 제생각엔 일단 가장 많이 쓰이는 key값으로 hash-set을 만들어 저장하고 이렇게 저장된 데이터를 binary트리를 이용해 인덱스를 만드는 편이 제일 나을 듯 하네요. 즉 key를 나눠서 이름을 key값으로 가지는 binary트리 하나 목적지를 key로 가지는거 하나 뭐 이런 식으로요.

ksl6424의 이미지

글쓴이: ksl6424 / 작성시간: 화, 2010/11/23 - 11:01오후

그렇군요. 굳이 노드에 다 때려박지 않아도 되는거였네요. 정말 감사합니다. 큰 도움이 됬습니다^^;
그런데 말씀하신 이름을 key값으로 가지는 트리하나 목적지를 key값으로 가지는 트리하나 이런식으로 하라는 말씀은
검색조건 갯수만큼의 트리를 생성하라는 말씀이신가요? 이렇게 만들었을때의 용량차지는 어쩔수없는거겠죠?

rgbi3307의 이미지

글쓴이: rgbi3307 / 작성시간: 화, 2010/11/23 - 10:29오전

아래와 같이 이름,목적지,연령대,프로필,취미,학교를 하나의 DATA 구조체로 선언하고,
이것을 메모리할당한 포인터를 NODE구조체의 void* data에 연결한후,
이진탐색트리(BST) 구조체에 연결해 나가면 될듯합니다.
이때 트리의 연결방향(왼쪽,오른쪽)은 BST 구조체에 있는 (*compare) 함수에 전달되는
매개변수값(키값:이름이나,목적지...)의 비교에 따라서 정해지도록 하면 될듯하네요.

//데이터 구조체 선언
typedef struct data {
	이름,
	목적지,
	연령대,
	프로필,
	취미,
	학교
} DATA;
 
//노드 선언
typedef struct node
{
	struct node*	left;
	void*		data;	
	struct node*	right;
} NODE;
 
//이진탐색트리 선언
typedef struct tree
{
	int	count;  //노드수
	int	(*compare) (void* argu1, void* argu2);
	NODE*	root;
} BST;

처음 발제하신 문제를 해결하기 위해서 여러가지 방법이 있을 수 있습니다.
위의 구조체는 Binary Search Tree(BST)로 구현할때 이런 형태가 된다는 것이구요,
바로 위에서 kaeri17님이 언급하신 것처럼,
키값들로 해시값을 산출하여 해시테이블에 저장한 곳에서
Linked List나 트리로 분기하도록 하는 방법도 아주 좋을듯합니다.
BST는 단점이 있는데, DATA의 수가 늘어날수록 트리의 깊이도 크지기 때문에,
트리를 균형잡히도록 하여 트리 깊이를 줄여서 알고리즘 효율성을 높여주는 방향으로
설계한 것이 AVL Tree, Red-Black Tree, Btree 입니다.
이들은 대용량의 자료를 처리하고자할때 알아두면 좋을듯합니다.

From 알지비(rgbi3307(at)nate.com) in the www.kernel.bz

From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))

ksl6424의 이미지

글쓴이: ksl6424 / 작성시간: 화, 2010/11/23 - 11:03오후

코드까지 직접.. 감동입니다!
친절한 답변 감사하구요. 이제 머리싸매고 만들어봐야겠네요.
팀프로젝트를 떠나서 조언해주신것 공부해봐야겠습니다.

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.