개요 https://www.acmicpc.net/problem/1920 해당 문제는 5년 전 고등학생때 했었던 문제입니다. 하도 풀어도 시간초과가 발생해서 포기했던 기억이 나네요. 어떻게 하면 M개의 난수가 A배열에 있는 지를 찾는지가 관건인 문제였습니다. 지금 보니 시간 복잡도를 조금만 줄이면 되는 문제로 이진 탐색으로 해결했습니다. 이진 탐색 알고리즘 알고리즘을 배우면 가장 먼저 배우는 알고리즘으로 작년에 다시 시도했을 때도 알고 있던 알고리즘이었습니다. 이를 적용할 생각이 없던 게 아쉽네요 정의는 아래 그림으로 보시면 이해하는 것이 편할 겁니다. 위하고 문제의 다른 점은 어떤 수들이 오는지 모르고 정렬되지 않고 입력된다는 점입니다. 탐색하면서 절반 씩 범위를 줄이기 때문에 시간 복잡도는 O(logN..
