정보처리기사 자료구조와 알고리즘 핵심정리

스택은 접시를 쌓는 것과 같아서 맨 위(나중에 올린 것)부터 꺼냅니다. 함수 호출, 되돌리기(Undo), 괄호 검사에 쓰입니다.

틀린 선지

• ① 먼저 넣은 자료가 먼저 나오는 선입선출(FIFO) 구조이다.: 큐의 설명입니다.
• ③ 양쪽 끝에서 모두 넣고 뺄 수 있다.: 데크(Deque)의 설명입니다.
• ④ 운영체제의 작업 스케줄링에 주로 쓰인다.: 큐의 쓰임새입니다.

1. 뿌리 A 를 방문
2. 왼쪽 서브트리(B)로: B 방문 → B 의 왼쪽 D → B 의 오른쪽 E
3. 오른쪽 서브트리 C 방문
4. 결과: A B D E C

틀린 선지

• ② D B E A C: 중위 순회(왼쪽 → 뿌리 → 오른쪽)의 결과입니다.
• ③ D E B C A: 후위 순회(왼쪽 → 오른쪽 → 뿌리)의 결과입니다.
• ④ A B C D E: 위에서부터 한 층씩 읽은 레벨 순회의 결과입니다.

이웃한 두 값을 앞에서부터 차례로 비교합니다.

1. 5 와 3 비교 → 바꿈 → [3, 5, 8, 1]
2. 5 와 8 비교 → 그대로 → [3, 5, 8, 1]
3. 8 과 1 비교 → 바꿈 → [3, 5, 1, 8]

1회전이 끝나면 가장 큰 값(8)이 맨 뒤에 놓입니다.

틀린 선지

• ① [3, 5, 8, 1]: 첫 번째 비교만 한 결과입니다.
• ② [1, 3, 5, 8]: 정렬이 모두 끝난 결과입니다.
• ④ [1, 5, 3, 8]: 선택 정렬 1회전의 결과입니다.

삽입 정렬은 평균 O(n²)입니다. 자료가 이미 거의 정렬되어 있을 때만 O(n)으로 빨라집니다.

틀린 선지

• ① 퀵 정렬: 평균 O(n log n)입니다. 다만 최악의 경우에는 O(n²)입니다.
• ② 병합(합병) 정렬: 언제나 O(n log n)입니다.
• ③ 힙 정렬: 언제나 O(n log n)입니다.

1. 3 을 넣음 → [3]
2. 4 를 넣음 → [3, 4]
3. + 를 만남 → 3 + 4 = 7 → [7]
4. 5 를 넣음 → [7, 5]
5. * 를 만남 → 7 × 5 = 35

일반 식으로 바꾸면 (3 + 4) × 5 입니다.

틀린 선지

• ① 17: 3 × 4 + 5 로 계산한 값입니다.
• ② 23: 3 + 4 × 5 로 계산한 값입니다.
• ④ 60: 세 수를 모두 곱한 값입니다.