어제 제 메일함을 열어보니 어떤 분이 Scheme 문제를 부탁하셨네요.

사실 저도 과제로 정신이 없어 풀 시간이 없었지만,

마침 어제 밤에 모든 과제를 마쳤기에 잠시 시간을 내어 풀어보았습니다.

총 3문제를 얘기하셨는데, 그 중 하나만 풀어봤습니다.

(사실 이 문제를 어디서 본 듯싶어서...^^;;;)

문제 3. Write a procedure, (make-collection-from-sets setA setB),

which returns an ordered list ("collection") containing

the elements from setA and setB.

Your procedure should run in linear time.

The sets are ordered list containing no duplicate elements within that set,

such as:

(define mySet1 (list 2 5 7 8 12)) (define mySet2 (list 1 3 5 8 9 13))

The two sets passed to make-collection-from-sets

may have elements in common.

In that case, both elements should appear in the collection.

For example, using mySet1 and mySet2 above:

(make-collection-from-sets mySet1 mySet2) => (1 2 3 5 5 7 8 8 9 12 13)

Note: This procedure will be similar to (set-diff setA setB) from lab 9.

linear time에 끝내야 하는군요.

하지만 저는 재귀로 풀었으니 linear time이 맞나요??

n이 1 증가할 때 해야 할 일이 2로 증가하고,

n이 2 증가할 때 해야 할 일이 4로 증가하는군요.

n이 3 증가할 때 해야 할 일이 6으로 증가하니 2n의 결과물이군요.

그럼 linear가 맞나요?

잘 모르겠습니다.

현재 알고리즘을 청강하고 있지만 말 그대로 청강인지라

다른 수업에 정신이 없어 점화식을 훈련하지 못했습니다.

이번 방학 때 훈련할 생각으로 수업을 듣는지라 아직 잘 모르겠습니다.OTL....

여튼 동작은 잘 하는군요.

결과물도 제대로 나왔습니다.

이번에 복학을 하여 SICP도 제대로 못 보고 있습니다.

그리고 실력도 낮아 도움을 제대로 드릴 수 없습니다.

이 점 양해바랍니다.

; make-collection-from-sets
(define (make-collection-from-sets set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((= (car set1) (car set2)) (cons (car set1) (make-collection-from-sets (cdr set1) set2)))
        ((< (car set1) (car set2)) (cons (car set1) (make-collection-from-sets (cdr set1) set2)))
        ((> (car set1) (car set2)) (cons (car set2) (make-collection-from-sets set1 (cdr set2))))
        (else (error "Cset1n't compset1re element in set"))))

; execute
(define mySet1 (list 2 5 7 8 12))
(define mySet2 (list 1 3 5 8 9 13))

;(make-collection-from-sets mySet1 mySet2) => (1 2 3 5 5 7 8 8 9 12 13)
(make-collection-from-sets mySet1 mySet2)

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.