【컴퓨터과학개론】종합 정리 기출문제 - 2

안녕하세요 【키보드 워리어】

 

⌨🗡🧑

블로그 방문자 여러분, 안경닦이입니다.

 

오늘은 지난 시간에 이어서 컴퓨터과학 개론 기출문제를 정리해보는 시간 가져보겠습니다.

 

기출문제 - 2

 

[05] 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관 없이 각 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택해서 결과적으로 전체적인 최적해를 얻는 전략을 사용하는 방법은?

 

보기 (1) 동적 프로그래밍 방법 (2) 욕심쟁이 방법 (3) 분할정복 방법 (4) 희귀 분석 방법

 

 

[정답]: 2번 

 

우리가 풀고자 하는 문제와 제반 조건이 매우 다양하기 때문에 모든 문제 혹은 대부분의 문제에 대해서 일반적으로 적용할 수 있는 알고리즘 설계 기법은 존재하지 않습니다.

 

 하지만 비교적 단순하면서 많은 문제에 사용가능 한 기법으로 분할 정복 방법,동적 프로그래밍 방법, 욕심쟁이 방법이 있어요.

 

이중 욕심쟁이 방법은 일련의 선택 과정을 통해 해를 찾는데, 전후 단계의 선택과는 상관없이 어떤 기준에 따라 각 과정마다 ‘가장 최고’라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 얻을 수 있을 것이라고 희망하는 방법으로, 욕심쟁이 방법이 문제에서 설명하고 있는 2번이 정답입니다.

 

※ 참고: 알고리즘의 설계

 

 

[06] 알고리즘의 성능을 나타내는 O – 표기 중에서 가장 효율적인 성능을 나타내는 것은?

 

보기        (1) O(n)   (2) O(n의2승)    (3) O(nlogn)    (4) O(logn)

 

[정답]: 4번

 

그림과 같이 왼쪽으로 오른쪽으로 갈수록 가장 성능이 좋은 것입니다. 상수시간은 데이터가 아무리 많아도 시간은 일정하며 문제를 해결하는 알고리즘을 만들었을 때 n의 표기로 어떤 것이 효율적인지 시간 복잡도 개념과 점근 성능 표기법으로 무엇이 효율적인지 알 수 있습니다.

 

※ 참고: 알고리즘 점근 성능의 표기법

 

 

 

[07] 퀵 정렬에 대한 설명을 올바른 것은?

 

보기 (1) 정렬된 두 서브리스트를 합병하여 하나의 정렬된 리스트를 형성한다.

        (2) 욕심쟁이 방법이 적용된 알고리즘이다.

        (3) 최악의 시간 복잡도는 O(n의2승)이다.

        (4) 주어진 리스트가 항상 동일한 크기의 두 서브 리스트로 분할된다.

 

[정답]: 3번

 

1번 >> 하나의 정렬된 리스트가 아닌 두 개의 서브리스르틀 정렬합니다.

2번 >> 분할 정복 방법이 적용됩니다.

4번 >> 주어진 리스트가 항상 동일하진 않습니다.

 

 

※ 참고: 퀵 정렬

 

 

 

 

[08] 포화 이진트리에 대한 설명으로 옳은 것은 무엇인가?

 

보기 (1) 모든 내부 노드들은 두 개의 자식 노드를 갖는다.

        (2) 트리 중에서 차수가 3개 이상인 트리를 의미한다.

        (3) 마지막 레벨 k에 노드가 모두 차 있지 않으며, 왼쪽부터 오른쪽으로 채워진 트리이다.

        (4) 모든 노드들이 왼쪽 또는 오른쪽의 한 가지로만 달려 있어 전체적으로 기울어진 직선 이진트리를 의미한다.

 

[정답]: 1번

 

2번 >> 트리 중에서 차수가 3개 이상인 트리를 의미한다.>>>2개 이상입니다.

3번 >> 마지막 레벨 K에 노드가 모두 차 있지 않으며(x), 왼쪽부터 오른쪽으로 채워진 트리리입니다.

4번 >> 경사 이진트리에 대한 설명입니다.

 

 

※ 참고: 특수한 조건을 가진 이진트리