[W02] 퀴즈 정리

1. 다음 코드 실행 시 출력 결과를 작성하시오.

def message1():
    print("A")

def message2():
    print("B")

def message3():
    for i in range (3) :
        message2()
        print("C")
    message1()

message3()

>>>
B
C
B
C
B
C
A

2. 다음 코드의 출력 결과를 예측하고, 왜 그렇게 되는지 각각 설명하시오.

def modify(a, b, c):
    a += 1
    b.append(4)
    c = [100, 200] 

x = 10
y = [1, 2, 3]
z = [7, 8, 9]

modify(x, y, z)

print(x)  # (1)
print(y)  # (2)
print(z)  # (3)

(1) 10
:modify함수의 x값으로 10을 넣었지만 함수 안에있는 a와 밖의 x가 같은 변수가 아님.

modify함수를 정의하는 부분에서 a+1한 값을 a에 대입함.
a값에 x가 들어가고, x는 10이기때문에 x에 1을 더한 값인 11이 출력됨

(2) [1,2,3,4]
리스트에 요소를 더 추가하는 함수인 append()를 사용했기 때문에 기
존에 입력받았던 리스트인 [1,2,3]에 4가 추가된 [1,2,3,4] 형태가 출력 됨

(3) [7, 8, 9]
함수 안에 c가 가리키는 배열과 밖의 z는 같은 변수가 아니고 서로 다른 배열을 가리킴.
변수에 다른 값을 대입해도 바깥 변수는 변하지 않음.

3. 인덱스를 이용해서 배열의 특정 값을 읽을 때 시간 복잡도를 빅오 표기법으로 기입하라.  또한 정답의 이유를 설명하라.

O(1)
-> 배열은 메모리에 연속적으로 저장되기 때문에 인덱스를 이용하면 원하는 원소의 위치를 바로 계산해서 접근 가능하다
[빅오 표기법정리]

제출했던 오답: O(n) -> 값을 검색하는 경우, 순차 탐색을 해야하기 때문에 O(n)이 됨.

4. 다음의 코드는 팩토리얼을 구하는 재귀함수이다. 빈 칸을 채워 완성 하시오.

def factorial(n):
   if n <= 1:
       return 1
   return __________

n*factorial(n-1)

5. 웹 브라우저는 페이지를 이동할 때마다 ‘히스토리’에 기록한다. 이 히스토리는 어떤 자료구조로 구현하는 것이 적절한지, 이유와 함께 서술하시오.

제출했던 답: 연결리스트

히스토리를 따라 과거의 페이지로 이동을 하게 될 경우
현재페이지를 가리키고 있을때, 현재페이지가 가리키는 히스토리가 있을것이고
그 히스토리의 현재페이지가 가리키는 히스토리가 있을 것이고
... 이런 식으로 계속 이어질 것이다.

히스토리를 연결리스트로 기록해두면
연결리스트에서 노드의 data가 현재페이지, next가 히스토리가 되어서 노드의 next를 따라 이동하면 되기 때문에 연결리스트로 구현하는것이 적절하다고 생각했다.

찾아본 답: 스택
브라우저에서 뒤로가기 실행 시 가장 마지막에 방문했던 페이지부터 순서대로 이동함. 해당 방식은 스택의 LIFO방식과 일치하기 때문이다.

6.고정 크기 배열(예: 크기 10)만 사용하여, 요소를 이동시키지 않고 O(1)로 삽입/삭제가 가능한 큐를 설계한다면 어떻게 해야할까? 설계 방식을 설명하고 간단하게 파이썬 혹은 수도 코드로 enque, deque 함수를 만들어 보시오.

??? 링버퍼. 원형큐

7. 한 절에는 여러 명의 스님이 살고 있다. 병에 걸린 스님은 머리에 붉은 점이 생기며, 스님들은 매일 아침 한자리에 모여 서로의 얼굴을 볼 수 있지만 자신의 얼굴은 볼 수 없다. 어느 날 아침, 주지 스님이 모든 스님에게 “이 절에는 머리에 붉은 점이 있는 스님이 최소 한 명 이상 있다”고 말했다. 이 날을 0일차라고 하며, 그 이후로 병에 걸린 스님의 수는 변하지 않는다. 스님들은 매일 아침 서로의 머리를 확인하면서 자신이 병에 걸렸는지 논리적으로 판단한다. 어떤 스님이 자신의 머리에 붉은 점이 있다는 사실을 확실히 알게 되면, 그 스님은 다음 날 아침 모임에 나오지 않고 절을 떠난다. 그런데 1일차부터 6일차 아침까지는 아무도 절을 떠나지 않았다. 그러나 7일차 아침이 되자 머리에 붉은 점이 있던 스님들이 모두 동시에 절을 떠나 더 이상 보이지 않았다. 이때 머리에 붉은 점이 있던 스님은 몇 명이었는가? 또한 붉은 점이 있는 스님이 n명일 때, 모든 스님이 절을 떠나는 날을 반환하는 재귀 함수 departure_day(n)을 작성하라. (단, 주지 스님은 병에 걸리지 않았다.) 

1명일 경우 -> 첫날 확인했을때 본인 제외 점이없음 => 아 혹시 나임?

2명일 경우 -> 첫날 확인 : 한명있음, '난 정상이니까 저사람 나가겠네 ㅋㅋ'
          -> 둘째날 확인 : 안나가있음 => 아 그럼 혹시 나도임?
          
3명일 경우 -> 첫날 확인 : 본인제외 2명임 , '아 둘이 나가겠네 ㅋㅋ'
		  -> 둘째날 확인 : 아무도 안나가있음 -> ' 아 오늘은 나가겟지 ㅋㅋ'
          -> 셋째날 확인 : 아직도 안나감 -> ' 아 잠만 나도임?'
...
7명일 경우 => 동일한 방법으로 7일차에 모두 나감
∴ 붉은점 스님은 7명

def departure_day(n):
	if n==1:
    	return 1
        
     return departure_day(n-1)+1