개념 한 쪽
코드 최적화 세트는 같은 결과를 내더라도 알고리즘과 자료구조 선택에 따라 실행 비용이 달라진다는 점을 묻는다. 정렬·검색 알고리즘의 동작과 시간복잡도, 해싱 충돌 해결이 중심이다.
이 개념을 문제로 확인하고 싶으면 이 개념 문제 10개 풀기 회원용
가입 없이 오늘의 10문제 바로 풀기 →
출제기준 단원 「코드 최적화」의 공개 문제 3개를 묻는 꼴별로 나누면 이렇습니다.
| 묻는 꼴 | 문제 수 | 무엇을 묻나 |
|---|---|---|
| 정렬 방식과 계산 | 1 | 인접 데이터 비교 정렬과 힙 정렬의 계산 |
| 성능 점검 도구 | 1 | 가상 사용자로 성능 목표를 확인하는 도구 |
| 최적화 개념 | 1 | 코드 개선과 자원 사용의 올바른 이해 |
힙 정렬은 배열을 힙이라는 자료구조로 구성해 가장 큰 값을 꺼내는 과정을 반복하는 정렬이다. 완전이진트리를 배열로 다룰 때 부모의 인덱스가 i이면 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2다. 삽입 정렬은 손에 든 카드를 정렬하듯 이미 정렬된 부분에서 제자리를 찾아 새 값을 끼워 넣는 방식이고, 버블 정렬은 인접한 두 데이터를 비교해 크기에 따라 위치를 바꾸는 방식이다.
힙 정렬의 시간복잡도는 입력 순서와 관계없이 최선·평균·최악 모두 O(n log n)이다. 성능 테스트는 가상의 사용자를 생성해 처리량, 응답시간, 경과시간, 자원사용률을 측정함으로써 성능 목표를 달성했는지 확인한다.
검색은 요소를 처음부터 하나씩 확인하는 선형 검색과, 정렬된 데이터에서 중간값을 비교해 범위를 반씩 줄이는 이진 검색으로 구분한다. 선형 검색은 순차 탐색이라는 동작 자체가 이름의 기준이며, 평균 검색 횟수는 (n+1)/2다. 이진 검색은 중간값을 비교해 범위를 절반씩 줄이는 방식이므로 피보나치 수열을 사용하지 않는다.
해싱은 키를 해시 함수로 바꿔 저장 위치를 정한다. 두 키가 같은 버킷을 가리켜 충돌하면, 선형 개방 주소법은 충돌이 난 자리의 다음 버킷, 그다음 버킷을 차례로 검사해 처음 나오는 빈 버킷에 데이터를 저장한다.
선지 판단은 힙 정렬의 시간복잡도를 모든 경우 O(n log n)으로 보는지, 완전이진트리 자식 인덱스 2i+1·2i+2를 적용하는지, 카드 정렬 비유를 삽입 정렬로, 인접한 두 데이터를 비교해 자리를 바꾸는 방식을 버블 정렬로, 순차 확인을 선형 검색으로 연결하는지, 선형 검색의 평균 검색 횟수를 (n+1)/2로 두는지, 이진 검색이 피보나치 수열을 쓰지 않는다고 판정하는지, 가상 사용자로 처리량·응답시간을 재는 테스트를 성능 테스트로 읽는지, 충돌 뒤 다음 버킷을 차례로 검사하는 방식을 선형 개방 주소법으로 고르는지에서 갈린다.
애플리케이션의 처리량, 응답시간, 경과시간, 자원사용률에 대해 가상의 사용자를 생성하고 테스트를 수행함으로써 성능 목표를 달성하였는지를 확인하는 테스트 자동화 도구는?
정답 ④ · 가상 사용자를 생성해 처리량, 응답시간 등 성능 지표를 확인하는 테스트 자동화 도구를 고르는 문제이다. 가상 사용자를 만들어 부하를 발생시키고 처리량, 응답시간, 경과시간, 자원사용률을 측정해 성능 목표 달성 여부를 확인하는 것은 성능 테스트 도구의 대표적인 기능이다.
가상 사용자를 생성하여 처리량, 응답시간 등을 측정하는 테스트는 성능 테스트이므로 성능 테스트 도구가 정답이다.
이진트리의 레코드 R=(88,74,63,55,37,25,33,19, 26,14,9)에 대하여 힙(heap) 정렬을 만들 때 37의 왼쪽과 오른쪽의 자노드(child node)의 값은?
정답 ④ · 주어진 11개의 레코드를 완전이진트리 형태로 구성한 후, 부모 노드가 자식 노드보다 크거나 같은 값을 가지도록 max heap(최대 힙) 정렬 과정을 거치게 됩니다. 과정을 거친 최종 힙 트리에서 값이 37인 노드의 위치를 찾아보면, 해당 노드는 맨 아래쪽 깊이(레벨 4)의 부모 노드 위치에 있습니다.
완전이진트리 배열 인덱스 i의 자식은 2i+1, 2i+2이므로 37의 자식은 14, 9이다.
This sort algorithm is likely to occur to anyone who has sorted cancelled checks or playing cards by simply holding them in the hand and inserting them one by one into the proper position in the stack or hand of already sorted items. What is this sort algorithm?
정답 ③ · 정렬된 카드 묶음에 새 항목을 하나씩 올바른 위치에 끼워 넣는 방식의 정렬 알고리즘 이름을 묻는 문제이다. 이미 정렬된 부분에 새 원소를 적절한 위치에 삽입하는 것이 삽입 정렬(Insertion sort)의 핵심 원리이며, 손안의 카드를 정리하는 비유는 삽입 정렬의 대표적 예시로 사용된다.
기존 정렬된 목록에 새 항목을 올바른 위치에 삽입하는 방식은 삽입 정렬(Insertion sort)의 핵심 원리이다.
정보처리기사 풀이 세트에서 이 개념의 문제 10개를 바로 풀어 보세요.