TIS-100 NO_MEMORY 도전 과제 공략

https://foxtrotin.tistory.com/206

TIS-100 SEQUENCE REVERSER (SEGMENT 42656) 공략

이 문제를 스택을 쓰지 않고 푸는 도전과제다

도전 과제 달성률이 2.4%로 처참해서 도전 정신을 불러일으킴ㅋㅋ

 

1. 0이 들어오기 전까지 값을 받는다

2. 들어온 값을 반대로 출력한다

이걸 스택을 쓰지 않고 하는 방법은 뭐가 있을까?

 

입력값이 5개를 넘는 케이스가 없는 것 같은데, 각 BAK마다 값을 넣어뒀다가

0이 들어오면 BAK에서 하나씩 뽑아 넘기는 방법으로 하면 될 것 같다

 

그러면 각 노드마다 해야 할 일은

[첫 노드]

1. 입력 받는다

2. 0이면 0과 -1을 보낸다 (0은 출력하세요, -1은 출력 끝을 의미)

3. 0이 아니면 값을 보낸다

 

[중간노드]

1. 값을 받는다

2. 0이 아니면 내 BAK이 0인지 본다. 0이면 print로 분기한다

3. BAK값이 0이면 내 BAK값에 현재 값을 넣는다

4. 내 BAK값이 이미 찼으면 다음 노드에 값을 넘긴다

5. print로 분기했으면 현재 값 0을 다음 노드로 넘겨서 출력하라고 전달한다. 그리고 BAK값을 꺼내서 다음 노드로 넘긴다

6. BAK값을 꺼내서 넘긴 다음에 오른쪽에서 값을 하나 더 받는다(-1을 꺼내옴) -1이 들어오면 다음 노드에 -1신호를 보내고(출력 끝이라고 전달) 자기는 다시 1번으로 돌아간다

 

[끝 노드]

1. 값을 받는다

2. -1이면 0을 출력하고 끝낸다

3. 0이면 0값이 올 때까지 계속 값을 받아서 출력한다

 

이게 가능한 이유는, 노드에서 MOV명령어를 쓰면

값이 올 때까지, 혹은 값을 받아갈 때까지 계속 대기 상태로 있는 특성이 있기 때문이다

그래서 이런 일이 벌어진다

PRINT아래 L: MOV ACC, DOWN이 자기 BAK값을 넘기는 건데

그 다음 노드도 다음 노드한테 자기 BAK값을 넘기고 그 다음 노드도 자기 BAK값을 넘기고..

그러면 서로 받아라->받아라->받아라 상태가 되기 때문에

마지막 노드가 받아서 출력해주기 전까지 언제 받아.. 하면서 기다리고 있다

 

이거 전에 스택으로 풀 때도 출력이 끝났다는 신호가 올 때까지 대기하고 있었는데 (MOV RIGHT, NIL) 같은 원리다

 

어셈에서는 재귀적인 접근을 이렇게 하는 구나 알았던 문제였음