이거 오늘 내가 퇴근하기 전에 만난 문제야. 내일 코딩해야 됨.
니가 일정시간 동안 gps 데이터를 수집했다고 쳐. 각각은 위도,경도,시간 세가지 정보가 배열이나 리스트로 있다 해봐
[{lat 1, lng 2, ts 123}, {lat 2, lng 3, ts 124} ...]
지도에 경로보여주기 서비스를 이용해서 이 경로+지도 이미지를 만들려고 하는데 이 서비스는 최대 n개의 데이터가 한계야.
그래서 니가 임의의 경로가 주어지면 거기서 n개를 최대한 균등하게 골라내는 게 문제야.
단순화하면 x개의 원소에서 n개를 균등한 간격으로 골라내는 거지. 예를들어 이 함수를 evenlyN 이라 할 떄
evenlyN(5,3) // 0,1,2,3,4 에서 3개를 고름
=> [0, 2, 4]
evenlyN(4, 3) // 0,1,2,3 에서 3개 고름
=> [0, 1, 3] 또는 [0, 2, 3]
실제로는 대략 이렇게 될거야
evenlyN(451, 80)
자 이걸 최대한 간단한 알고리듬으로 만들어봐라! ㅎㅎ
넘 쉽잖아.
근데 실무에선 보간 좌표로 구해내야하지 않겠음?
그냥 실제 값에 가까운 nearest neighborhood 를 하란거지?
양쪽 끝을 hold 하는지 여백균등으로 하는지도 결정해야함.
그냥 451/80 값으로 점프하고 끝자리쪽가서 예외처리만해주면되는거아님?? 더필요함??
그건 real number 니까 약간의 트릭이 필요하징.
결국 평균노름이라 아무렇게나 해도되는거아님??
가장자리를 hold 해야 되면 2 빼고 놀고 안에다 1 더해주면 되고.
이를 테면 int N = 451, M = 80; for( int i = 0; i < M; ++i ) result[i] = src[ N * ( i * 2 + 1 ) / ( M * 2 ) ]; 처럼 되겠지.
에이 그렇지 아주 어려운건 아니지 최대한 엘레강스 하면서 이펙티브한 알고리듬을 찾아내자는 거지 ㅎㅎ. 퇴근 전에 옆생키가 했다길래 보니까 맨 끝지점이 빠짐. 맨 첫지점과 끝지점이 있어야 되고 데이터는 이미 에러 필터링 후처리되어서 유효한 데이터만 존재
앙 맨 끝점 처리할거면 두 개 접고 놀면 됨. 저긴 반올림 처리도 되어있음.
에이 이런건 코세는 달려들면 안돼지 ㅎㅎ
int N = 451, M = 80; int EDGE_HOLD = M - 2; result[ 0 ] = src[ 0 ]; result[ M - 1 ] = src[ N - 1 ]; for( int i = 0; i < EDGE_HOLD; ++i ) result[ i + 1 ] = src[ N * ( i * 2 + 1 ) / ( EDGE_HOLD * 2 ) ];
이런식이겠쥐?
근데 이게 evenlyN(4,3), evenlyN(2,3), ... 이런 경우도 있다