글 읽기 - c++ mergesort 왜 틀렸는 지 이해가 되지 않습니다. 도움 부탁드립니다.

sctm1219 2년 전 0

도움이 필요합니다...

제 머리로는 어디가 틀린 것인지 모르겠습니다.

#include<iostream>

int sorted[1000000];

void merge(int list[], int left, int mid, int right) {
	int a1, a2, k;
	a1 = left, a2 = mid + 1;
	k = left;
	while (a1 <= mid && a2 <= right) {
		if (list[a1] <= list[a2]) sorted[k++] = list[a1++];
		else sorted[k++] = list[a2++];
	}
	if (a1 > mid) while (k <= right) sorted[k++] = list[a2++];
	else while (k <= right) sorted[k++] = list[a1++];
	while (left <= right) list[left] = sorted[left++];
}

void merge_sort(int list[], int left, int right) {
	if (left < right) {
		int mid =  left + (right - left) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	int t;
	int* arr;
	std::cin >> t;
	arr = new int[t];
	for (int i = 0; i < t; i++) std::cin >> arr[i];
	merge_sort(arr, 0, t - 1);
	for (int i = 0; i < t; i++) std::cout << arr[i] << "\n";
	delete[] arr;
	return 0;
}

hwa3060 2년 전 1

15번째 줄 코드를

while (left <= right)

{

list[left] = sorted[left];

left++;

}

로 바꾸면 통과가 됩니다만..

기존코드와 차이점을 도저히 못찾겠습니다..ㅠㅠ

sctm1219 2년 전 0

hwa3060님이 말씀하신걸로 바꾸었더니 놀랍게도 통과가 되었습니다...

틀렸다고 뜬 이유는 안전성 때문일까요? 도저히 이해가 되지 않습니다..ㅠㅠ

wider93 2년 전 3

c++은 연산자 실행 우선순위가 정해져 있지 않은 부분이 많습니다. f(a)+g(b)를 구하려고 해도 두 함수 중 어떤 것이 먼저 호출될지 정해져 있지 않습니다. 더 최적화하기 좋은 쪽으로 컴파일러가 선택할 수 있게 하기 위함입니다.

a[s] = b[s++]로 적으면

s++가 언제 실행될지 알 수 없습니다. 보장되는 것은 b[s]를 읽은 후에 s+=1이 된다는 것 뿐 a[s]에 더할지 a[s+1]에 더할지를 알 수 없습니다. 그래서 값을 바꾸는 s++, --i 같은 것들은 그 변수가 식 전체에 한 번만 사용될 때만 권장합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ mergesort 왜 틀렸는 지 이해가 되지 않습니다. 도움 부탁드립니다.

sctm1219 2년 전 0

hwa3060 2년 전 1

sctm1219 2년 전 0

wider93 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말