디버깅
프로그램을 짜는 것보다 중요한 것은 프로그램이 원하는 대로 돌아가는지 확인하는 과정인 것 같다. 코드를 작성하더라도 반드시 내 의도대로 돌아가는 보장이 없다. 그래서 디버깅을 해야한다. 디버깅을 하면 내 논리가 어디서 막히는 지 확인할 수 있기 때문이다.
디버깅도 상황에 따라 다르게 쓰고 있다. 변수가 뭔지 해석할 때는 출력코드를 사용하고 반복문이 어떻게 작동하는지 확인할 때는 디버깅툴을 사용한다. 코테도 봐야하는 상황을 고려할 때 출력코드를 사용하는 것에 익숙해져야겠다.
병합정렬을 구현하는데 합병 로직이 제대로 작동하지 않았다.
void Merge(vector<int> &a, int lo, int mid, int hi) {
cout << "Before: ";
Print(a, lo, hi); // lo: 현재 배열의 첫번째 인덱스, hi: 현재 배열의 끝 인덱스
int i = lo, j = mid + 1; // i: 왼쪽 배열의 첫번째 인덱스, mid: 왼쪽 배열의 끝 인덱스
// j: 오른쪽 배열 첫번째 인덱스 -> 구간: lo ~ mid, mid+1 ~ hi
// cout << endl;
// cout << "lo: " << lo << " hi: " << hi << endl;
// cout << "i: " << i << " mid: " << mid << " j: " << j << endl;
// cout << endl;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid) {
while (j <= hi) {
a[k] = aux[j++];
}
} else if (j > hi) {
while (i <= mid) {
a[k] = aux[i++];
}
} else if (aux[j] < aux[i]) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
cout << "After : ";
Print(a, lo, hi);
// cout << endl;
// count += hi - lo + 1;
// cout << "Count : " << hi - lo + 1 << ", " << count << endl; // 누적 카운트 (디버깅용)
}
일단 코드도 너무 길 뿐더러 각 변수가 어떤 역할을 하는지 처음 보고서는 이해를 하지 못했다. 그래서 나름 가설을 세우고 가설대로 코드가 작동하는지 출력코드를 작성했다.
// cout << endl;
// cout << "lo: " << lo << " hi: " << hi << endl;
// cout << "i: " << i << " mid: " << mid << " j: " << j << endl;
// cout << endl;
지금은 주석처리했지만 이 부분이 내가 궁금했던 변수들이다. 출력을 화면을 보면서 변수 옆에 다음과 같이 정리했다.
int i = lo, j = mid + 1; // i: 왼쪽 배열의 첫번째 인덱스, mid: 왼쪽 배열의 끝 인덱스
// j: 오른쪽 배열 첫번째 인덱스 -> 구간: lo ~ mid, mid+1 ~ hi
변수의 역할을 확인하고나서 병합로직을 작성했다. 병합로직에서 데이터들이 원하는 자리에 계속 들어가지 않았다.
for (int k = lo; k <= hi; k++) {
if (i > mid) {
while (j <= hi) {
a[k] = aux[j++];
}
} else if (j > hi) {
while (i <= mid) {
a[k] = aux[i++];
}
} else if (aux[j] < aux[i]) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
이번에는 디버깅툴을 사용해서 인덱스의 변화에 따라 배열의 데이터가 어떻게 변하는지 관찰했다. 그 결과, 조건문의 첫번째와 두번째 로직에서 k가 제대로 갱신되지 않았음을 확인했다.
if (i > mid) {
while (j <= hi) {
a[k] = aux[j++];
}
} else if (j > hi) {
while (i <= mid) {
a[k] = aux[i++];
}
나는 반복문에서 k가 갱신이 되고 있다고 가정을 했는데 조건문 로직 내부에 while문이 반복되고 있었고 해당 과정에서는 k가 제대로 갱신되고 있지 않은 상태였다. 따라서 while문 순회를 한번 돌 때마다 k를 1씩 증가시켰다.
while (j <= hi) {
a[k++] = aux[j++];
}
} else if (j > hi) {
while (i <= mid) {
a[k++] = aux[i++];
}
병합정렬은 의도대로 구현되었다.