irre   4년 전

c 배운지 얼마 안되서 어디서 틀렸는지 잘모르겠네요 ㅠㅠ

1207koo   4년 전

1. 52번째 줄에 return이 애매합니다.

애초에 리턴 타입이 int인데 아무것도 리턴하지 않는 것이 이상합니다.

그리고 return이 아니라 continue를 의도하신 것 같습니다 (또는 break를 원하신 것 같기도 합니다. return에 가까운 게 break이긴 합니다만 continue가 알고리즘 상 맞는 것 같습니다)

2. 20번째 줄에 정렬 범위를 어떻게 수정해야 할까요? 이건 단순 실수로 보입니다.

irre   4년 전

20번째줄 정렬 범위는 0 ~ i-1 로 수정하고 52번째 줄은 continue로 수정 했지만 시간초과가 뜨네요 ㅠㅠ

1207koo   4년 전

그거는 퀵 소트 특징 때문에 그렇습니다.

퀵소트는 평균적으로 N log N (N은 정렬해야 하는 배열의 크기)의 시간이 들지만

최악의 경우 N^2의 시간이 듭니다.

예를 들어서 정렬이 되어 있는 경우나 역정렬 되어 있는 경우가 그런 케이스입니다.

해결법은 다른 정렬 방식을 사용하거나

피봇을 잘 잡는 방법이 있습니다.

다른 정렬 방식으로는 std::sort도 있긴 하지만 배우기 위해서는 직접 정렬을 구현하는 것이 좋고

수의 범위가 100만 이하이므로 카운팅 소트가 좋을 것 같습니다. (카운팅 소트 특성 상 이런 문제에서만 정렬이 가능하니까 다른 방법도 알아보세요)

피봇을 잘 잡는 방법으로는 여러 개의 숫자(보통 시작, 끝, 중간 위치를 고릅니다) 중 중앙값(예를 들어서 3개를 고르면 2번째로 큰 숫자)을 피봇으로 쓰는 것이 대표적입니다.

배열을 두 개의 부분 배열로 분리할 때 크기가 비슷할 수록 속도가 빨라집니다. 따라서 일부러 여러 개의 수를 봐서 중앙값에 가까울 확률이 높은 수를 고르는 것입니다. (물론 이 경우에도 최악의 경우에 걸리는 시간은 N^2지만, 저격 데이터를 만들기가 더 어렵고, 느릴 확률도 더 적기 때문에 통과될 가능성이 있습니다. 최악이 N^2인 것은 같기 때문에 이 방법을 쓰더라도 퀵소트만 쓰는 습관은 좋지 않습니다.)

그 외에도 퀵소트를 빠르게 할 수 있는 방법은 정렬해야 하는 배열의 범위가 작은 경우 삽입 정렬 등을 하는 방법이 있습니다. (구현은 좀 더 귀찮아 집니다) 삽입 정렬 자체는 N^2지만 곱해지는 계수가 일반적으로 작기 때문에 N이 작은 경우에 대해서는 삽입 정렬이 더 빠릅니다. (N=1일 때 10N^2가 2N보다 큰 것과 같은 이유입니다)

irre   4년 전

머지소트로 제출했더니 맞았습니다

덕분에 배웠습니다 감사합니다~

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