정보처리기사 필기 기본서 2024년 1권의 168페이지 선택정렬에 관한 내용입니다.
교재의 예제에서는 8 5 6 2 4를 정렬할 때 1회전의 결과가 2 8 6 5 4라고 나옵니다. 그러나 일반적으로 선택정렬이라고 하면 다음과 같이 동작합니다.
"첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째값과 스왑(1회전 완료), 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 값과 스왑(2회전)하는 과정을 반복하며 정렬을 수행한다."
즉, 하나의 회전에 스왑연산이 한번만 이루어집니다. 그러나 교재의 내용에 따르면 한 회전에 스왑연산이 여러번 수행될 수 있다는 것입니다. 선택정렬은 최솟값을 찾고 최솟값하고만 스왑이 이루어집니다. 따라서 교재의 예제에 1회전의 결과는 2 8 6 5 4가 아니라 2 5 6 8 4가 되어야합니다.
교재의 동작방식은 선택정렬과 버블정렬을 섞어놓은것처럼 동작하네요. 여러 자료와 알고리즘 서적등 어떤 자료를 봐도 최솟값을 찾고 1회전에 1번의 스왑만 이루어집니다. 답변바랍니다! 또한 교재의 기출문제를 모두 풀어보지는 않아 다른문제는 어떤지 모르겠으나 171페이지의 1번 문제의 경우 항상 최솟값이 선택된 인덱스의 바로 다음 인덱스이기 때문에 교재의 방법과 선택정렬의 방법대로 해도 3회전의 결과가 똑같지만 최솟값이 선택된 인덱스의 바로 다음인덱스가 아닌경우 반례가 발생하게 됩니다.
안녕하세요 길벗수험서 운영팀입니다.
오름차순 선택정렬을 구현하는 방법에는 두 가지가 있습니다.
1. 각 요소들을 비교해가며 자신보다 낮은 수가 있으면 바로 교체를 수행하여 최소값을 맨 앞에 위치시킴
2. 각 요소들을 비교해가며 최소값의 위치를 확인한 후 회전이 종료될 때 맨 앞의 요소와 저장된 위치의 값을 교체시킴
기존 정보처리기사, 산업기사, 기능사 기출문제에서 선택정렬의 각 회전에 대한 문제가 나왔을 때 주로 1번의 방법을 사용하여 해결하는 문제가 주로 출제되었습니다.
이점 염두에 두시고 말씀하신 2번 방법 외의 교재에서 설명하고 있는 1번 방법 또한 기억하여 문제를 푸는데 혼동을 겪지 않으시길 바랍니다.
행복한 하루되세요 :)
-
관리자2024-01-28 11:42:04
안녕하세요 길벗수험서 운영팀입니다.
오름차순 선택정렬을 구현하는 방법에는 두 가지가 있습니다.
1. 각 요소들을 비교해가며 자신보다 낮은 수가 있으면 바로 교체를 수행하여 최소값을 맨 앞에 위치시킴
2. 각 요소들을 비교해가며 최소값의 위치를 확인한 후 회전이 종료될 때 맨 앞의 요소와 저장된 위치의 값을 교체시킴
기존 정보처리기사, 산업기사, 기능사 기출문제에서 선택정렬의 각 회전에 대한 문제가 나왔을 때 주로 1번의 방법을 사용하여 해결하는 문제가 주로 출제되었습니다.
이점 염두에 두시고 말씀하신 2번 방법 외의 교재에서 설명하고 있는 1번 방법 또한 기억하여 문제를 푸는데 혼동을 겪지 않으시길 바랍니다.
행복한 하루되세요 :)