2021년 3회 정보처리기사 기출문제 29번

29. 순서가 A, B, C, D로 정해진 입력 자료를 스택에 입력한 후 출력한 결과로 불가능한 것은?

① D, C, B, A     ② B, C, D, A

③ C, B, A, D     ❹ D, B, C, A

 

 

 

이 문제는 스택을 이용한 자료 구조 문제입니다. 순서대로 A, B, C, D를 스택에 입력한 후, 스택에서 꺼내는 출력 순서에 대해 가능한지 불가능한지를 묻고 있습니다. 스택은 후입선출(LIFO, Last In First Out) 방식으로 작동하는 자료구조입니다. 즉, 가장 나중에 들어간 자료가 가장 먼저 나옵니다.

문제 분석

입력 순서가 A, B, C, D라고 할 때, 이 순서대로 자료를 스택에 넣고, 그 이후에 스택에서 꺼내는 순서로 어떤 것이 가능한지 살펴보겠습니다.

1. 스택에 자료를 넣는 순서: A → B → C → D
2. 스택에서 자료를 꺼내는 순서: 후입선출 방식이기 때문에, 가장 마지막에 들어간 D가 가장 먼저 꺼내지고, 그 다음은 C, 그 다음 B, 마지막으로 A가 꺼내집니다.

각 선택지 분석

① D, C, B, A

• A, B, C, D가 스택에 들어간 후, D가 가장 먼저 꺼내지고, 그 후에 C, B, A가 차례로 꺼내지므로 가능한 출력 순서입니다.
• 결론: 가능.

② B, C, D, A

• A가 스택에 들어갔을 때, 스택에 있는 A를 먼저 꺼내야 하는데, 이 순서에서는 B가 먼저 나와야 하므로 불가능한 출력 순서입니다.
• 결론: 불가능.

③ C, B, A, D

• 스택에 A, B, C, D가 들어간 후, C가 먼저 나오고, 그 다음 B, A가 나오고 D가 마지막에 나와야 하는데, 스택에서 C가 나오는 순서는 불가능합니다.
• 스택에서는 C를 꺼내려면 D가 먼저 나와야 하기 때문입니다. 따라서 이 순서도 불가능합니다.
• 결론: 불가능.

④ D, B, C, A

• D가 먼저 나오고, 그 다음 B가 나오고, C와 A가 차례로 나오게 되면, 이는 스택에서 가능한 출력 순서입니다.
• 결론: 가능.

결론

불가능한 출력 순서는 ② B, C, D, A입니다.

추가 설명

스택의 특성을 이해하는 것이 중요합니다. 자료를 넣는 순서와 자료를 꺼내는 순서가 서로 맞지 않으면, 출력 순서는 불가능합니다. 스택은 항상 가장 마지막에 들어간 자료부터 꺼내기 때문에, 특정 순서로 출력을 하려면 그에 맞는 순서대로 스택에서 꺼낼 수 있도록 들어가야 합니다.