PGR21.com
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
Date 2008/07/26 12:29:21
Name HL선샤인
Subject C언어 질문입니다. 도와주세요ㅠㅠ
계절학기 수업으로 컴퓨터공학 쪽 수업을 듣고 있는데;;(전공은 컴퓨터가 아닙니다.)

C언어를 이용하는 것이 과제로 나왔거든요.

제가 C언어를 공부 시작한지 아직 한달도 채 안되서 많이 헤매고 있습니다ㅠㅠ

zebra puzzle를 풀어내는 알고리즘을 구현하는 것인데요.

아..... zebra puzzle이 뭐냐면, 아마 보시면 많이들 아실텐데;





5명의 사람이 각각 다른 국적, 직업, 집색깔, 좋아하는 음료수, 애완동물을 가지고 연달아있는 5개의 집에 살고있다.

영국인은 빨간집에 산다.
스페인인은 개를 기른다.
일본인은 화가이다.
이탈리아인은 홍차를 마신다.
노르웨이인은 왼쪽에서 첫번째 집에 산다.
녹색집은 흰색집 바로 오른쪽에 있다.
사진사는 달팽이를 키운다.
외교관은 노란색집에 산다.
우유는 중앙에 위치한 집에서 마신다.
녹색집 주인은 커피를 마신다.
노르웨이인의 집은 파란색집 엎이다.
바이올리니스트는 오렌지쥬스를 마신다.
여우는 물리학자 옆집에서 키운다.
말은 외교관 옆집에서 키운다.

이 때 얼룩말을 기르는 사람과 암반수를 마시는 사람은 각각 누구인가?





이것입니다.

문제는 이미 제가 표를 그리면서 풀어서 답을 알고 있습니다.

이 조건들이 주어졌을 때 이 문제를 풀어내는 알고리즘을 구현하는 것입니다.

일단 제가 조금 생각은 해 봤는데, 집합의 개념을 주어서

{(국적),(직업),(집색깔),(음료수),(애완동물)}

꼴의 리스트를 전부 만든 다음, 조건이 입력되면 불가능한 경우를 삭제하는 식으로 해볼 생각인데요.

예를 들어서 첫번째 조건인 "영국인은 빨간집에 산다."가 주어지면,

{영국,(직업),(집색깔),(음료수),(애완동물)} 꼴의 집합과 {(국적),(직업),빨간집,(음료수),(애완동물)}의 집합의 교집합인

{영국,(직업),빨간집,(음료수),(애완동물)} 꼴만 남기고 나머지는 삭제하는 식으로 생각을 해봤습니다.

그런데 어떤 식으로 만들어야 할지 막막하네요ㅠㅠ

혹시 제가 생각한 방식 말고 더 좋은 알고리즘이 있으시면 좀 도와주세요^^

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
08/07/26 13:52
수정 아이콘
과목명이 알고리즘이라면 아마 이 문제는 backtracking으로 해결 하라는 의도같네요.
교재나 아래링크 참고하세요.

http://www.aistudy.co.kr/algorithm/design_park.htm#_bookmark_2f5a398
http://internet512.chonbuk.ac.kr/algorithm/20030506/default.htm#
08/07/26 17:55
수정 아이콘
언어도 막 배우신분께 쉽지는 않은 과제인 것 같은데요.
Memex님 말씀대로 기본적으로 backtracking으로 푸는 문제구요. 거기에 약간의 heuristic을 가미하면 됩니다.
참고로 prolog, scheme과 같은 선언적 프로그래밍 언어로는 매우 쉽게 푸는 문제입니다만... (거기서 힌트를 얻으셔도 되구요)
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
40005 모니터 교체후 옆쪽이 까맣게 잘리는현상 어떻게 해결해야되나요? [2] Jess:D1481 08/07/26 1481
40004 pgr에도 스크랩 기능이 있다면 좋겠어요. [8] 구름비2132 08/07/26 2132
40003 어머니와 성격이 너무 달라 자주 다툽니다.. [8] fomoser2138 08/07/26 2138
40002 임실치즈피자가 회사가 여럿이네요. [6] 포셀라나3119 08/07/26 3119
40001 가방 추천좀.. [1] funnyday2089 08/07/26 2089
40000 고대 근처에서 자취/하숙 하시는 pgr러 분들 계신가요? [11] 오뱅2735 08/07/26 2735
39999 워크래프트 질문입니다 [6] 날으는씨즈1648 08/07/26 1648
39998 태양의 여자 말이에요 [8] sunrise1993 08/07/26 1993
39997 모니터 질문좀요 [2] 솔직한사람1641 08/07/26 1641
39995 만화책 구입에 관해서.. [4] 랩교1924 08/07/26 1924
39994 가그린 [2] 라즈2171 08/07/26 2171
39993 C언어 질문입니다. 도와주세요ㅠㅠ [2] HL선샤인1883 08/07/26 1883
39991 급질입니다 오늘 롯데 야구 보러가는거에 대해서.. [4] Whut!1703 08/07/26 1703
39990 영화 추천 좀 부탁드립니다. [6] 호랑이잡자2114 08/07/26 2114
39989 컴퓨터 견적에 관한 질문(3) [1] Ex-sports1949 08/07/26 1949
39988 헬스관련 질문입니다. [6] 카시야신1888 08/07/26 1888
39987 여자친구의 헤어지자는 말.. [9] 여보야4290 08/07/26 4290
39985 잠실포차 여전히 영업하나요? [3] WhyYouKickMyDoG2135 08/07/26 2135
39984 아는여자애와 채팅중 질문 올려봅니다. [12] wAvElarva2787 08/07/26 2787
39982 여행 갈만한 곳 추천해 주세요!! [2] 신지용1586 08/07/26 1586
39981 교통관련 질문입니다. 앞차가 뒤차를 박았을 경우. [7] 밀가리2713 08/07/26 2713
39980 드랍핵에 대해 질문드립니다 [5] 축구사랑1850 08/07/26 1850
39979 컴활 자격증에 관해 질문드립니다~ [4] 테란의 횡재1878 08/07/26 1878
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로