n개의 양의 정수가 주어지는데
이게
만약
1, 2, 3, 1, 3, 4, 5, 3
이렇게 있다치면
최대 최소의 차가 제일 큰거를 구하는건데
최대는 무조건 최소보다 뒤에잇어야함.
뒤에 나오는수 y랑 y보다 앞에 있는 수 x의 차가 제일 큰거를 구하는건데
저 예를보면 답은 1, 5 야.
저걸 그냥 조건없이하면 할수있겠는데
분할과 정복으로 알고리즘을 짜라고하네... 시간 복잡도가 더 좋지않은데 이거 연습하라면서...
그래서 일단 했는데 divide and conquer하면 재기가 들어가야하는데 어떻게 base case를 짜야 이게 값을 찾는지 도무지 어제 5시간 뻘짓햇는데도 못구했어...
좀 힌트라도 줄 사람있나 해서 글 써봄.... ㅠ
1 2 3 1 /3 4 5 3
이렇게 나눠서
1 2 3 1의 최소 최대
3 4 5 3의 최소 최대
1 2 3 1의 최소와 3 4 5 3의 최대
1 2 3 1로 반을 나눈 최소최대 구할땐
1 2/31 로 나눠서 재귀적으로
이제 알겠징헤헷..
내가지금 학교라 코드는 못짜주겟는데 집와서까지 못하면 알려줄겡;;
그럼인덱스 1, 2칸씩 이상 떨어진거에 대해 문제가 생길거같은데여..
그리고 뒷수- 앞수라. 최대최소가 의미가있을까여...
마지막으로 10 2 1 5 8 4 7 3일 경우엔 중간에 걸쳐지는 수 1, 8이 최대인데.. 저 알고리즘으로 안풀리네여..ㅎㅎ
최대 최소의 차가 무슨 의미야?
어떤수 보다 뒤에 있는 숫자와 어떤수와의 차를 구해서 그 차가 제일 큰 숫자쌍을 말하면되는거지?
ㅇㅇ
1,8도 당연히 구하잖아..
10 2 1 5 / 8 4 7 3에서 1이 최소고 8이 최대니깐 8-1을 당연히 거치지
스포츠 패널 모집 단ㅌ 방송채팅페이지제공! 텔레그램 JFK44
짝1.97 팽이2.90 묶음/올킬 찾는사람 손! fu72