해설 보기
정답인접한 두 원소를 비교·교환하며 큰 값을 뒤로 밀어내는 버블 정렬입니다.
핵심 개념
코드 패턴으로 정렬 알고리즘 식별하기 — 버블 정렬
정렬 알고리즘은 비교와 교환이 일어나는 위치만 봐도 종류를 구분할 수 있습니다. 제시된 함수는 안쪽 for 문에서 j를 1부터 i까지 늘려가며 바로 이웃한 두 원소 a[j-1]과 a[j]를 비교하고, 순서가 어긋나면 그 자리에서 곧바로 서로 교환합니다. 이렇게 인접한 쌍을 훑고 지나가면 안쪽 반복이 한 번 끝날 때마다 남은 구간의 최댓값이 뒤쪽 끝으로 밀려 확정되고, 바깥 for 문이 i를 size-1부터 1까지 줄이며 정렬 대상 범위를 한 칸씩 좁혀 갑니다. 이것이 전형적인 버블 정렬의 구조이며, 시간 복잡도는 평균과 최악 모두 O(n²)입니다.
선지별 해설
①삽입 정렬은 현재 원소를 temp에 보관한 뒤 이미 정렬된 앞 구간의 원소들을 뒤로 밀어내며 알맞은 자리에 끼워 넣는 코드가 나타납니다. 제시된 코드에는 그런 이동(shift) 과정이 없으므로 삽입 정렬이 아닙니다.
②선택 정렬은 남은 구간에서 최솟값의 인덱스를 찾아 변수에 기억해 두었다가 한 패스에 단 한 번만 교환합니다. 제시된 코드에는 최솟값 인덱스를 저장하는 변수가 없고 교환이 안쪽 루프 안에서 여러 번 일어나므로 다릅니다.
③힙 정렬은 배열을 힙으로 만든 뒤 루트와 마지막 원소를 교환하고 힙을 재구성하는 과정을 반복합니다. 부모·자식 인덱스 계산(2i, 2i+1 등)이나 재구성 함수가 전혀 없으므로 힙 정렬이 아닙니다.
④a[j-1] > a[j]일 때 두 값을 맞바꾸는 인접 원소 비교·교환 방식이고, 안쪽 루프가 한 번 끝날 때마다 최댓값이 뒤쪽에 확정되며 바깥 루프가 범위를 줄여 갑니다. 이는 버블 정렬의 정의 그대로입니다.
해설 보기
정답여덟 번째 push는 6 2 / 의 계산 결과인 3입니다.
핵심 개념
후위 표기식 변환과 스택을 이용한 계산 과정
중위 표기식 (4+2)/3+(6/2-1)을 후위 표기식으로 바꾸면 4 2 + 3 / 6 2 / 1 - + 가 됩니다. 후위식을 스택으로 계산할 때는 피연산자를 만나면 push하고, 연산자를 만나면 두 개를 pop해 계산한 뒤 그 결과를 다시 push합니다. 즉 연산 결과도 push 횟수에 포함된다는 점이 핵심입니다. 순서대로 보면 4(1), 2(2), 4+2=6(3), 3(4), 6/3=2(5), 6(6), 2(7), 6/2=3(8), 1(9), 3-1=2(10), 2+2=4(11)로 push가 일어나며, 최종 결과는 4입니다.