티스토리 뷰
문제 풀이에 앞서,
안녕하세요. 깨뱌입니다.
5번 풀이를 안한줄 몰랐어요;; 왜 건너뛴지 스스로도 이해가 잘ㅠㅠ;;
(아마도 풀이과정이 길어서 다른것 부터 하고 올리려고 미루다가 까먹었나봐요ㅋㅋ)
아무튼 시작합니다~
문제
문5. C언어 함수로 구현된 <정렬 알고리즘>과 크기가 5인 배열 list를 이용하여 sort(list,5)를 수행하였다. <설명>에서 옳은 것만을 모두 고르면? (단, sort(list,5) 수행 전에 list 배열에 4, 9, 8, 6, 3이 순서대로 저장되어 있다.)
<정렬 알고리즘>
|
1
2
3
4
5
6
7
8
9
10
11
12
|
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int list[], int n)
{
int i, j, least, temp;
for(i = 0; i < n-1; i++)
{
least = i;
for(j = i+1; j < n; j++)
if(list[j] < list[least]) least=j;
SWAP(list[i], list[least], temp);
}
|
cs |
<설명>
|
ㄱ. sort(list,5)의 수행이 완료될 때까지 SWAP은 4회 수행된다. ㄴ. SWAP이 두 번째 수행된 후 배열 list에는 3,4,8,6,9가 순서대로 저장되어 있다. ㄷ. 정렬 알고리즘의 시간 복잡도를 빅세타(Θ) 표기법으로 표현한 겻은 Θ(nlogn)이다. |
① ㄱ
② ㄱ, ㄴ
③ ㄱ, ㄷ
④ ㄴ, ㄷ
풀이전 참고
* 시간복잡도 : 알고리즘이 수행되는 시간
* 공간복잡도 : 알고리즘을 수행하는 데 메모리를 얼마나 사용하는가
* 시간 복잡도 표기법
- 빅오 표기법 : 최악의 경우
- 빅오메가 표기법 : 최선의 경우
- 빅세타 표기법 : 빅오와 빅오메가의 평균
* 빅 O 표기법 (시간 복잡도가 빠른 순서대로)
O(logn) -> O(n) -> O(nlogn) -> O(n^2) -> O(n^3) -> O(2^n) -> O(n!)
1) O(1) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양과는 상관없이 항상 일정한 실행 시간을 갖는 알고리즘을 의미한다.
2) O(logn) : 이와 같은 성능을 갖는 알고리즘은 처리해야 할 데이터의 양이 증가할수록 실행시간도 약간씩 증가하는 알고리즘을 의미한다. 실행시간의 증가폭 자체가 logn의 그래프를 가지므로 급격하게 증가하지는 않는다. 일반적으로 효율이 좋은 검색 알고리즘의 성능이 이에 해당된다.
3) O(n) : 이런 성능을 갖는 알고리즘은 처리해야 할 데이터의 양과 비례하여 실행시간도 증가하는 경우이다. ex) for문
4) O(nlogn) : 처리해야할 데이터의 양에 비해 정비례보다 약간 더 증가하는 실행시간을 갖게된다. 일반적으로 효율이 좋은 정렬(sort) 알고리즘의 성능이 이에 해당된다.
5) O(n^2) : 이런 알고리즘은 2중 반복문을 의미한다. (중첩 for문) 이런 알고리즘은 처리해야 할 양이 증가하면 증가할수록 데이터의 제곱만큼의 실행시간이 소요되기때문에 좋은 알고리즘은 아니다.
6) O(n^3) : 이런 알고리즘은 3중 반복문을 의미한다. 처리해야 할 양이 세제곱만큼 증가한다. (최악)
7) O(2^n) : 이런 알고리즘은 데이터의 증가에 따라 2의 n승 만큼 실행시간이 증가하는 알고리즘이다. (최악)
풀이과정
ㄱ. 배열 요소가 5개로 보아 첫번째 for문이 5-1인 4만큼 반복되므로 SWAP 역시 4회 수행된다.
-> 맞는 지문
ㄴ. 순서대로 해본다.
list[] = {4, 9, 8, 6, 2, 3};
sort(list, 5);
1) for(i = 0; i < 4; i++) { // i = 0일 경우
least = 0
for(j = 1; j < 5; j++)
① j = 1 일 경우
if(list[1](값 : 9) < list[0](값 : 4) ) -> least=0 (변경없음)
② j = 2 일 경우
if(list[2](값 : 8) < list[0](값 : 4) ) -> least=0 (변경없음)
③ j = 3 일 경우
if(list[3](값 : 6) < list[0](값 : 4) ) -> least=0 (변경없음)
④ j = 4 일 경우
if(list[4](값 : 3) < list[0](값 : 4) ) -> least=4 (변경)
SWAP(list[0], list[least=4], temp) -> 1회
따라서, list[0]=3, list[4]=4
=> {3, 9, 8, 6, 4}
2) for(i = 0; i < 4; i++) { // i = 1 일 경우
least = 1
for(j = 2; j < 5; j++)
① j = 2 일 경우
if(list[2](값 : 8) < list[1](값 : 9) ) -> least=2 (변경)
② j = 3 일 경우
if(list[3](값 : 6) < list[2](값 : 8) ) -> least=3 (변경)
③ j = 4 일 경우
if(list[4](값 : 4) < list[0](값 : 6) ) -> least=4 (변경)
SWAP(list[1], list[least=4], temp) -> 2회
따라서, list[1]=4, list[4]=9
=> {3, 4, 8, 6, 9}
-> 맞는 지문
ㄷ. 이 문제의 경우 이중 for문이므로 빅세타 표기법으로 Θ(n^2)이 옳다.
-> 틀린 지문
마치며...
어후 오늘 포스팅이 좀 길었죠?
저도 틈틈이 몇일에 걸쳐 작성한 것 같네요..ㅠㅠ
이해 안가는 부분 있으시면 댓글 달아주시거나 메일 주시면 제가 아는 한 성심성의껏 대답해 드립니다~^^
항상 감사합니다.