yujjjang   4년 전

시간 초과가 됩니다. 50% 에서 바뀌더군요.

무한 루프에 빠져들어서 시간초과가 되는건지.. 확인하고 있는데 무엇이 잘못되었는지 경우를 찾을수가 없어요.. 방법도 잘 모르구요

혹은 알고리즘 문제로 시간이 너무 오래걸려서 해결하지 못하는 거라면 혹시 문제점을 지적해주실수 있으신가요?

공부를 시작한지가 얼마되지않아서 아는게 없네요..ㅠ

chogahui05   4년 전

재귀함수로 하나씩 줄여가면서 답을 만족하는 가장 작은 값을 리턴하게 하면

그냥 탐색하는 것이랑 다른 게 무엇인지 잘 모르겠습니다.


예를 들어서;

1 3 4 5 6 7 11 12 14 16 17 23 27 ... 100222

이런 데이터가 있습니다.

이 중에 9라는 데이터는 없습니다. 이진 탐색으로도 당연히 안 찾아지는 데이터입니다.

그러면 100222부터 탐색하실려고요?


물론, 역으로 탐색한다고 한다면

1 1 1 1 1 1 1 ... 1 3 4 7 11 100222

이런 데이터에서 걸리겠죠.


힌트 하나 드릴게요.

1 3 4 5 6 7 11 12 14 16 17 ...

밑줄 친 부분을 먼저 주목해 주세요. 9보다 작게 되는 최초의 위치.

9보다 크게 되는 최초의 위치는 어떻게 찾을 수 있을지는 밑줄을 보시면 되고요.

이거 역시 이분 탐색으로 찾으실 수 있습니다.

yujjjang   4년 전

감사합니다. 덕분에 무엇이 문제점인지 알고 다시 고쳤습니다.

문제해결에 도움을 주셔서 너무 감사드립니다. !!

감기조심하세요~

chogahui05   4년 전

어려운 알고리즘 하나 하셨네요..

보통 이진탐색만 배우는데. 저도 여기서 이분탐색을 배웠어요.. 제일 쉽게 설명하자면

인접한 것끼리 비교하는 연산이 핵심이고요.


이것도 어려워지면 한없이 어려워지는 알고리즘이니.. 까다롭지요..

제가 못 푼 문제 중에서 2990번도 사실 정해가 이분 탐색입니다.

구현하기가 짜증날 정도라서 그냥 트라이를 써서 틀렸지만요.


함수 식만 잘 세우는 연습만 해 보세요.

추천 문제 하나만 링크하겠습니다.

https://www.acmicpc.net/proble...

yujjjang   4년 전

컴퓨터 공부를 시작한지 몇일이되지않아서.. 덕분에 좋은거 배워갑니다 !!

정답비율이 너무 낮아서 많이 두렵지만 오늘 한번 열심히 해보겠습니다.

너무 감사드립니다. 풀다가 모르는것 있으면 질문을 올릴거 같아서 .... 밤에 시간나시면 한번만 확인부탁드립니다 감사해요 !!

댓글을 작성하려면 로그인해야 합니다.