알고리즘 문제를 풀던 중 "비내림차순으로 정렬된" 이라는 문장을 보았다.
내림차순도, 오름차순도 아니고 대체 뭐지... 라는 생각이 들어서 찾아보았다.
과연 "비내림차순"은 무엇일까?
비내림차순, 영어로는 non-decreasing.
[ 1 2 3 3 3 4 5 ], [ 1 2 3 4 5 ] 순서로 정렬된 수열들을 보았다고 생각하자.
사람들은 일반적으로 두 수열에 대해서 "오름차순으로 정렬이 되었구나" 라고 생각할 것이다.
하지만 [ 1 2 3 3 3 4 5 ]는 비내림차순(non-decreasing)이고, [ 1 2 3 4 5 ]는 오름차순(ascending)이다.
둘의 차이는 간단하다.
숫자가 증가하는 순서로 정렬된 상태에서 크기가 같은 수가 포함될 수 있는가의 차이이다.
내림차순은 수가 증가하거나 같을 수 있다. [ 1 2 3 3 3 4 5 ] : 4, 5번 째 수가 증가하지 않고 이전의 수와 크기가 같음
오름차순은 수가 증가해야한다. (같으면 안됨) [ 1 2 3 4 5 ] : 수가 계속해서 증가함
즉, 일반화하면
내림차순은 a1 ≤ a2 ≤ a3 .... ≤ an
오름차순은 a1 < a2 < a3 ... < an 의 차이다.
요약
-----------------------------------
비내림차순 : 수가 증가하거나 같아야 함.
오름차순 : 수가 증가해야함.
-----------------------------------