백준 C++ 1920번 수 찾기 ( 이중탐색 )

 

반갑습니다.

 

요즘은

중국어를 공부하고 싶은 마음에

단어 책을 샀습니다.

 

근데 이게 결국 발음도 중요하지 않습니까

강의도 사야 하나..

 

이게 무슨 고추장이 밥보다 많은 상황인가...

주객전도일세...

 

---

 

문제를 이해했다

첫 번째 A, 5개 나오고

 

A의 친구들 주르륵

그다음에 B, 5개 나오고

 

A의 친구들이 B에 있는지 비교해서 있으면 1 없으면 0 

 

 

이중 포문이라 그런지

테케 답은 맞는데 시간초과 난다

 

흠....

어떻게 푸는 게 가장 현명할까..?

하긴 m이랑 n이 100000 개여서..

아마 시간이 좀 이상해지는 거 같다.

 

흠..

 

인지 씨를 찾았다.

 

인지 씨는 뭐..?

 

이분탐색에 대해 알려주었다.

 

 

이분탐색

binary_search라고 불리고

헤더파일 <algorithm>에 있다고 한다.

 

 

업다운이라고 생각하면 쉽다고 한다.

 

사용하면

컴퓨터가 자동으로 가운데 숫자를 지정하고

우리가 필요한 숫자랑 비교해서

작으면 왼쪽만 보고

크면 오른쪽만 보고

다시 남은 곳에서 가운데를 찾아 지정해 줘

그럼 또 비교하고

그렇게 차동으로 찾아주고 true / false로 뱉어주는 친구이다.

 

 

이 친구의 시간복잡도는 엄청 작다고 한다.

 

 

가장 중요한 것은

정렬을 해줘야 한다는 것!

 

이걸로 풀어보겠습니다.

 

아! 쓰는 방법은

binary_search(시작, 끝, 찾을 숫자);

그리고 그걸 담을 bool값까지!

 

 

짜잔! 완성!

 

그리고 인지 씨는 

굳이 vb 벡터 안 만들어도 된다고

숫자만 찾으면 되는 거 아니냐고 했다.

그렇네?!

 

그리고 또 하나 true는 자동으로 숫자 1이어서 그냥

굳이 저렇게 삼항연산자 안 써도 된다고 한다.

 

 

밑에 수정했다.

 

---

 

오늘은 이중탐색을 배웠다.

binary_search

 

내가 자주 활용 할 수 있을지 잘 모르겠다.

 

내가 말이다 내가

 

좋은 친구인데 좋은 친구일수록 활용하는 게 어렵다.

 

순서를 기억하고 싶을 땐

pair로 vector을 만들어주면 괜찮다고 한다.

 

그래 다음을 부탁한다! 이중탐색!