유사이미지 서비스를 개발 중인 광성이는 이제 거의 막바지에 다다랐다!
딥러닝을 이용하여 이미지의 특징값을 추출하는 것을 완료하였고,
이제 남은 작업은 전체 이미지의 특징값을 색인하고 있는 서버를 만들고, 사용자가 이미지 쿼리를 요청하면 해당 이미지의 특징값과 거리가 가장 가까운 K개를 뽑아 결과를 반환하기만 하면 된다.
문제는 사용자 이미지 쿼리와 가장 가까운 K개를 선택할 때, 100% 정확한 결과를 추출하기에는 이미지 데이터셋의 크기가 너무 크고 계산량이 너무 많아 정해진 시간 내에 결과를 반환할 수가 없다.
고심 끝에 광성이는 100% 정확하지는 않지만 정답과 유사한 결과를 탐색하는 빠른 알고리즘을 개발하였다.
예를 들면,
사용자 쿼리 이미지와 거리가 가까운 이미지 5개를 뽑을 경우, 그 거리는 각각 [1, 2, 3, 5, 7] 이라 하자.
반면, 새로운 알고리즘의 결과는 [1, 2, 3, 7, 8] 로 정답에 있는 거리 5의 이미지가 누락되었지만 처리속도는 5배 빠르고, 결과도 그럭저럭 서비스하기에 나쁘지 않다.
알고리즘 개발을 완료하고 서비스에 투입하려던 찰나, 참견하기 좋아하는 영준이가 자신도 비슷한 알고리즘을 만들었다며 두 알고리즘 중 더 나은 알고리즘을 서비스에 투입하자고 제안하였다.
이제 광성이는 당신에게 어떤 알고리즘이 더 좋은지 판단하는 프로그램을 구현해달라고 의뢰하였다.
100% 정확한 결과를 내는 알고리즘을 통해 얻은 길이가 K인 거리 리스트와,
유사한 결과를 내는 N개의 알고리즘의 결과가 주어졌을 때 다음 성능 조건에 따라 가장 좋은 알고리즘을 고르는 프로그램을 작성하라.
좋은 알고리즘의 기준은 다음과 같다.
예를 들어,
K=5 인 100% 정확한 알고리즘의 결과가 [2, 3, 5, 5, 6] 이라고 하자.
알고리즘 0 의 결과는 [3, 5, 5, 7, 8] 이라면, 거리 2, 6 이 누락으로 총 2개가 누락되었다.
알고리즘 1 의 결과는 [2, 3, 5, 5, 7] 이라면, 거리 6 누락으로 1개 누락되었다.
알고리즘 2 의 결과는 [3, 5, 5, 6, 7] 이라면, 거리 2 누락으로 1개 누락되었다.
알고리즘 0은 총 2개 누락으로 알고리즘 1, 2보다 누락 개수가 많아 안 좋은 알고리즘이며,
알고리즘 1, 2는 1개 누락으로 누락된 개수는 같지만, 알고리즘 1은 누락된 거리의 최소값이 6, 알고리즘 2는 누락된 거리의 최소값이 2로 알고리즘 1이 더 큰 거리가 누락되었으므로 셋 중 가장 좋은 알고리즘은 1번 알고리즘이다.
리스트의 길이 K (1 <= K <= 50) 와 알고리즘의 갯수 N(1 <= N <= 100000) 이 주어진다.
이어서 길이가 K인 정답셋이 거리 순으로 주어진다.
다음으로 총 N개의 알고리즘의 결과셋이 주어진다.
가장 좋은 알고리즘의 인덱스를 출력한다.
5 3
2 3 5 5 6
3 5 5 7 8
2 3 5 5 7
3 5 5 6 7
1