http://sscc.ssu.ac.kr/zboard4/zboard.php?id=study_34&page=1&sn1=&divpage=1&sn=off&ss=on&sc=on&select_arrange=headnum&desc=asc&no=25
그림출처 : 기사79 (http://www.gisa79.com)
해설출처 : 18기 신성진 본인
퍼갈때는 반드시 출처를 밝히고 퍼가세요.
시인들의 배움터 종강후 처음 쓰는 게시물이군..
내가 왠만하면 이런거 더이상 하고 싶진 않다만.. -_-
다른것도 아니고 내가 직접 시험본거고 내가 이렇게 풀었기 때문에 써 본다..
먼저, 이 게시판에 맞게 여기 내용에 맞춰 알고리즘을 보겠다.
시험문제 : Insertion Sort 오름차순
우리는 Insertion Sort 가 어떤 방식으로 구현되는지를 모른다는 가정하에 푼다.
단, Sort가 무엇을 뜻하는지는 안다고 가정하고.
순서도는 위의 그림을 참고 바란다.
문제 푸는 것은 (1)~(5) 까지 들어갈 내용을 쓰는거고.
AR : 30개의 값을 가진 배열이고, 정렬안된 데이터가 들어있다.
KEY, W, M : 임시 변수값
자, 그럼 이제 이걸 어떻게 풀었느냐.
여기에서는 쓸데없이 소트를 위해서 여러번 반복해서 푸는 방식이 아니라
소트를 딱 한번만 하는 데에도 답이 나오는 방식으로 한다.
순서도를 잘 봐라.
분기문에서 "Yes"가 나오면 위로 올라가지?
그렇다면 이건 분기문이 아니라 "반복문"이다. 즉, For문 등으로 활용이 가능하다는 거지.
그렇다면 반복문의 변수는 어떻게 들어가는가?
먼저 중간의 분기문에서 "Yes"위로 올라가는 것은 바로 위에 "W=W-1"이 있다.
그렇다면.. 분기문의 "Yes"가 가리키는 화살표에서부터 분기문까지 반복을 하겠다는 소리고,
해당 반복에 대한 변수값의 증감은 "W=W-1"로 표현이 가능하다는거지.
즉, 이를 표현하기 가장 좋은 반복문은 무엇일까?
바로 do-while이다.
do {
...
w=w-1;
} while(4번의 분기문)
로 표현이 가능하다는것.
근데 이 사이에 또 분기문이 있지? 이를 표현하면 아래와 같이 세련되게 나온다.
do {
if(key >= AR(W)) // 사이의 분기문에 대한 반대의 조건 부여
break;
[3번의 Expression]
w=w-1;
} while(4번의 분기문)
그럼 이제 아래의 분기문을 보자.
"M<=30"이라고 되어있지?
이 역시 do-while로 표현이 가능하다.
do {
...
m=m+1;
} while(m<=30)
자, 그럼 2개를 do-while로 표현하면 대충 감이 오는가?
그러므로 아래에서는 (4) 분기문과 M<=30 분기문을 반복문으로 명명해서 칭하겠다.
위에서 말했듯이, 30개의 값을 가진 배열이고.
이를 수행하기 위해서 30번 정도 반복한다라는 것을 추측할 수 있을 것이여.
그렇다면 여기서 (1)번을 푸는 방법이 대충 눈에 보인다.
(1)번은 위의 M<=30 의 반복문 밖에 있는 내용이기 때문에,
(1)에 들어갈 내용은 당연히 M에 대한 초기값을 설정해야 한다.
초기값을 설정하려면 값이 무엇이 들어가야 될까?
바로 M=숫자, 변수, 수식 세가지가 들어간다.
먼저 변수를 대입했을때를 보자.
밑에서도 봤듯이 M=M+1 이라고 되어있으니까 M의 값은 증가하는 구조고.
그리고 다른 변수도 안된다. 왜냐하면, M<=30 반복문 밖에서 초기화를 하는 변수이기 때문에
초기화를 할때의 변수삽입은 다른 정해진 값을 넣어야 한다.
근데 다른 초기화된 변수는? AR 배열변수밖에 없다.
만약 M=AR(1) 등으로 초기화를 한다고 해봐라.
그러면 밑에서 M=M+1 을 할 경우에 M의 값이 증가하는데,
이것은 즉, 나중에 써먹게 된다면 AR 배열의 값을 바꾸는데 쓸 수가 있을 것이다.
근데 이건 배열값을 임의로 조작하는게 아니라 배열 내부의 위치를 바꾸는 문제란 말이다.
그러므로 탈락.
다음은 수식이다.
초기화가 이미 된걸 가지고 수식을 하거나 숫자 가지고 해야 하는데.
M=1+2.. 그런 쓸데없는 초기화는 먼저 말이 안된다.
M=변수+숫자.. 변수 자체가 안되는데 뭐 어쩌라고..
M=변수+변수.. 더더욱 말이 안된다.
이건 덧셈뿐 아니라 가감승제나머지도 똑같이 적용된다.
다음은 숫자이다.
소트를 하기 위한 기본 원칙을 상기해보자.
소트는 말그대로 정렬하는 것이기 때문에, 기본 원칙은 바로 두개의 값에 대한 비교가 근본이다.
AR(1) AR(2) AR(3) ... 의 배열이 있다고 하자.
그러면 위에서 언급했듯이 AR 배열 빼고는 초기화된 변수가 아무것도 없다.
그러면 M=AR(1) 등이 아니라면 당연히 M이 써먹을 데는 AR 배열의 인자값 외에는 들어갈게 없다고
상상을 할수가 있는데, M이 1이면 당연히 AR(1)을 바로 떠올릴 수 있을 것이다.
이런 식으로 따지면 인자값은 당연히 정수가 되겠고.
그런데, 시험에서는 배열을 표현할때 먼저 선행사항이 있는데,
이는 AR배열의 첫번째 값은 C언어와 같이 AR[0] 이 아니라, AR(1)로 표기하도록 규칙이 정해져있다.
(거기서 정한 규칙이야 따지지 마.. 수도코드와 같이 판단하면 돼)
그렇다면 최소한 M=0 이하로는 절대 답이 될수 없다는 것은 유추할 수 있을 것이다.
(0 이하로 나와서 뭐 어쩔건데.. NULL 값 쓸라구?)
그럼 이제 M의 값을 1부터 하나씩 넣어보자.
M=1이면 비교를 할 때 AR(M) 과 AR(2) 를 비교함
M=2이면 비교를 할 때 AR(1) 과 AR(M)을 비교함
M=3 이상의 값이 나와버린다면 비교는 값 2개를 가지고 하는데 처음값부터 비교를 한다는게 불가능하다.
(왜 처음부터 비교하냐고? 지금 초기화를 하는 위치이다. 그걸 명심해라.)
근데 M이 3이면 AR(2) 와 M(AR(3)) 을 비교하거나, AR(1) M(AR(3)) 을 비교하는데,
전자의 경우는 AR(1)은 뭐고 후자의 경우는 AR(2)는 대체 어디다 쓰란 말인가?
말이 안된다.
그러므로 M의 값은 1 혹은 2가 나온다.
일단 여기까지 이레짐작하고 다음을 넘어가자.
다음을 넘어가니까 M<=30 의 반복문 안으로 들어왔다.
그러면
do {
...
} while(M<=30)
에서 "..." 의 첫번째 내용이란 말이여.
"KEY=AR(M)" 이라고 되어있지?
그렇다면 이 "KEY"는 뭐하는 변수일까?
뭔지는 몰라도 짐작이 될 것이다. 바로 Insertion Sort를 하기 위해서 사용되는 키값이라는 것을.
그렇다면 이 KEY 값을 어떻게 굴리느냐를 한번쯤 고민해보면서. 다음.
"W=(2)"라고 되어있다.
그렇다면 (2)가 무엇이 나올지 당장은 모르더라도, "W"가 KEY와 비교될 값이라고 짐작할 수 있다.
아니나 다를까. 바로 아래에
"KEY < AR(W)" 라는 분기문이 바로나온다.
그리고 그 사이에 (4)에 대한 반복문 화살표가 나왔고.
그렇다면 KEY와 W가 무슨 변수인지는 몰라도 어떤 값의 범위가 들어가는지는 알 수 있다.
KEY=AR(M)에서 KEY는 배열의 값이 나오는 것이고,
KEY
자, 그럼 KEY와 W의 범위를 알았으니 W를 구해볼까?
먼저 KEY
왜냐면, Insertion Sort 배열 내의 값이 처음부터 오름차순-내림차순으로 될수도 있지만,
그런 경우에만 풀라고 내놓은 문제가 절대로 아니기 때문에,
KEY
그럼 Yes로 하고 내려가보자.
(3)이 뭔지는 모른다. 하지만 W=어쩌구저쩌구 이런 식의 표현은 절대 아니라는걸 알 수 있다.
바로 밑에 W=W-1이 있는데, (3)이 W의 값을 대입하는 식의 표현이 나온다면
그것은 똑바로 된 순서도도 아닐뿐더러 말그대로 잘못그린거다.
(왜냐하면 그냥 순서도가 아니라 "알고리즘"을 만드는 순서도기 때문에. 항상 최적화된 내용을 넣어야지)
그러면 W의 값이 뭔지는 몰라도 1 이하로는 절대로 나올수 없다는 것을 추측할 수 있다.
위의 분기문에서 봤듯이 AR(W)면 W는 AR 배열의 인자값으로 쓰이는 변수인데,
시험에서는 앞에 언급했드시 배열은 1부터 시작하니까.
W=1이면 W=W-1 하면 0이 되어버린다. 그러면 되겠나 안되겠나? 당연히 넌센스다.
그렇기 때문에 뭔지는 몰라도 1 밑으로 나올 수는 없다.
그럼 W=2일때를 보자. 그리고 밑의 분기문을 보자.
처음 비교시 W=2 라고 하고 뜬금없이 KEY < AR(2) 가 나오나? 그럼 AR(1)은 어쩔건데..
하물여 W가 2보다 큰값이면 더하면 더하지 덜하진 않다.
그러므로 W는 배열의 인자값이지만 절대로 숫자가 나올 수 없다.
그 대신 수식이나 변수가 들어갈 수 있다.
우리는 앞서서 KEY, M, W에 대한 값의 범위를 이미 구했다.
M : AR 배열의 인자값
KEY : AR 배열의 값
W : AR 배열의 인자값
그렇다면 W라는 값은 M이거나 M과 관련된 수식이 나온다.
왜냐, W는 숫자는 못들어가고 변수나 변수 수식이 나와야 하는데,
KEY는 배열값이기 때문에 Match가 안되고 배열 인자값이 M이 매치가 되기 때문이다.
그러면 여기까지 (1), (2) 값의 추측이 가능하다.
(1) : M=1 , M=2
(2) : W=M 혹은 M이 들어간 수식
자.. 이제 여기부터가 하이라이트다.
다시 한번 (2)의 W를 보자. 그리고 (1)의 M을 보자.
M=1이면 비교를 할 때 AR(M) 과 AR(2) 를 비교함
M=2이면 비교를 할 때 AR(1) 과 AR(M)을 비교함
그럼 소트의 기본원칙인 두 수의 비교는 어디에 들어가야 할까?
당연히 (3)에 들어갈 수밖에 없다. Expression이 거기 하나밖에 없으니까.
근데 W=M이면 어떻게 될까? AR(M)과 AR(W)도 같은 수이다. 비교가 되나? 안된다.
그러므로 W=M-1 혹은 W=M+1 이 나와야 한다.
그러므로 아래 식은 다음과 같이 바꿀 수 있다.
M=1, W=M+1이면 비교를 할 때 AR(M) 과 AR(W)를 비교함
M=2, W=M-1이면 비교를 할 때 AR(W) 과 AR(M)을 비교함
자.. 다시 원론적 이야기로 넘어가자.
우리가 흔히 알고 있는 소트는 두 수를 비교해서 아니다 싶으면 위치를 바꿔버리는거다.
위치를 바꾸는 기본공식은 무엇인가?
TMP = A;
A = B;
B = TMP;
그러면 Expression 3개, 변수 3개가 들어간다.
근데 여기 (4) 반복문을 보자.
W=W-1. Expression이다. 근데 이게 위의 위치 바꾸는 공식에 해당하는 Expression인가? 아니다.
그렇다면 실제 Expression은 (3) 한개이다.
그리고 사용되는 변수는 KEY 변수와 AR 배열 내의 여러 가지 변수이다.
그렇다면 위의 Exchange를 위한 Expression 3개, 변수 3개의 조건을 절대 만족 못시킨다.
즉, Exchange를 이용한 Sort가 절대 아니라는 것이다.
그럼 어떻게 할까? 잘 생각해보자.
강조하지만 헷갈리면 안된다. Sort의 기본원칙이 두 수를 비교하라는 거지 Exchange 하는거는 선택옵션일 뿐이라는걸.
위에 나온
M=1, W=M+1이면 비교를 할 때 AR(M) 과 AR(W)를 비교함
M=2, W=M-1이면 비교를 할 때 AR(W) 과 AR(M)을 비교함
는 말그대로 비교이지, 치환하라는 소리가 절대 아니다.
그럼 어떻게 할까?
KEY를 보자.
먼저 위에서 KEY=AR(M)으로 초기화를 시켰다.
그러면 AR(M)의 값은 이미 임시값으로 빼돌렸다는 소리다.
그러면 어떨까? AR(M)의 값은 죽이되든 밥이되든 나몰라라 해도 된다.
물론 그 범위는 "두 수를 비교하고 이를 이용해서 여러가지 연산을 하고." 의 (4) 분기문, (5)=KEY 범위 내이고.
(범위가 왜그런지까지는 말하지 않겠음.)
그러면 이를 잘 활용하면 조금씩 보일 것이다.
즉, AR(M)은 임시값인 KEY로 빼돌렸으므로, AR(M)을 임의대로 조작해도 된다.
그렇다면
M=1, W=M+1이면 비교를 할 때 AR(M) 과 AR(W)를 비교함
M=2, W=M-1이면 비교를 할 때 AR(W) 과 AR(M)을 비교함
여기에서 AR(M) 은 임의 조작 가능 값이므로, 어떻게 해야 할까? 치환도 안된다고 하는데..
바로 복사를 하는거다.
즉, AR(M) = AR(W) 를 하는거다. (전자든 후자든 둘다 된다.)
그러면 AR(M) -> AR(W)로 바뀌더라도 AR(M)의 값은 KEY에 저장이 되어있으니까 상관없다.
여기까지 보면, (1), (2), (3)은 동시에 풀릴수 있다는 것이다. 값 또한 그 범위가 더욱 더 좁혀졌다.
M=1, W=M+1, AR(M)=AR(W)
M=2, W=M-1, AR(M)=AR(W)
근데.. 좀 세련되지 못하다.. -_- (3)의 값이 동일하기 때문이다.
실제 시험문제에서도 A(M)=A(W)라는 선택지는 존재하지도 않았다.
선택지에 존재하면서 세련되게 바꾸면
M=1, W=M+1, AR(W-1)=AR(W)
M=2, W=M-1, AR(W+1)=AR(W)
이렇게 바꿀 수 있다.
7 3 이라라고 AR의 앞의 2개가 들어갔다 치자. 그렇다면
M=1, W=M+1, AR(W-1)=AR(W) : KEY = 7, AR(W) = 3
M=2, W=M-1, AR(W+1)=AR(W) : KEY = 3, AR(W) = 7
이 되고, 분기문을 쓰면 KEY < AR(W)는 각각 FALSE - TRUE 가 된다.
시험문제에는 "오름차순"정렬을 하라고 나와있다.
그렇다면 (4) 조건이 무엇인지는 몰라도
아래의 (3)과 W=W-1 표현을 사용하는 것은 TRUE 일 때만 가능한 것이고, FALSE에서는 불가능하다.
오름차순의 기본은? 당연히 작은 값이 앞에 가야 한다.
7 3 이렇게 있으면? 3 3 이 되든 3 7 이 되어야 한다.
왜냐.. 3 3 이나 3 7은 오름차순이 되지만, 7 3 은 오름차순이 안되기 때문이다.
그런데 위에도 말했듯이 7 3 -> 3 7 은 Exchange이기 때문에 안된다고 했고,
7 3 -> 3 3 은 Copy를 하면서 Key가 7로 들어간다는 의미이므로 된다고 했다.
그럼 둘중에 어느 것이 맞을까? 바로 후자이다.
(1), (2), (3) 답 나왔다.
(1) M=2
(2) W=M-1
(3) AR(W+1)=AR(W)
그리고 이를 이용해서 바로 (4), (5) 까지도 답이 나온다.
여태까지 한 방법은, 실제로 소트에서 반복문이 두번이나 나왔는데도,
단순히 처음 한번을 실행했을 때에 나온 결과를 분석해서 풀었다.
그냥 어렵게 생각할 것 없이,
Start - AR(30) - (1) - KEY=AR(M) - W=(2) - KEY
그리고 다음에 (4)가 나오는데,
처음 한번이다. 단순하게 숫자 2개를 비교한게 바로 처음의 공식이다.
아까 7과 3을 비교했다고 하지 않았나..
근데 (4) 반복문이 나오고 관련 변수는 W=W-1 이다.
반대로 말하면 W 빼고는 값이 바뀐 변수는 아무것도 없다는 거다. ((4) 분기문 내에서)
그러니까 다른건 다 고정값이고 W만 고려해서 (4)를 접근해 가자.
(1), (2), (3) 구했으니까, 이대로 하면 W=W-1 하기 이전은 당연히 W=1 이다.
그런데, W=W-1 을 해서 W=0 이 되었다.
그리고 (4)가 뭔지는 몰라도 Yes를 했다고 하자.
그러면 KEY < AR(W)로 다시 넘어가는데.. AR(0)이 되어버린다.
그럼 비교의 Y/N을 떠나서 비교 자체가 안된다.(NULL값이므로)
그렇기 때문에 W=0일 때에는 반드시 No가 나오도록 분기문을 이끌어야 한다.
어떻게 해야 할까?
(4)의 내용을 W>=1 혹은 W>0 으로 하면 된다.
위에도 말했듯이 do-while 이기 때문에 만족하는 조건이 들어가야 하기 때문이다.
선택지에는 W>=1 이 있으므로,
(4) : W>=1
이제 (5) 남았다. 이것도 금방 풀린다.
위에서 값을 복사해서 3 3 이 되었다고 했고, KEY=7 이 되었다.
그러면 이제 (5)를 실행하고 나면 M<=30 반복문이 끝난다. (M=M+1은 M<=30 과 한세트로 보고)
그럼 어떻게 해야 할까?
M<=30 반복문이 끝나고 다음 반복이 되면 KEY값은 또 바뀐다.
그렇기 때문에 KEY값이 바뀌기 전에 KEY값을 어딘가에 넣어야 한다.
그 어딘가는 다름아닌 위의 3 3 에서 3의 예전 자리로 되어야 한다.
(7 3 에서 3 3으로 기껏 바꿔놨는데 다시 7 3으로 바꾸면 어색하지 않은가)
즉, 3 7 로 바꿔야 한다는 것이다.
여기서 3 7 의 7의 자리는 다름아닌 이전 3의 자리, 즉 배열 인자값 M의 자리가 된다.
(5) 역시 답 나왔다.
(5) : AR(M) = KEY
이제 남은건 10개든 100개든 다 넣어서 (1) ~ (5)가 맞는지 해보는거다..
근데 틀릴 리가 없다.
왜냐하면 (4)의 반복문같은 경우는 일찌감치 한정된 W값에 대한 체크여부를 나타낸 것이고,
나머지는 다 Expression이기 때문에 단순표현이다.
즉, KEY < AR(W)가 Y/N으로 가든 안가든 연산에는 아무런 영향을 미치지 않기 때문이다.
못미더우면 7 3이 아니라 3 7을 넣어서 해봐라. 그래도 성립이 된다는걸 알면 할것도 없는것이 되니까.
그렇기 때문에 처음 한바퀴만 돌렸을 뿐인데도 모든 정답이 다 나올 수 있는 것이다.
질문이나 추가 원하는 자료에 대해서는 이 게시물 관련 내용에 한해서만 환영한다.
