이진탐색 알고리즘

https://www.acmicpc.net/problem/10816

오늘의 스터디 첫 문제는 숫자카드2였다.

풀면서도 음...왠지 이건 아닌거 같은데 라는 강한 예감이 들었는데 맞았다. 시간초과가 난다.

이중 반복문을 써서는 절대 해결할 수 없는 문제이다.

두번째로 사용한 방법은 딕셔너리로 숫자카드에 적힌 정수의 개수를 배열로 미리 정리해놓고 가져다 쓰는 방식이다.

이 방식은 메모리 초과가 발생했다.

어떤 알고리즘으로 접근해야할지 잘 모르겠어서 빠른 검색을 했다.

참고가 될만한 좋은 블로그가 있어 내 식대로 블로그를 이해한 내용에 대해 서술하겠다.(참고:https://yhwan.tistory.com/10)

일단, 해당 블로그에서는 이진탐색과 Lower bound, Upper bound를 사용하라고 한다.

이진탐색

https://www.youtube.com/watch?v=IfIuG95RH0o

대략 요약하면,

여러개의 숫자가 카드가 뒤집어져있을 때 카드를 모두 뒤집어보지 않아도 효율적으로 몇 개의 카드만 뒤집어 내가 원하는 숫자카드를 찾는 방법이다.

 

방법: 7개의 숫자카드 중에 45가 적힌 카드를 찾아보자.

1. 7개의 숫자카드를 오름차순 또는 내림차순으로 정렬한다.
2. 처음에는 1번 카드부터 7번 카드까지 전부 검색 범위가 된다.
3. 검색 범위에서 중간에 위치한 카드(4번 카드)를 확인해보면 41이 나온다.
4. 45보다 41이 크다면 1, 2, 3번 카드는 찾는 값보다 당연히 작다.
5. 그러므로 검색 범위에서 1, 2, 3, 4번 카드는 제거하고 5, 6, 7번 카드만 다시 탐색한다.
6. 이번에는 6번 카드를 확인해보자.
7. 6번카드가 45가 나와서 내가 찾는 값과 동일하다.

위의 이진탐색과 Lower bound, Upper bound를 사용하여 숫자카드2를 풀어보자.