[gratus907]

안녕하세요. 챌린지 문제 해결 과정에서 여쭈어 볼 점이 있어 질문 드립니다.
주어진 문제의 motivation이 Garbage collection에 있지만, 실제 문항에서는 어떤 rooted graph를 입력으로 받아서, 루트 노드로부터 방문할 수 있는 모든 노드를 마킹하되 이 과정에서 노드당 2비트 이상의 메모리를 사용하지 않는 알고리즘을 고안하는 것만을 요구하는 것으로 보입니다.

(질문 1) 이 경우, motivation과는 무관하게 graph가 어떤 방법으로 잘 들어온다고 가정한 상태로 알고리즘을 고안하고 pseudo-code 로 작성하면 되나요? 아니면, 실제로 GC를 작성해 보았던 SM-5를 기준으로 생각해서 작성해야 하나요?

(질문 2) 만약 질문 1에 대한 답이 알고리즘만 고안하고 작성해도 좋다는 것이면, Garbage collection이라는 원래의 상황과 무관하게 Graph가 adjacent list 또는 adjacent matrix 형태로 주어진다고 가정하고 C나 JAVA 같은 언어를 이용해서 알고리즘을 구현하는 상황을 가정해도 되나요? 즉, 가상의 언어로 작성한 Pseudo-code 에서 가상의 언어가 K나 SM-5 같은 언어여야 하는지, 아니면 C언어 코드처럼 작성해도 되는지 궁금합니다.

(질문 3) 질문 2에 대한 대답이 그렇게 해도 되는 것이라면, 정의한 언어의 Specification을 따로 첨부해야 하는지 (숙제 문서처럼), 아니면 그냥 Pseudo-code 라는 말의 원래 뜻 그대로 (예를 들어 아래 예시와 같이) 사람이 읽을 수 있는 수준에서 작성해도 되는지 궁금합니다.

[조민기]

챌린지 채점은 교수님께서 하셔서 제가 확답을 드리기는 어려운 점 양해 바랍니다.

(질문 1과 2 - 인풋의 형식)
그래프가 인풋으로 주어질 때로 가정하시면 될 것 같습니다. 다만 이에 대한 언급을 간략하게라도 적어주셔야 할 것 같습니다. 예를 들어 그래프가 무엇에 해당하는 것이고 알고리즘의 아웃풋이 무엇인지 적어주시면 좋겠습니다.
adjacent matrix가 주어진다고 가정하는 것은 문제의 취지(그래프의 노드 개수에 비례하는 메모리가 더 필요한 점을 피하려는 것)와 맞지 않는 듯합니다. 반면 adjacent list가 주어진다고 가정하는 것은 괜찮아 보입니다.

(질문 2와 3 - pseudo code의 형태)
사람이 읽기 편한 가상의 언어를 사용하시면 될 것 같고 그 언어의 정의를 적으실 필요는 없을 듯합니다. C나 Java 같은 imperative style의 pseudo code를 작성하셔도 무방할 것 같습니다. 다만 특정 언어에 특징적인 개념은 피하셨으면 합니다.

보통 pseudo code에 많이 쓰이는 assign, array를 비롯한 자료구조, for나 while loop, 수학 연산자들, 함수 정의, 그리고 함수형 언어의 let binding이나 lambda expression 정도는 모두 설명 없이 사용해도 될 것 같습니다.

[gratus907]

감사합니다~!!