작성일 : 11-07-11 22:40
기하 알고리즘 강좌 질문 있습니다.
 글쓴이 : 황희선(h2sjolly)
조회 : 7,799  

선생님께서 두 선분의 교차여부를 판단하기 위해서
점이 모두 오른쪽에 있거나, 왼쪽에 있으면 교차하지 않는다고 하셨는데..

그 예제 문제에서는 10개의 선분이 교차하는 가짓수를 구하는 것이었는데요,
만약 3 개의 선분이 한 점에서 만난다면, 이것은 어떻게 판단하나요?

역시 수학공식을 써야 되는건가요?

이런것도 쉽게 판별하는 방법이 있을까요?'

답변 부탁드립니다 ㅠㅠ;;


황희선 11-07-11 22:43
 
선생님, 그리고 조언 하나 부탁드립니다 ㅠㅠ;;

전 예전에는 배열에 수를 입력받을 때에 0부터 처리해서 어려움을 겪었는데,
이제는 그래서 1부터 처리합니다...;;

하지만 두 가지 경우 모두 헷갈릴 때가 많은데,
어느 경우가 낳을까요..?

또한, 병합정렬 알고리즘을 사용하다 보니, n log_2 n이라 해도 이상하게도 많은 데이타를 처리 할 때에는 제 컴퓨터로 2초가량 걸렸습니다.

역시 stdlib.h헤더파일에 있는
qsort를 이용하는 것이 좋겠죠?

조언 부탁드립니다.
고맙습니다.
컴스쿨 11-07-12 17:31
 
어떤 문제를 말씀하시는건지 모르겠지만 평면내 직선의 교점 문제라면 문제에 "만약 중복되는 교점이 생기는 경우 각각의 교점으로 인정하고" 라는 전제가 있습니다. 만약 a,b,c 3개의 선분이 한점에서 만난다면 a와b, a와c, b와c 이렇게 3개의 교점이 생기는 겁니다.

배열에 수를 입력받을때 0부터 받는것이 좋은지 1부터 받는것이 좋은지는 그야말로 작성자의 선택입니다.
일반적으로 0부터 받는것이 여러가지 다양한 수식을 이용해 처리하기가 용이하지만 입력받는 수 자체가 입출력의 번호로 이용이 되거나 다이나막에서 0번은 아무것도 없을때의 초기값으로 사용하거나 하는 등의 필요에 의해 1번부터 사용하는 것이 편리한 경우도 많기 때문에 문제의 성격과 문제를 해결하기 위해 사용할 알고리즘 등에 따라 문제별로 알맞은 방법을 선택하는 것이 좋을거라 생각합니다.

qsort를 사용할 것인지 병합정렬을 사용할 것인지 역시 그때그때 자신의 판단으로 결정해야 하며 사실 두 알고리즘의 복잡도가 거의 비슷하기 때문에 대부분의 문제에서 별로 큰 이슈가 되지 못할거라 보입니다.
자신의 컴퓨터로 2초가 나오는건 채점컴퓨터의 성능을 믿으시고 별로 신경쓰지 않으셔도 될거 같습니다.
 
 

Total 635
번호 제   목 글쓴이 날짜 조회
55 올림피아드 강의 교재는 별도로 없는건지용~ (1) 한지민 08-27 8387
54 엑셀 완전초짜인데요 차트 만들기요..질문 (1) 정동명 08-25 8492
53 알고리즘 강좌 수강하고자 합니다. (1) 박수현 08-22 8830
52 알고리즘 강좌 신청합니다 (1) 이재성 07-13 7102
51 알고리즘 강의신청이요 (1) 김선미 07-13 6804
50 기하 알고리즘 강좌 질문 있습니다. (2) 황희선 07-11 7800
49 2008년도 정올 전국대회 초등부 3번문제 (1) 황희선 07-11 8092
48    2008년도 정올 전국대회 초등부 3번문제 (1) 컴스쿨 07-11 7864
47 2008년도 정올 전국대회 초등부 2번/중등부 1번 기출문제 (1) 황희선 07-10 7190
46    2008년도 정올 전국대회 초등부 2번/중등부 1번 기출문제 (4) 컴스쿨 07-11 10088
45 알고리즘 강의신청합니다~^^ (1) 황희선 07-10 6703
44 알고리즘 강의신청이요 (1) 김선미 07-08 6724
43 알고리즘 강의 신청 (1) 최현민 07-05 6692
42 교육신청과목어디서찾나요 (1) 안병태 06-29 6754
41 동영상 재생 (7) 김태경 06-28 6899
40 2006 전국 본선 1번 문제 (3) 금은실 06-27 7048
39 알고리듬 강의 신청 (1) 문일준 06-20 6858
38 알고리즘 강의 신처 (1) 이여진 06-15 7138
37 미디어 연결중 (2) 이수정 05-20 7585
36 Dyamic(동전 바꿔주기) (1) 김현수 05-19 13156
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30    

회사소개 | 개인정보처리방침 | 이용약관 | 찾아오시는 길 | 이메일주소 무단수집거부 | 사업자정보확인
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호 한컴에듀케이션(주) TEL : 031-388-8840 FAX : 031-388-0996
대표자 : 김동규 사업자번호 : 130-86-02870 통신판매업신고번호 : 제 2010-경기안양-888호
COPYTIGHT(C) 한컴에듀케이션(주), ALL RIGHT RESERVED.
담은강좌 : 0